/* Liveness for SSA trees.
|
/* Liveness for SSA trees.
|
Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Contributed by Andrew MacLeod <amacleod@redhat.com>
|
Contributed by Andrew MacLeod <amacleod@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 "basic-block.h"
|
#include "basic-block.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-ssa-live.h"
|
#include "tree-ssa-live.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "vecprim.h"
|
#include "vecprim.h"
|
|
|
static void live_worklist (tree_live_info_p, int *, int);
|
static void live_worklist (tree_live_info_p, int *, int);
|
static tree_live_info_p new_tree_live_info (var_map);
|
static tree_live_info_p new_tree_live_info (var_map);
|
static inline void set_if_valid (var_map, bitmap, tree);
|
static inline void set_if_valid (var_map, bitmap, tree);
|
static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
|
static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
|
tree, basic_block);
|
tree, basic_block);
|
static inline void register_ssa_partition (var_map, tree, bool);
|
static inline void register_ssa_partition (var_map, tree, bool);
|
static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
|
static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
|
var_map, bitmap, tree);
|
var_map, bitmap, tree);
|
static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
|
static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
|
|
|
/* This is where the mapping from SSA version number to real storage variable
|
/* This is where the mapping from SSA version number to real storage variable
|
is tracked.
|
is tracked.
|
|
|
All SSA versions of the same variable may not ultimately be mapped back to
|
All SSA versions of the same variable may not ultimately be mapped back to
|
the same real variable. In that instance, we need to detect the live
|
the same real variable. In that instance, we need to detect the live
|
range overlap, and give one of the variable new storage. The vector
|
range overlap, and give one of the variable new storage. The vector
|
'partition_to_var' tracks which partition maps to which variable.
|
'partition_to_var' tracks which partition maps to which variable.
|
|
|
Given a VAR, it is sometimes desirable to know which partition that VAR
|
Given a VAR, it is sometimes desirable to know which partition that VAR
|
represents. There is an additional field in the variable annotation to
|
represents. There is an additional field in the variable annotation to
|
track that information. */
|
track that information. */
|
|
|
/* Create a variable partition map of SIZE, initialize and return it. */
|
/* Create a variable partition map of SIZE, initialize and return it. */
|
|
|
var_map
|
var_map
|
init_var_map (int size)
|
init_var_map (int size)
|
{
|
{
|
var_map map;
|
var_map map;
|
|
|
map = (var_map) xmalloc (sizeof (struct _var_map));
|
map = (var_map) xmalloc (sizeof (struct _var_map));
|
map->var_partition = partition_new (size);
|
map->var_partition = partition_new (size);
|
map->partition_to_var
|
map->partition_to_var
|
= (tree *)xmalloc (size * sizeof (tree));
|
= (tree *)xmalloc (size * sizeof (tree));
|
memset (map->partition_to_var, 0, size * sizeof (tree));
|
memset (map->partition_to_var, 0, size * sizeof (tree));
|
|
|
map->partition_to_compact = NULL;
|
map->partition_to_compact = NULL;
|
map->compact_to_partition = NULL;
|
map->compact_to_partition = NULL;
|
map->num_partitions = size;
|
map->num_partitions = size;
|
map->partition_size = size;
|
map->partition_size = size;
|
map->ref_count = NULL;
|
map->ref_count = NULL;
|
return map;
|
return map;
|
}
|
}
|
|
|
|
|
/* Free memory associated with MAP. */
|
/* Free memory associated with MAP. */
|
|
|
void
|
void
|
delete_var_map (var_map map)
|
delete_var_map (var_map map)
|
{
|
{
|
free (map->partition_to_var);
|
free (map->partition_to_var);
|
partition_delete (map->var_partition);
|
partition_delete (map->var_partition);
|
if (map->partition_to_compact)
|
if (map->partition_to_compact)
|
free (map->partition_to_compact);
|
free (map->partition_to_compact);
|
if (map->compact_to_partition)
|
if (map->compact_to_partition)
|
free (map->compact_to_partition);
|
free (map->compact_to_partition);
|
if (map->ref_count)
|
if (map->ref_count)
|
free (map->ref_count);
|
free (map->ref_count);
|
free (map);
|
free (map);
|
}
|
}
|
|
|
|
|
/* This function will combine the partitions in MAP for VAR1 and VAR2. It
|
/* This function will combine the partitions in MAP for VAR1 and VAR2. It
|
Returns the partition which represents the new partition. If the two
|
Returns the partition which represents the new partition. If the two
|
partitions cannot be combined, NO_PARTITION is returned. */
|
partitions cannot be combined, NO_PARTITION is returned. */
|
|
|
int
|
int
|
var_union (var_map map, tree var1, tree var2)
|
var_union (var_map map, tree var1, tree var2)
|
{
|
{
|
int p1, p2, p3;
|
int p1, p2, p3;
|
tree root_var = NULL_TREE;
|
tree root_var = NULL_TREE;
|
tree other_var = NULL_TREE;
|
tree other_var = NULL_TREE;
|
|
|
/* This is independent of partition_to_compact. If partition_to_compact is
|
/* This is independent of partition_to_compact. If partition_to_compact is
|
on, then whichever one of these partitions is absorbed will never have a
|
on, then whichever one of these partitions is absorbed will never have a
|
dereference into the partition_to_compact array any more. */
|
dereference into the partition_to_compact array any more. */
|
|
|
if (TREE_CODE (var1) == SSA_NAME)
|
if (TREE_CODE (var1) == SSA_NAME)
|
p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
|
p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
|
else
|
else
|
{
|
{
|
p1 = var_to_partition (map, var1);
|
p1 = var_to_partition (map, var1);
|
if (map->compact_to_partition)
|
if (map->compact_to_partition)
|
p1 = map->compact_to_partition[p1];
|
p1 = map->compact_to_partition[p1];
|
root_var = var1;
|
root_var = var1;
|
}
|
}
|
|
|
if (TREE_CODE (var2) == SSA_NAME)
|
if (TREE_CODE (var2) == SSA_NAME)
|
p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
|
p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
|
else
|
else
|
{
|
{
|
p2 = var_to_partition (map, var2);
|
p2 = var_to_partition (map, var2);
|
if (map->compact_to_partition)
|
if (map->compact_to_partition)
|
p2 = map->compact_to_partition[p2];
|
p2 = map->compact_to_partition[p2];
|
|
|
/* If there is no root_var set, or it's not a user variable, set the
|
/* If there is no root_var set, or it's not a user variable, set the
|
root_var to this one. */
|
root_var to this one. */
|
if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
|
if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
|
{
|
{
|
other_var = root_var;
|
other_var = root_var;
|
root_var = var2;
|
root_var = var2;
|
}
|
}
|
else
|
else
|
other_var = var2;
|
other_var = var2;
|
}
|
}
|
|
|
gcc_assert (p1 != NO_PARTITION);
|
gcc_assert (p1 != NO_PARTITION);
|
gcc_assert (p2 != NO_PARTITION);
|
gcc_assert (p2 != NO_PARTITION);
|
|
|
if (p1 == p2)
|
if (p1 == p2)
|
p3 = p1;
|
p3 = p1;
|
else
|
else
|
p3 = partition_union (map->var_partition, p1, p2);
|
p3 = partition_union (map->var_partition, p1, p2);
|
|
|
if (map->partition_to_compact)
|
if (map->partition_to_compact)
|
p3 = map->partition_to_compact[p3];
|
p3 = map->partition_to_compact[p3];
|
|
|
if (root_var)
|
if (root_var)
|
change_partition_var (map, root_var, p3);
|
change_partition_var (map, root_var, p3);
|
if (other_var)
|
if (other_var)
|
change_partition_var (map, other_var, p3);
|
change_partition_var (map, other_var, p3);
|
|
|
return p3;
|
return p3;
|
}
|
}
|
|
|
|
|
/* Compress the partition numbers in MAP such that they fall in the range
|
/* Compress the partition numbers in MAP such that they fall in the range
|
0..(num_partitions-1) instead of wherever they turned out during
|
0..(num_partitions-1) instead of wherever they turned out during
|
the partitioning exercise. This removes any references to unused
|
the partitioning exercise. This removes any references to unused
|
partitions, thereby allowing bitmaps and other vectors to be much
|
partitions, thereby allowing bitmaps and other vectors to be much
|
denser. Compression type is controlled by FLAGS.
|
denser. Compression type is controlled by FLAGS.
|
|
|
This is implemented such that compaction doesn't affect partitioning.
|
This is implemented such that compaction doesn't affect partitioning.
|
Ie., once partitions are created and possibly merged, running one
|
Ie., once partitions are created and possibly merged, running one
|
or more different kind of compaction will not affect the partitions
|
or more different kind of compaction will not affect the partitions
|
themselves. Their index might change, but all the same variables will
|
themselves. Their index might change, but all the same variables will
|
still be members of the same partition group. This allows work on reduced
|
still be members of the same partition group. This allows work on reduced
|
sets, and no loss of information when a larger set is later desired.
|
sets, and no loss of information when a larger set is later desired.
|
|
|
In particular, coalescing can work on partitions which have 2 or more
|
In particular, coalescing can work on partitions which have 2 or more
|
definitions, and then 'recompact' later to include all the single
|
definitions, and then 'recompact' later to include all the single
|
definitions for assignment to program variables. */
|
definitions for assignment to program variables. */
|
|
|
void
|
void
|
compact_var_map (var_map map, int flags)
|
compact_var_map (var_map map, int flags)
|
{
|
{
|
sbitmap used;
|
sbitmap used;
|
int tmp, root, root_i;
|
int tmp, root, root_i;
|
unsigned int x, limit, count;
|
unsigned int x, limit, count;
|
tree var;
|
tree var;
|
root_var_p rv = NULL;
|
root_var_p rv = NULL;
|
|
|
limit = map->partition_size;
|
limit = map->partition_size;
|
used = sbitmap_alloc (limit);
|
used = sbitmap_alloc (limit);
|
sbitmap_zero (used);
|
sbitmap_zero (used);
|
|
|
/* Already compressed? Abandon the old one. */
|
/* Already compressed? Abandon the old one. */
|
if (map->partition_to_compact)
|
if (map->partition_to_compact)
|
{
|
{
|
free (map->partition_to_compact);
|
free (map->partition_to_compact);
|
map->partition_to_compact = NULL;
|
map->partition_to_compact = NULL;
|
}
|
}
|
if (map->compact_to_partition)
|
if (map->compact_to_partition)
|
{
|
{
|
free (map->compact_to_partition);
|
free (map->compact_to_partition);
|
map->compact_to_partition = NULL;
|
map->compact_to_partition = NULL;
|
}
|
}
|
|
|
map->num_partitions = map->partition_size;
|
map->num_partitions = map->partition_size;
|
|
|
if (flags & VARMAP_NO_SINGLE_DEFS)
|
if (flags & VARMAP_NO_SINGLE_DEFS)
|
rv = root_var_init (map);
|
rv = root_var_init (map);
|
|
|
map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
|
map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
|
memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
|
memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
|
|
|
/* Find out which partitions are actually referenced. */
|
/* Find out which partitions are actually referenced. */
|
count = 0;
|
count = 0;
|
for (x = 0; x < limit; x++)
|
for (x = 0; x < limit; x++)
|
{
|
{
|
tmp = partition_find (map->var_partition, x);
|
tmp = partition_find (map->var_partition, x);
|
if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
|
if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
|
{
|
{
|
/* It is referenced, check to see if there is more than one version
|
/* It is referenced, check to see if there is more than one version
|
in the root_var table, if one is available. */
|
in the root_var table, if one is available. */
|
if (rv)
|
if (rv)
|
{
|
{
|
root = root_var_find (rv, tmp);
|
root = root_var_find (rv, tmp);
|
root_i = root_var_first_partition (rv, root);
|
root_i = root_var_first_partition (rv, root);
|
/* If there is only one, don't include this in the compaction. */
|
/* If there is only one, don't include this in the compaction. */
|
if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
|
if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
|
continue;
|
continue;
|
}
|
}
|
SET_BIT (used, tmp);
|
SET_BIT (used, tmp);
|
count++;
|
count++;
|
}
|
}
|
}
|
}
|
|
|
/* Build a compacted partitioning. */
|
/* Build a compacted partitioning. */
|
if (count != limit)
|
if (count != limit)
|
{
|
{
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
|
map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
|
count = 0;
|
count = 0;
|
/* SSA renaming begins at 1, so skip 0 when compacting. */
|
/* SSA renaming begins at 1, so skip 0 when compacting. */
|
EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
|
{
|
{
|
map->partition_to_compact[x] = count;
|
map->partition_to_compact[x] = count;
|
map->compact_to_partition[count] = x;
|
map->compact_to_partition[count] = x;
|
var = map->partition_to_var[x];
|
var = map->partition_to_var[x];
|
if (TREE_CODE (var) != SSA_NAME)
|
if (TREE_CODE (var) != SSA_NAME)
|
change_partition_var (map, var, count);
|
change_partition_var (map, var, count);
|
count++;
|
count++;
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
free (map->partition_to_compact);
|
free (map->partition_to_compact);
|
map->partition_to_compact = NULL;
|
map->partition_to_compact = NULL;
|
}
|
}
|
|
|
map->num_partitions = count;
|
map->num_partitions = count;
|
|
|
if (rv)
|
if (rv)
|
root_var_delete (rv);
|
root_var_delete (rv);
|
sbitmap_free (used);
|
sbitmap_free (used);
|
}
|
}
|
|
|
|
|
/* This function is used to change the representative variable in MAP for VAR's
|
/* This function is used to change the representative variable in MAP for VAR's
|
partition from an SSA_NAME variable to a regular variable. This allows
|
partition from an SSA_NAME variable to a regular variable. This allows
|
partitions to be mapped back to real variables. */
|
partitions to be mapped back to real variables. */
|
|
|
void
|
void
|
change_partition_var (var_map map, tree var, int part)
|
change_partition_var (var_map map, tree var, int part)
|
{
|
{
|
var_ann_t ann;
|
var_ann_t ann;
|
|
|
gcc_assert (TREE_CODE (var) != SSA_NAME);
|
gcc_assert (TREE_CODE (var) != SSA_NAME);
|
|
|
ann = var_ann (var);
|
ann = var_ann (var);
|
ann->out_of_ssa_tag = 1;
|
ann->out_of_ssa_tag = 1;
|
VAR_ANN_PARTITION (ann) = part;
|
VAR_ANN_PARTITION (ann) = part;
|
if (map->compact_to_partition)
|
if (map->compact_to_partition)
|
map->partition_to_var[map->compact_to_partition[part]] = var;
|
map->partition_to_var[map->compact_to_partition[part]] = var;
|
}
|
}
|
|
|
static inline void mark_all_vars_used (tree *);
|
static inline void mark_all_vars_used (tree *);
|
|
|
/* Helper function for mark_all_vars_used, called via walk_tree. */
|
/* Helper function for mark_all_vars_used, called via walk_tree. */
|
|
|
static tree
|
static tree
|
mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
|
mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
|
void *data ATTRIBUTE_UNUSED)
|
void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
tree t = *tp;
|
tree t = *tp;
|
|
|
if (TREE_CODE (t) == SSA_NAME)
|
if (TREE_CODE (t) == SSA_NAME)
|
t = SSA_NAME_VAR (t);
|
t = SSA_NAME_VAR (t);
|
|
|
/* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
|
/* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
|
fields that do not contain vars. */
|
fields that do not contain vars. */
|
if (TREE_CODE (t) == TARGET_MEM_REF)
|
if (TREE_CODE (t) == TARGET_MEM_REF)
|
{
|
{
|
mark_all_vars_used (&TMR_SYMBOL (t));
|
mark_all_vars_used (&TMR_SYMBOL (t));
|
mark_all_vars_used (&TMR_BASE (t));
|
mark_all_vars_used (&TMR_BASE (t));
|
mark_all_vars_used (&TMR_INDEX (t));
|
mark_all_vars_used (&TMR_INDEX (t));
|
*walk_subtrees = 0;
|
*walk_subtrees = 0;
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Only need to mark VAR_DECLS; parameters and return results are not
|
/* Only need to mark VAR_DECLS; parameters and return results are not
|
eliminated as unused. */
|
eliminated as unused. */
|
if (TREE_CODE (t) == VAR_DECL)
|
if (TREE_CODE (t) == VAR_DECL)
|
set_is_used (t);
|
set_is_used (t);
|
|
|
if (IS_TYPE_OR_DECL_P (t))
|
if (IS_TYPE_OR_DECL_P (t))
|
*walk_subtrees = 0;
|
*walk_subtrees = 0;
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
|
/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
|
eliminated during the tree->rtl conversion process. */
|
eliminated during the tree->rtl conversion process. */
|
|
|
static inline void
|
static inline void
|
mark_all_vars_used (tree *expr_p)
|
mark_all_vars_used (tree *expr_p)
|
{
|
{
|
walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
|
walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
|
}
|
}
|
|
|
|
|
/* Remove local variables that are not referenced in the IL. */
|
/* Remove local variables that are not referenced in the IL. */
|
|
|
void
|
void
|
remove_unused_locals (void)
|
remove_unused_locals (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
tree t, *cell;
|
tree t, *cell;
|
|
|
/* Assume all locals are unused. */
|
/* Assume all locals are unused. */
|
for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
|
for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
|
{
|
{
|
tree var = TREE_VALUE (t);
|
tree var = TREE_VALUE (t);
|
if (TREE_CODE (var) != FUNCTION_DECL
|
if (TREE_CODE (var) != FUNCTION_DECL
|
&& var_ann (var))
|
&& var_ann (var))
|
var_ann (var)->used = false;
|
var_ann (var)->used = false;
|
}
|
}
|
|
|
/* Walk the CFG marking all referenced symbols. */
|
/* Walk the CFG marking all referenced symbols. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
tree phi, def;
|
tree phi, def;
|
|
|
/* Walk the statements. */
|
/* Walk the statements. */
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
mark_all_vars_used (bsi_stmt_ptr (bsi));
|
mark_all_vars_used (bsi_stmt_ptr (bsi));
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
use_operand_p arg_p;
|
use_operand_p arg_p;
|
ssa_op_iter i;
|
ssa_op_iter i;
|
|
|
/* No point processing globals. */
|
/* No point processing globals. */
|
if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
|
if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
|
continue;
|
continue;
|
|
|
def = PHI_RESULT (phi);
|
def = PHI_RESULT (phi);
|
mark_all_vars_used (&def);
|
mark_all_vars_used (&def);
|
|
|
FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
|
FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
|
{
|
{
|
tree arg = USE_FROM_PTR (arg_p);
|
tree arg = USE_FROM_PTR (arg_p);
|
mark_all_vars_used (&arg);
|
mark_all_vars_used (&arg);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Remove unmarked vars and clear used flag. */
|
/* Remove unmarked vars and clear used flag. */
|
for (cell = &cfun->unexpanded_var_list; *cell; )
|
for (cell = &cfun->unexpanded_var_list; *cell; )
|
{
|
{
|
tree var = TREE_VALUE (*cell);
|
tree var = TREE_VALUE (*cell);
|
var_ann_t ann;
|
var_ann_t ann;
|
|
|
if (TREE_CODE (var) != FUNCTION_DECL
|
if (TREE_CODE (var) != FUNCTION_DECL
|
&& (!(ann = var_ann (var))
|
&& (!(ann = var_ann (var))
|
|| !ann->used))
|
|| !ann->used))
|
{
|
{
|
*cell = TREE_CHAIN (*cell);
|
*cell = TREE_CHAIN (*cell);
|
continue;
|
continue;
|
}
|
}
|
|
|
cell = &TREE_CHAIN (*cell);
|
cell = &TREE_CHAIN (*cell);
|
}
|
}
|
}
|
}
|
|
|
/* This function looks through the program and uses FLAGS to determine what
|
/* This function looks through the program and uses FLAGS to determine what
|
SSA versioned variables are given entries in a new partition table. This
|
SSA versioned variables are given entries in a new partition table. This
|
new partition map is returned. */
|
new partition map is returned. */
|
|
|
var_map
|
var_map
|
create_ssa_var_map (int flags)
|
create_ssa_var_map (int flags)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
basic_block bb;
|
basic_block bb;
|
tree dest, use;
|
tree dest, use;
|
tree stmt;
|
tree stmt;
|
var_map map;
|
var_map map;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
bitmap used_in_real_ops;
|
bitmap used_in_real_ops;
|
bitmap used_in_virtual_ops;
|
bitmap used_in_virtual_ops;
|
#endif
|
#endif
|
|
|
map = init_var_map (num_ssa_names + 1);
|
map = init_var_map (num_ssa_names + 1);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
used_in_real_ops = BITMAP_ALLOC (NULL);
|
used_in_real_ops = BITMAP_ALLOC (NULL);
|
used_in_virtual_ops = BITMAP_ALLOC (NULL);
|
used_in_virtual_ops = BITMAP_ALLOC (NULL);
|
#endif
|
#endif
|
|
|
if (flags & SSA_VAR_MAP_REF_COUNT)
|
if (flags & SSA_VAR_MAP_REF_COUNT)
|
{
|
{
|
map->ref_count
|
map->ref_count
|
= (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
|
= (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
|
memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
|
memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
|
}
|
}
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
tree phi, arg;
|
tree phi, arg;
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
int i;
|
int i;
|
register_ssa_partition (map, PHI_RESULT (phi), false);
|
register_ssa_partition (map, PHI_RESULT (phi), false);
|
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
|
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
|
{
|
{
|
arg = PHI_ARG_DEF (phi, i);
|
arg = PHI_ARG_DEF (phi, i);
|
if (TREE_CODE (arg) == SSA_NAME)
|
if (TREE_CODE (arg) == SSA_NAME)
|
register_ssa_partition (map, arg, true);
|
register_ssa_partition (map, arg, true);
|
|
|
mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
|
mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
|
}
|
}
|
}
|
}
|
|
|
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);
|
|
|
/* Register USE and DEF operands in each statement. */
|
/* Register USE and DEF operands in each statement. */
|
FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
|
{
|
{
|
register_ssa_partition (map, use, true);
|
register_ssa_partition (map, use, true);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
|
bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
|
#endif
|
#endif
|
}
|
}
|
|
|
FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
|
FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
|
{
|
{
|
register_ssa_partition (map, dest, false);
|
register_ssa_partition (map, dest, false);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
|
bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
|
#endif
|
#endif
|
}
|
}
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
/* Validate that virtual ops don't get used in funny ways. */
|
/* Validate that virtual ops don't get used in funny ways. */
|
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
|
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
|
SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
|
SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
|
{
|
{
|
bitmap_set_bit (used_in_virtual_ops,
|
bitmap_set_bit (used_in_virtual_ops,
|
DECL_UID (SSA_NAME_VAR (use)));
|
DECL_UID (SSA_NAME_VAR (use)));
|
}
|
}
|
|
|
#endif /* ENABLE_CHECKING */
|
#endif /* ENABLE_CHECKING */
|
|
|
mark_all_vars_used (bsi_stmt_ptr (bsi));
|
mark_all_vars_used (bsi_stmt_ptr (bsi));
|
}
|
}
|
}
|
}
|
|
|
#if defined ENABLE_CHECKING
|
#if defined ENABLE_CHECKING
|
{
|
{
|
unsigned i;
|
unsigned i;
|
bitmap both = BITMAP_ALLOC (NULL);
|
bitmap both = BITMAP_ALLOC (NULL);
|
bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
|
bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
|
if (!bitmap_empty_p (both))
|
if (!bitmap_empty_p (both))
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
|
fprintf (stderr, "Variable %s used in real and virtual operands\n",
|
fprintf (stderr, "Variable %s used in real and virtual operands\n",
|
get_name (referenced_var (i)));
|
get_name (referenced_var (i)));
|
internal_error ("SSA corruption");
|
internal_error ("SSA corruption");
|
}
|
}
|
|
|
BITMAP_FREE (used_in_real_ops);
|
BITMAP_FREE (used_in_real_ops);
|
BITMAP_FREE (used_in_virtual_ops);
|
BITMAP_FREE (used_in_virtual_ops);
|
BITMAP_FREE (both);
|
BITMAP_FREE (both);
|
}
|
}
|
#endif
|
#endif
|
|
|
return map;
|
return map;
|
}
|
}
|
|
|
|
|
/* Allocate and return a new live range information object base on MAP. */
|
/* Allocate and return a new live range information object base on MAP. */
|
|
|
static tree_live_info_p
|
static tree_live_info_p
|
new_tree_live_info (var_map map)
|
new_tree_live_info (var_map map)
|
{
|
{
|
tree_live_info_p live;
|
tree_live_info_p live;
|
unsigned x;
|
unsigned x;
|
|
|
live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
|
live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
|
live->map = map;
|
live->map = map;
|
live->num_blocks = last_basic_block;
|
live->num_blocks = last_basic_block;
|
|
|
live->global = BITMAP_ALLOC (NULL);
|
live->global = BITMAP_ALLOC (NULL);
|
|
|
live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
|
live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
|
for (x = 0; x < num_var_partitions (map); x++)
|
for (x = 0; x < num_var_partitions (map); x++)
|
live->livein[x] = BITMAP_ALLOC (NULL);
|
live->livein[x] = BITMAP_ALLOC (NULL);
|
|
|
/* liveout is deferred until it is actually requested. */
|
/* liveout is deferred until it is actually requested. */
|
live->liveout = NULL;
|
live->liveout = NULL;
|
return live;
|
return live;
|
}
|
}
|
|
|
|
|
/* Free storage for live range info object LIVE. */
|
/* Free storage for live range info object LIVE. */
|
|
|
void
|
void
|
delete_tree_live_info (tree_live_info_p live)
|
delete_tree_live_info (tree_live_info_p live)
|
{
|
{
|
int x;
|
int x;
|
if (live->liveout)
|
if (live->liveout)
|
{
|
{
|
for (x = live->num_blocks - 1; x >= 0; x--)
|
for (x = live->num_blocks - 1; x >= 0; x--)
|
BITMAP_FREE (live->liveout[x]);
|
BITMAP_FREE (live->liveout[x]);
|
free (live->liveout);
|
free (live->liveout);
|
}
|
}
|
if (live->livein)
|
if (live->livein)
|
{
|
{
|
for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
|
for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
|
BITMAP_FREE (live->livein[x]);
|
BITMAP_FREE (live->livein[x]);
|
free (live->livein);
|
free (live->livein);
|
}
|
}
|
if (live->global)
|
if (live->global)
|
BITMAP_FREE (live->global);
|
BITMAP_FREE (live->global);
|
|
|
free (live);
|
free (live);
|
}
|
}
|
|
|
|
|
/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
|
/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
|
for partition I. STACK is a varray used for temporary memory which is
|
for partition I. STACK is a varray used for temporary memory which is
|
passed in rather than being allocated on every call. */
|
passed in rather than being allocated on every call. */
|
|
|
static void
|
static void
|
live_worklist (tree_live_info_p live, int *stack, int i)
|
live_worklist (tree_live_info_p live, int *stack, int i)
|
{
|
{
|
unsigned b;
|
unsigned b;
|
tree var;
|
tree var;
|
basic_block def_bb = NULL;
|
basic_block def_bb = NULL;
|
edge e;
|
edge e;
|
var_map map = live->map;
|
var_map map = live->map;
|
edge_iterator ei;
|
edge_iterator ei;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
int *tos = stack;
|
int *tos = stack;
|
|
|
var = partition_to_var (map, i);
|
var = partition_to_var (map, i);
|
if (SSA_NAME_DEF_STMT (var))
|
if (SSA_NAME_DEF_STMT (var))
|
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
|
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
|
|
|
EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
|
EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
|
{
|
{
|
*tos++ = b;
|
*tos++ = b;
|
}
|
}
|
|
|
while (tos != stack)
|
while (tos != stack)
|
{
|
{
|
b = *--tos;
|
b = *--tos;
|
|
|
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
|
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
|
if (e->src != ENTRY_BLOCK_PTR)
|
if (e->src != ENTRY_BLOCK_PTR)
|
{
|
{
|
/* Its not live on entry to the block its defined in. */
|
/* Its not live on entry to the block its defined in. */
|
if (e->src == def_bb)
|
if (e->src == def_bb)
|
continue;
|
continue;
|
if (!bitmap_bit_p (live->livein[i], e->src->index))
|
if (!bitmap_bit_p (live->livein[i], e->src->index))
|
{
|
{
|
bitmap_set_bit (live->livein[i], e->src->index);
|
bitmap_set_bit (live->livein[i], e->src->index);
|
*tos++ = e->src->index;
|
*tos++ = e->src->index;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
|
/* If VAR is in a partition of MAP, set the bit for that partition in VEC. */
|
|
|
static inline void
|
static inline void
|
set_if_valid (var_map map, bitmap vec, tree var)
|
set_if_valid (var_map map, bitmap vec, tree var)
|
{
|
{
|
int p = var_to_partition (map, var);
|
int p = var_to_partition (map, var);
|
if (p != NO_PARTITION)
|
if (p != NO_PARTITION)
|
bitmap_set_bit (vec, p);
|
bitmap_set_bit (vec, p);
|
}
|
}
|
|
|
|
|
/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
|
/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and
|
global bit for it in the LIVE object. BB is the block being processed. */
|
global bit for it in the LIVE object. BB is the block being processed. */
|
|
|
static inline void
|
static inline void
|
add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
|
add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
|
tree var, basic_block bb)
|
tree var, basic_block bb)
|
{
|
{
|
int p = var_to_partition (live->map, var);
|
int p = var_to_partition (live->map, var);
|
if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
|
if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
|
return;
|
return;
|
if (!bitmap_bit_p (def_vec, p))
|
if (!bitmap_bit_p (def_vec, p))
|
{
|
{
|
bitmap_set_bit (live->livein[p], bb->index);
|
bitmap_set_bit (live->livein[p], bb->index);
|
bitmap_set_bit (live->global, p);
|
bitmap_set_bit (live->global, p);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Given partition map MAP, calculate all the live on entry bitmaps for
|
/* Given partition map MAP, calculate all the live on entry bitmaps for
|
each basic block. Return a live info object. */
|
each basic block. Return a live info object. */
|
|
|
tree_live_info_p
|
tree_live_info_p
|
calculate_live_on_entry (var_map map)
|
calculate_live_on_entry (var_map map)
|
{
|
{
|
tree_live_info_p live;
|
tree_live_info_p live;
|
unsigned i;
|
unsigned i;
|
basic_block bb;
|
basic_block bb;
|
bitmap saw_def;
|
bitmap saw_def;
|
tree phi, var, stmt;
|
tree phi, var, stmt;
|
tree op;
|
tree op;
|
edge e;
|
edge e;
|
int *stack;
|
int *stack;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
int num;
|
int num;
|
edge_iterator ei;
|
edge_iterator ei;
|
#endif
|
#endif
|
|
|
saw_def = BITMAP_ALLOC (NULL);
|
saw_def = BITMAP_ALLOC (NULL);
|
|
|
live = new_tree_live_info (map);
|
live = new_tree_live_info (map);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
bitmap_clear (saw_def);
|
bitmap_clear (saw_def);
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
|
for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
|
{
|
{
|
var = PHI_ARG_DEF (phi, i);
|
var = PHI_ARG_DEF (phi, i);
|
if (!phi_ssa_name_p (var))
|
if (!phi_ssa_name_p (var))
|
continue;
|
continue;
|
stmt = SSA_NAME_DEF_STMT (var);
|
stmt = SSA_NAME_DEF_STMT (var);
|
e = EDGE_PRED (bb, i);
|
e = EDGE_PRED (bb, i);
|
|
|
/* Any uses in PHIs which either don't have def's or are not
|
/* Any uses in PHIs which either don't have def's or are not
|
defined in the block from which the def comes, will be live
|
defined in the block from which the def comes, will be live
|
on entry to that block. */
|
on entry to that block. */
|
if (!stmt || e->src != bb_for_stmt (stmt))
|
if (!stmt || e->src != bb_for_stmt (stmt))
|
add_livein_if_notdef (live, saw_def, var, e->src);
|
add_livein_if_notdef (live, saw_def, var, e->src);
|
}
|
}
|
}
|
}
|
|
|
/* Don't mark PHI results as defined until all the PHI nodes have
|
/* Don't mark PHI results as defined until all the PHI nodes have
|
been processed. If the PHI sequence is:
|
been processed. If the PHI sequence is:
|
a_3 = PHI <a_1, a_2>
|
a_3 = PHI <a_1, a_2>
|
b_3 = PHI <b_1, a_3>
|
b_3 = PHI <b_1, a_3>
|
The a_3 referred to in b_3's PHI node is the one incoming on the
|
The a_3 referred to in b_3's PHI node is the one incoming on the
|
edge, *not* the PHI node just seen. */
|
edge, *not* the PHI node just seen. */
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
var = PHI_RESULT (phi);
|
var = PHI_RESULT (phi);
|
set_if_valid (map, saw_def, var);
|
set_if_valid (map, saw_def, var);
|
}
|
}
|
|
|
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);
|
|
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
|
{
|
{
|
add_livein_if_notdef (live, saw_def, op, bb);
|
add_livein_if_notdef (live, saw_def, op, bb);
|
}
|
}
|
|
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
|
{
|
{
|
set_if_valid (map, saw_def, op);
|
set_if_valid (map, saw_def, op);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
stack = XNEWVEC (int, last_basic_block);
|
stack = XNEWVEC (int, last_basic_block);
|
EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
|
{
|
{
|
live_worklist (live, stack, i);
|
live_worklist (live, stack, i);
|
}
|
}
|
free (stack);
|
free (stack);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
/* Check for live on entry partitions and report those with a DEF in
|
/* Check for live on entry partitions and report those with a DEF in
|
the program. This will typically mean an optimization has done
|
the program. This will typically mean an optimization has done
|
something wrong. */
|
something wrong. */
|
|
|
bb = ENTRY_BLOCK_PTR;
|
bb = ENTRY_BLOCK_PTR;
|
num = 0;
|
num = 0;
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
int entry_block = e->dest->index;
|
int entry_block = e->dest->index;
|
if (e->dest == EXIT_BLOCK_PTR)
|
if (e->dest == EXIT_BLOCK_PTR)
|
continue;
|
continue;
|
for (i = 0; i < (unsigned)num_var_partitions (map); i++)
|
for (i = 0; i < (unsigned)num_var_partitions (map); i++)
|
{
|
{
|
basic_block tmp;
|
basic_block tmp;
|
tree d;
|
tree d;
|
var = partition_to_var (map, i);
|
var = partition_to_var (map, i);
|
stmt = SSA_NAME_DEF_STMT (var);
|
stmt = SSA_NAME_DEF_STMT (var);
|
tmp = bb_for_stmt (stmt);
|
tmp = bb_for_stmt (stmt);
|
d = default_def (SSA_NAME_VAR (var));
|
d = default_def (SSA_NAME_VAR (var));
|
|
|
if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
|
if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
|
{
|
{
|
if (!IS_EMPTY_STMT (stmt))
|
if (!IS_EMPTY_STMT (stmt))
|
{
|
{
|
num++;
|
num++;
|
print_generic_expr (stderr, var, TDF_SLIM);
|
print_generic_expr (stderr, var, TDF_SLIM);
|
fprintf (stderr, " is defined ");
|
fprintf (stderr, " is defined ");
|
if (tmp)
|
if (tmp)
|
fprintf (stderr, " in BB%d, ", tmp->index);
|
fprintf (stderr, " in BB%d, ", tmp->index);
|
fprintf (stderr, "by:\n");
|
fprintf (stderr, "by:\n");
|
print_generic_expr (stderr, stmt, TDF_SLIM);
|
print_generic_expr (stderr, stmt, TDF_SLIM);
|
fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
|
fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
|
entry_block);
|
entry_block);
|
fprintf (stderr, " So it appears to have multiple defs.\n");
|
fprintf (stderr, " So it appears to have multiple defs.\n");
|
}
|
}
|
else
|
else
|
{
|
{
|
if (d != var)
|
if (d != var)
|
{
|
{
|
num++;
|
num++;
|
print_generic_expr (stderr, var, TDF_SLIM);
|
print_generic_expr (stderr, var, TDF_SLIM);
|
fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
|
fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
|
if (d)
|
if (d)
|
{
|
{
|
fprintf (stderr, " but is not the default def of ");
|
fprintf (stderr, " but is not the default def of ");
|
print_generic_expr (stderr, d, TDF_SLIM);
|
print_generic_expr (stderr, d, TDF_SLIM);
|
fprintf (stderr, "\n");
|
fprintf (stderr, "\n");
|
}
|
}
|
else
|
else
|
fprintf (stderr, " and there is no default def.\n");
|
fprintf (stderr, " and there is no default def.\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
else
|
else
|
if (d == var)
|
if (d == var)
|
{
|
{
|
/* The only way this var shouldn't be marked live on entry is
|
/* The only way this var shouldn't be marked live on entry is
|
if it occurs in a PHI argument of the block. */
|
if it occurs in a PHI argument of the block. */
|
int z, ok = 0;
|
int z, ok = 0;
|
for (phi = phi_nodes (e->dest);
|
for (phi = phi_nodes (e->dest);
|
phi && !ok;
|
phi && !ok;
|
phi = PHI_CHAIN (phi))
|
phi = PHI_CHAIN (phi))
|
{
|
{
|
for (z = 0; z < PHI_NUM_ARGS (phi); z++)
|
for (z = 0; z < PHI_NUM_ARGS (phi); z++)
|
if (var == PHI_ARG_DEF (phi, z))
|
if (var == PHI_ARG_DEF (phi, z))
|
{
|
{
|
ok = 1;
|
ok = 1;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
if (ok)
|
if (ok)
|
continue;
|
continue;
|
num++;
|
num++;
|
print_generic_expr (stderr, var, TDF_SLIM);
|
print_generic_expr (stderr, var, TDF_SLIM);
|
fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
|
fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
|
entry_block);
|
entry_block);
|
fprintf (stderr, "but it is a default def so it should be.\n");
|
fprintf (stderr, "but it is a default def so it should be.\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
gcc_assert (num <= 0);
|
gcc_assert (num <= 0);
|
#endif
|
#endif
|
|
|
BITMAP_FREE (saw_def);
|
BITMAP_FREE (saw_def);
|
|
|
return live;
|
return live;
|
}
|
}
|
|
|
|
|
/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
|
/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
|
|
|
void
|
void
|
calculate_live_on_exit (tree_live_info_p liveinfo)
|
calculate_live_on_exit (tree_live_info_p liveinfo)
|
{
|
{
|
unsigned b;
|
unsigned b;
|
unsigned i, x;
|
unsigned i, x;
|
bitmap *on_exit;
|
bitmap *on_exit;
|
basic_block bb;
|
basic_block bb;
|
edge e;
|
edge e;
|
tree t, phi;
|
tree t, phi;
|
bitmap on_entry;
|
bitmap on_entry;
|
var_map map = liveinfo->map;
|
var_map map = liveinfo->map;
|
|
|
on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
|
on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
|
for (x = 0; x < (unsigned)last_basic_block; x++)
|
for (x = 0; x < (unsigned)last_basic_block; x++)
|
on_exit[x] = BITMAP_ALLOC (NULL);
|
on_exit[x] = BITMAP_ALLOC (NULL);
|
|
|
/* Set all the live-on-exit bits for uses in PHIs. */
|
/* Set all the live-on-exit bits for uses in PHIs. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
|
for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
|
{
|
{
|
t = PHI_ARG_DEF (phi, i);
|
t = PHI_ARG_DEF (phi, i);
|
e = PHI_ARG_EDGE (phi, i);
|
e = PHI_ARG_EDGE (phi, i);
|
if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
|
if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
|
continue;
|
continue;
|
set_if_valid (map, on_exit[e->src->index], t);
|
set_if_valid (map, on_exit[e->src->index], t);
|
}
|
}
|
}
|
}
|
|
|
/* Set live on exit for all predecessors of live on entry's. */
|
/* Set live on exit for all predecessors of live on entry's. */
|
for (i = 0; i < num_var_partitions (map); i++)
|
for (i = 0; i < num_var_partitions (map); i++)
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
on_entry = live_entry_blocks (liveinfo, i);
|
on_entry = live_entry_blocks (liveinfo, i);
|
EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
|
EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
|
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
|
if (e->src != ENTRY_BLOCK_PTR)
|
if (e->src != ENTRY_BLOCK_PTR)
|
bitmap_set_bit (on_exit[e->src->index], i);
|
bitmap_set_bit (on_exit[e->src->index], i);
|
}
|
}
|
}
|
}
|
|
|
liveinfo->liveout = on_exit;
|
liveinfo->liveout = on_exit;
|
}
|
}
|
|
|
|
|
/* Initialize a tree_partition_associator object using MAP. */
|
/* Initialize a tree_partition_associator object using MAP. */
|
|
|
static tpa_p
|
static tpa_p
|
tpa_init (var_map map)
|
tpa_init (var_map map)
|
{
|
{
|
tpa_p tpa;
|
tpa_p tpa;
|
int num_partitions = num_var_partitions (map);
|
int num_partitions = num_var_partitions (map);
|
int x;
|
int x;
|
|
|
if (num_partitions == 0)
|
if (num_partitions == 0)
|
return NULL;
|
return NULL;
|
|
|
tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
|
tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
|
tpa->num_trees = 0;
|
tpa->num_trees = 0;
|
tpa->uncompressed_num = -1;
|
tpa->uncompressed_num = -1;
|
tpa->map = map;
|
tpa->map = map;
|
tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
|
tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
|
memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
|
memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
|
|
|
tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
|
tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
|
memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
|
memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
|
|
|
x = MAX (40, (num_partitions / 20));
|
x = MAX (40, (num_partitions / 20));
|
tpa->trees = VEC_alloc (tree, heap, x);
|
tpa->trees = VEC_alloc (tree, heap, x);
|
tpa->first_partition = VEC_alloc (int, heap, x);
|
tpa->first_partition = VEC_alloc (int, heap, x);
|
|
|
return tpa;
|
return tpa;
|
|
|
}
|
}
|
|
|
|
|
/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
|
/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */
|
|
|
void
|
void
|
tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
|
tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
|
{
|
{
|
int i;
|
int i;
|
|
|
i = tpa_first_partition (tpa, tree_index);
|
i = tpa_first_partition (tpa, tree_index);
|
if (i == partition_index)
|
if (i == partition_index)
|
{
|
{
|
VEC_replace (int, tpa->first_partition, tree_index,
|
VEC_replace (int, tpa->first_partition, tree_index,
|
tpa->next_partition[i]);
|
tpa->next_partition[i]);
|
}
|
}
|
else
|
else
|
{
|
{
|
for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
|
for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
|
{
|
{
|
if (tpa->next_partition[i] == partition_index)
|
if (tpa->next_partition[i] == partition_index)
|
{
|
{
|
tpa->next_partition[i] = tpa->next_partition[partition_index];
|
tpa->next_partition[i] = tpa->next_partition[partition_index];
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Free the memory used by tree_partition_associator object TPA. */
|
/* Free the memory used by tree_partition_associator object TPA. */
|
|
|
void
|
void
|
tpa_delete (tpa_p tpa)
|
tpa_delete (tpa_p tpa)
|
{
|
{
|
if (!tpa)
|
if (!tpa)
|
return;
|
return;
|
|
|
VEC_free (tree, heap, tpa->trees);
|
VEC_free (tree, heap, tpa->trees);
|
VEC_free (int, heap, tpa->first_partition);
|
VEC_free (int, heap, tpa->first_partition);
|
free (tpa->partition_to_tree_map);
|
free (tpa->partition_to_tree_map);
|
free (tpa->next_partition);
|
free (tpa->next_partition);
|
free (tpa);
|
free (tpa);
|
}
|
}
|
|
|
|
|
/* This function will remove any tree entries from TPA which have only a single
|
/* This function will remove any tree entries from TPA which have only a single
|
element. This will help keep the size of the conflict graph down. The
|
element. This will help keep the size of the conflict graph down. The
|
function returns the number of remaining tree lists. */
|
function returns the number of remaining tree lists. */
|
|
|
int
|
int
|
tpa_compact (tpa_p tpa)
|
tpa_compact (tpa_p tpa)
|
{
|
{
|
int last, x, y, first, swap_i;
|
int last, x, y, first, swap_i;
|
tree swap_t;
|
tree swap_t;
|
|
|
/* Find the last list which has more than 1 partition. */
|
/* Find the last list which has more than 1 partition. */
|
for (last = tpa->num_trees - 1; last > 0; last--)
|
for (last = tpa->num_trees - 1; last > 0; last--)
|
{
|
{
|
first = tpa_first_partition (tpa, last);
|
first = tpa_first_partition (tpa, last);
|
if (tpa_next_partition (tpa, first) != NO_PARTITION)
|
if (tpa_next_partition (tpa, first) != NO_PARTITION)
|
break;
|
break;
|
}
|
}
|
|
|
x = 0;
|
x = 0;
|
while (x < last)
|
while (x < last)
|
{
|
{
|
first = tpa_first_partition (tpa, x);
|
first = tpa_first_partition (tpa, x);
|
|
|
/* If there is not more than one partition, swap with the current end
|
/* If there is not more than one partition, swap with the current end
|
of the tree list. */
|
of the tree list. */
|
if (tpa_next_partition (tpa, first) == NO_PARTITION)
|
if (tpa_next_partition (tpa, first) == NO_PARTITION)
|
{
|
{
|
swap_t = VEC_index (tree, tpa->trees, last);
|
swap_t = VEC_index (tree, tpa->trees, last);
|
swap_i = VEC_index (int, tpa->first_partition, last);
|
swap_i = VEC_index (int, tpa->first_partition, last);
|
|
|
/* Update the last entry. Since it is known to only have one
|
/* Update the last entry. Since it is known to only have one
|
partition, there is nothing else to update. */
|
partition, there is nothing else to update. */
|
VEC_replace (tree, tpa->trees, last,
|
VEC_replace (tree, tpa->trees, last,
|
VEC_index (tree, tpa->trees, x));
|
VEC_index (tree, tpa->trees, x));
|
VEC_replace (int, tpa->first_partition, last,
|
VEC_replace (int, tpa->first_partition, last,
|
VEC_index (int, tpa->first_partition, x));
|
VEC_index (int, tpa->first_partition, x));
|
tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
|
tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
|
|
|
/* Since this list is known to have more than one partition, update
|
/* Since this list is known to have more than one partition, update
|
the list owner entries. */
|
the list owner entries. */
|
VEC_replace (tree, tpa->trees, x, swap_t);
|
VEC_replace (tree, tpa->trees, x, swap_t);
|
VEC_replace (int, tpa->first_partition, x, swap_i);
|
VEC_replace (int, tpa->first_partition, x, swap_i);
|
for (y = tpa_first_partition (tpa, x);
|
for (y = tpa_first_partition (tpa, x);
|
y != NO_PARTITION;
|
y != NO_PARTITION;
|
y = tpa_next_partition (tpa, y))
|
y = tpa_next_partition (tpa, y))
|
tpa->partition_to_tree_map[y] = x;
|
tpa->partition_to_tree_map[y] = x;
|
|
|
/* Ensure last is a list with more than one partition. */
|
/* Ensure last is a list with more than one partition. */
|
last--;
|
last--;
|
for (; last > x; last--)
|
for (; last > x; last--)
|
{
|
{
|
first = tpa_first_partition (tpa, last);
|
first = tpa_first_partition (tpa, last);
|
if (tpa_next_partition (tpa, first) != NO_PARTITION)
|
if (tpa_next_partition (tpa, first) != NO_PARTITION)
|
break;
|
break;
|
}
|
}
|
}
|
}
|
x++;
|
x++;
|
}
|
}
|
|
|
first = tpa_first_partition (tpa, x);
|
first = tpa_first_partition (tpa, x);
|
if (tpa_next_partition (tpa, first) != NO_PARTITION)
|
if (tpa_next_partition (tpa, first) != NO_PARTITION)
|
x++;
|
x++;
|
tpa->uncompressed_num = tpa->num_trees;
|
tpa->uncompressed_num = tpa->num_trees;
|
tpa->num_trees = x;
|
tpa->num_trees = x;
|
return last;
|
return last;
|
}
|
}
|
|
|
|
|
/* Initialize a root_var object with SSA partitions from MAP which are based
|
/* Initialize a root_var object with SSA partitions from MAP which are based
|
on each root variable. */
|
on each root variable. */
|
|
|
root_var_p
|
root_var_p
|
root_var_init (var_map map)
|
root_var_init (var_map map)
|
{
|
{
|
root_var_p rv;
|
root_var_p rv;
|
int num_partitions = num_var_partitions (map);
|
int num_partitions = num_var_partitions (map);
|
int x, p;
|
int x, p;
|
tree t;
|
tree t;
|
var_ann_t ann;
|
var_ann_t ann;
|
sbitmap seen;
|
sbitmap seen;
|
|
|
rv = tpa_init (map);
|
rv = tpa_init (map);
|
if (!rv)
|
if (!rv)
|
return NULL;
|
return NULL;
|
|
|
seen = sbitmap_alloc (num_partitions);
|
seen = sbitmap_alloc (num_partitions);
|
sbitmap_zero (seen);
|
sbitmap_zero (seen);
|
|
|
/* Start at the end and work towards the front. This will provide a list
|
/* Start at the end and work towards the front. This will provide a list
|
that is ordered from smallest to largest. */
|
that is ordered from smallest to largest. */
|
for (x = num_partitions - 1; x >= 0; x--)
|
for (x = num_partitions - 1; x >= 0; x--)
|
{
|
{
|
t = partition_to_var (map, x);
|
t = partition_to_var (map, x);
|
|
|
/* The var map may not be compacted yet, so check for NULL. */
|
/* The var map may not be compacted yet, so check for NULL. */
|
if (!t)
|
if (!t)
|
continue;
|
continue;
|
|
|
p = var_to_partition (map, t);
|
p = var_to_partition (map, t);
|
|
|
gcc_assert (p != NO_PARTITION);
|
gcc_assert (p != NO_PARTITION);
|
|
|
/* Make sure we only put coalesced partitions into the list once. */
|
/* Make sure we only put coalesced partitions into the list once. */
|
if (TEST_BIT (seen, p))
|
if (TEST_BIT (seen, p))
|
continue;
|
continue;
|
SET_BIT (seen, p);
|
SET_BIT (seen, p);
|
if (TREE_CODE (t) == SSA_NAME)
|
if (TREE_CODE (t) == SSA_NAME)
|
t = SSA_NAME_VAR (t);
|
t = SSA_NAME_VAR (t);
|
ann = var_ann (t);
|
ann = var_ann (t);
|
if (ann->root_var_processed)
|
if (ann->root_var_processed)
|
{
|
{
|
rv->next_partition[p] = VEC_index (int, rv->first_partition,
|
rv->next_partition[p] = VEC_index (int, rv->first_partition,
|
VAR_ANN_ROOT_INDEX (ann));
|
VAR_ANN_ROOT_INDEX (ann));
|
VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p);
|
VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p);
|
}
|
}
|
else
|
else
|
{
|
{
|
ann->root_var_processed = 1;
|
ann->root_var_processed = 1;
|
VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
|
VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
|
VEC_safe_push (tree, heap, rv->trees, t);
|
VEC_safe_push (tree, heap, rv->trees, t);
|
VEC_safe_push (int, heap, rv->first_partition, p);
|
VEC_safe_push (int, heap, rv->first_partition, p);
|
}
|
}
|
rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
|
rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
|
}
|
}
|
|
|
/* Reset the out_of_ssa_tag flag on each variable for later use. */
|
/* Reset the out_of_ssa_tag flag on each variable for later use. */
|
for (x = 0; x < rv->num_trees; x++)
|
for (x = 0; x < rv->num_trees; x++)
|
{
|
{
|
t = VEC_index (tree, rv->trees, x);
|
t = VEC_index (tree, rv->trees, x);
|
var_ann (t)->root_var_processed = 0;
|
var_ann (t)->root_var_processed = 0;
|
}
|
}
|
|
|
sbitmap_free (seen);
|
sbitmap_free (seen);
|
return rv;
|
return rv;
|
}
|
}
|
|
|
|
|
/* Initialize a type_var structure which associates all the partitions in MAP
|
/* Initialize a type_var structure which associates all the partitions in MAP
|
of the same type to the type node's index. Volatiles are ignored. */
|
of the same type to the type node's index. Volatiles are ignored. */
|
|
|
type_var_p
|
type_var_p
|
type_var_init (var_map map)
|
type_var_init (var_map map)
|
{
|
{
|
type_var_p tv;
|
type_var_p tv;
|
int x, y, p;
|
int x, y, p;
|
int num_partitions = num_var_partitions (map);
|
int num_partitions = num_var_partitions (map);
|
tree t;
|
tree t;
|
sbitmap seen;
|
sbitmap seen;
|
|
|
tv = tpa_init (map);
|
tv = tpa_init (map);
|
if (!tv)
|
if (!tv)
|
return NULL;
|
return NULL;
|
|
|
seen = sbitmap_alloc (num_partitions);
|
seen = sbitmap_alloc (num_partitions);
|
sbitmap_zero (seen);
|
sbitmap_zero (seen);
|
|
|
for (x = num_partitions - 1; x >= 0; x--)
|
for (x = num_partitions - 1; x >= 0; x--)
|
{
|
{
|
t = partition_to_var (map, x);
|
t = partition_to_var (map, x);
|
|
|
/* Disallow coalescing of these types of variables. */
|
/* Disallow coalescing of these types of variables. */
|
if (!t
|
if (!t
|
|| TREE_THIS_VOLATILE (t)
|
|| TREE_THIS_VOLATILE (t)
|
|| TREE_CODE (t) == RESULT_DECL
|
|| TREE_CODE (t) == RESULT_DECL
|
|| TREE_CODE (t) == PARM_DECL
|
|| TREE_CODE (t) == PARM_DECL
|
|| (DECL_P (t)
|
|| (DECL_P (t)
|
&& (DECL_REGISTER (t)
|
&& (DECL_REGISTER (t)
|
|| !DECL_IGNORED_P (t)
|
|| !DECL_IGNORED_P (t)
|
|| DECL_RTL_SET_P (t))))
|
|| DECL_RTL_SET_P (t))))
|
continue;
|
continue;
|
|
|
p = var_to_partition (map, t);
|
p = var_to_partition (map, t);
|
|
|
gcc_assert (p != NO_PARTITION);
|
gcc_assert (p != NO_PARTITION);
|
|
|
/* If partitions have been coalesced, only add the representative
|
/* If partitions have been coalesced, only add the representative
|
for the partition to the list once. */
|
for the partition to the list once. */
|
if (TEST_BIT (seen, p))
|
if (TEST_BIT (seen, p))
|
continue;
|
continue;
|
SET_BIT (seen, p);
|
SET_BIT (seen, p);
|
t = TREE_TYPE (t);
|
t = TREE_TYPE (t);
|
|
|
/* Find the list for this type. */
|
/* Find the list for this type. */
|
for (y = 0; y < tv->num_trees; y++)
|
for (y = 0; y < tv->num_trees; y++)
|
if (t == VEC_index (tree, tv->trees, y))
|
if (t == VEC_index (tree, tv->trees, y))
|
break;
|
break;
|
if (y == tv->num_trees)
|
if (y == tv->num_trees)
|
{
|
{
|
tv->num_trees++;
|
tv->num_trees++;
|
VEC_safe_push (tree, heap, tv->trees, t);
|
VEC_safe_push (tree, heap, tv->trees, t);
|
VEC_safe_push (int, heap, tv->first_partition, p);
|
VEC_safe_push (int, heap, tv->first_partition, p);
|
}
|
}
|
else
|
else
|
{
|
{
|
tv->next_partition[p] = VEC_index (int, tv->first_partition, y);
|
tv->next_partition[p] = VEC_index (int, tv->first_partition, y);
|
VEC_replace (int, tv->first_partition, y, p);
|
VEC_replace (int, tv->first_partition, y, p);
|
}
|
}
|
tv->partition_to_tree_map[p] = y;
|
tv->partition_to_tree_map[p] = y;
|
}
|
}
|
sbitmap_free (seen);
|
sbitmap_free (seen);
|
return tv;
|
return tv;
|
}
|
}
|
|
|
|
|
/* Create a new coalesce list object from MAP and return it. */
|
/* Create a new coalesce list object from MAP and return it. */
|
|
|
coalesce_list_p
|
coalesce_list_p
|
create_coalesce_list (var_map map)
|
create_coalesce_list (var_map map)
|
{
|
{
|
coalesce_list_p list;
|
coalesce_list_p list;
|
|
|
list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
|
list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
|
|
|
list->map = map;
|
list->map = map;
|
list->add_mode = true;
|
list->add_mode = true;
|
list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
|
list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
|
sizeof (struct partition_pair_d));
|
sizeof (struct partition_pair_d));
|
return list;
|
return list;
|
}
|
}
|
|
|
|
|
/* Delete coalesce list CL. */
|
/* Delete coalesce list CL. */
|
|
|
void
|
void
|
delete_coalesce_list (coalesce_list_p cl)
|
delete_coalesce_list (coalesce_list_p cl)
|
{
|
{
|
free (cl->list);
|
free (cl->list);
|
free (cl);
|
free (cl);
|
}
|
}
|
|
|
|
|
/* Find a matching coalesce pair object in CL for partitions P1 and P2. If
|
/* Find a matching coalesce pair object in CL for partitions P1 and P2. If
|
one isn't found, return NULL if CREATE is false, otherwise create a new
|
one isn't found, return NULL if CREATE is false, otherwise create a new
|
coalesce pair object and return it. */
|
coalesce pair object and return it. */
|
|
|
static partition_pair_p
|
static partition_pair_p
|
find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
|
find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
|
{
|
{
|
partition_pair_p node, tmp;
|
partition_pair_p node, tmp;
|
int s;
|
int s;
|
|
|
/* Normalize so that p1 is the smaller value. */
|
/* Normalize so that p1 is the smaller value. */
|
if (p2 < p1)
|
if (p2 < p1)
|
{
|
{
|
s = p1;
|
s = p1;
|
p1 = p2;
|
p1 = p2;
|
p2 = s;
|
p2 = s;
|
}
|
}
|
|
|
tmp = NULL;
|
tmp = NULL;
|
|
|
/* The list is sorted such that if we find a value greater than p2,
|
/* The list is sorted such that if we find a value greater than p2,
|
p2 is not in the list. */
|
p2 is not in the list. */
|
for (node = cl->list[p1]; node; node = node->next)
|
for (node = cl->list[p1]; node; node = node->next)
|
{
|
{
|
if (node->second_partition == p2)
|
if (node->second_partition == p2)
|
return node;
|
return node;
|
else
|
else
|
if (node->second_partition > p2)
|
if (node->second_partition > p2)
|
break;
|
break;
|
tmp = node;
|
tmp = node;
|
}
|
}
|
|
|
if (!create)
|
if (!create)
|
return NULL;
|
return NULL;
|
|
|
node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
|
node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
|
node->first_partition = p1;
|
node->first_partition = p1;
|
node->second_partition = p2;
|
node->second_partition = p2;
|
node->cost = 0;
|
node->cost = 0;
|
|
|
if (tmp != NULL)
|
if (tmp != NULL)
|
{
|
{
|
node->next = tmp->next;
|
node->next = tmp->next;
|
tmp->next = node;
|
tmp->next = node;
|
}
|
}
|
else
|
else
|
{
|
{
|
/* This is now the first node in the list. */
|
/* This is now the first node in the list. */
|
node->next = cl->list[p1];
|
node->next = cl->list[p1];
|
cl->list[p1] = node;
|
cl->list[p1] = node;
|
}
|
}
|
|
|
return node;
|
return node;
|
}
|
}
|
|
|
/* Return cost of execution of copy instruction with FREQUENCY
|
/* Return cost of execution of copy instruction with FREQUENCY
|
possibly on CRITICAL edge and in HOT basic block. */
|
possibly on CRITICAL edge and in HOT basic block. */
|
int
|
int
|
coalesce_cost (int frequency, bool hot, bool critical)
|
coalesce_cost (int frequency, bool hot, bool critical)
|
{
|
{
|
/* Base costs on BB frequencies bounded by 1. */
|
/* Base costs on BB frequencies bounded by 1. */
|
int cost = frequency;
|
int cost = frequency;
|
|
|
if (!cost)
|
if (!cost)
|
cost = 1;
|
cost = 1;
|
if (optimize_size || hot)
|
if (optimize_size || hot)
|
cost = 1;
|
cost = 1;
|
/* Inserting copy on critical edge costs more
|
/* Inserting copy on critical edge costs more
|
than inserting it elsewhere. */
|
than inserting it elsewhere. */
|
if (critical)
|
if (critical)
|
cost *= 2;
|
cost *= 2;
|
return cost;
|
return cost;
|
}
|
}
|
|
|
/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
|
/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
|
|
|
void
|
void
|
add_coalesce (coalesce_list_p cl, int p1, int p2,
|
add_coalesce (coalesce_list_p cl, int p1, int p2,
|
int value)
|
int value)
|
{
|
{
|
partition_pair_p node;
|
partition_pair_p node;
|
|
|
gcc_assert (cl->add_mode);
|
gcc_assert (cl->add_mode);
|
|
|
if (p1 == p2)
|
if (p1 == p2)
|
return;
|
return;
|
|
|
node = find_partition_pair (cl, p1, p2, true);
|
node = find_partition_pair (cl, p1, p2, true);
|
|
|
node->cost += value;
|
node->cost += value;
|
}
|
}
|
|
|
|
|
/* Comparison function to allow qsort to sort P1 and P2 in descending order. */
|
/* Comparison function to allow qsort to sort P1 and P2 in descending order. */
|
|
|
static
|
static
|
int compare_pairs (const void *p1, const void *p2)
|
int compare_pairs (const void *p1, const void *p2)
|
{
|
{
|
#if 0
|
#if 0
|
partition_pair_p * pp1 = (partition_pair_p *) p1;
|
partition_pair_p * pp1 = (partition_pair_p *) p1;
|
partition_pair_p * pp2 = (partition_pair_p *) p2;
|
partition_pair_p * pp2 = (partition_pair_p *) p2;
|
int result;
|
int result;
|
|
|
result = (* pp2)->cost - (* pp1)->cost;
|
result = (* pp2)->cost - (* pp1)->cost;
|
/* Issue 128204: Cygwin vs Linux host differences:
|
/* Issue 128204: Cygwin vs Linux host differences:
|
If the costs are the same, use the partition indicies in order to
|
If the costs are the same, use the partition indicies in order to
|
obtain a stable, reproducible sort. Otherwise the ordering will
|
obtain a stable, reproducible sort. Otherwise the ordering will
|
be at the mercy of the host's qsort library function implementation. */
|
be at the mercy of the host's qsort library function implementation. */
|
if (result == 0)
|
if (result == 0)
|
{
|
{
|
result = (* pp2)->first_partition - (* pp1)->first_partition;
|
result = (* pp2)->first_partition - (* pp1)->first_partition;
|
if (result == 0)
|
if (result == 0)
|
result = (* pp2)->second_partition - (* pp1)->second_partition;
|
result = (* pp2)->second_partition - (* pp1)->second_partition;
|
}
|
}
|
|
|
return result;
|
return result;
|
#else
|
#else
|
return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
|
return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
|
#endif
|
#endif
|
}
|
}
|
|
|
|
|
/* Prepare CL for removal of preferred pairs. When finished, list element
|
/* Prepare CL for removal of preferred pairs. When finished, list element
|
0 has all the coalesce pairs, sorted in order from most important coalesce
|
0 has all the coalesce pairs, sorted in order from most important coalesce
|
to least important. */
|
to least important. */
|
|
|
void
|
void
|
sort_coalesce_list (coalesce_list_p cl)
|
sort_coalesce_list (coalesce_list_p cl)
|
{
|
{
|
unsigned x, num, count;
|
unsigned x, num, count;
|
partition_pair_p chain, p;
|
partition_pair_p chain, p;
|
partition_pair_p *list;
|
partition_pair_p *list;
|
|
|
gcc_assert (cl->add_mode);
|
gcc_assert (cl->add_mode);
|
|
|
cl->add_mode = false;
|
cl->add_mode = false;
|
|
|
/* Compact the array of lists to a single list, and count the elements. */
|
/* Compact the array of lists to a single list, and count the elements. */
|
num = 0;
|
num = 0;
|
chain = NULL;
|
chain = NULL;
|
for (x = 0; x < num_var_partitions (cl->map); x++)
|
for (x = 0; x < num_var_partitions (cl->map); x++)
|
if (cl->list[x] != NULL)
|
if (cl->list[x] != NULL)
|
{
|
{
|
for (p = cl->list[x]; p->next != NULL; p = p->next)
|
for (p = cl->list[x]; p->next != NULL; p = p->next)
|
num++;
|
num++;
|
num++;
|
num++;
|
p->next = chain;
|
p->next = chain;
|
chain = cl->list[x];
|
chain = cl->list[x];
|
cl->list[x] = NULL;
|
cl->list[x] = NULL;
|
}
|
}
|
|
|
/* Only call qsort if there are more than 2 items. */
|
/* Only call qsort if there are more than 2 items. */
|
if (num > 2)
|
if (num > 2)
|
{
|
{
|
list = XNEWVEC (partition_pair_p, num);
|
list = XNEWVEC (partition_pair_p, num);
|
count = 0;
|
count = 0;
|
for (p = chain; p != NULL; p = p->next)
|
for (p = chain; p != NULL; p = p->next)
|
list[count++] = p;
|
list[count++] = p;
|
|
|
gcc_assert (count == num);
|
gcc_assert (count == num);
|
|
|
qsort (list, count, sizeof (partition_pair_p), compare_pairs);
|
qsort (list, count, sizeof (partition_pair_p), compare_pairs);
|
|
|
p = list[0];
|
p = list[0];
|
for (x = 1; x < num; x++)
|
for (x = 1; x < num; x++)
|
{
|
{
|
p->next = list[x];
|
p->next = list[x];
|
p = list[x];
|
p = list[x];
|
}
|
}
|
p->next = NULL;
|
p->next = NULL;
|
cl->list[0] = list[0];
|
cl->list[0] = list[0];
|
free (list);
|
free (list);
|
}
|
}
|
else
|
else
|
{
|
{
|
cl->list[0] = chain;
|
cl->list[0] = chain;
|
if (num == 2)
|
if (num == 2)
|
{
|
{
|
/* Simply swap the two elements if they are in the wrong order. */
|
/* Simply swap the two elements if they are in the wrong order. */
|
if (chain->cost < chain->next->cost)
|
if (chain->cost < chain->next->cost)
|
{
|
{
|
cl->list[0] = chain->next;
|
cl->list[0] = chain->next;
|
cl->list[0]->next = chain;
|
cl->list[0]->next = chain;
|
chain->next = NULL;
|
chain->next = NULL;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Retrieve the best remaining pair to coalesce from CL. Returns the 2
|
/* Retrieve the best remaining pair to coalesce from CL. Returns the 2
|
partitions via P1 and P2. Their calculated cost is returned by the function.
|
partitions via P1 and P2. Their calculated cost is returned by the function.
|
NO_BEST_COALESCE is returned if the coalesce list is empty. */
|
NO_BEST_COALESCE is returned if the coalesce list is empty. */
|
|
|
static int
|
static int
|
pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
|
pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
|
{
|
{
|
partition_pair_p node;
|
partition_pair_p node;
|
int ret;
|
int ret;
|
|
|
gcc_assert (!cl->add_mode);
|
gcc_assert (!cl->add_mode);
|
|
|
node = cl->list[0];
|
node = cl->list[0];
|
if (!node)
|
if (!node)
|
return NO_BEST_COALESCE;
|
return NO_BEST_COALESCE;
|
|
|
cl->list[0] = node->next;
|
cl->list[0] = node->next;
|
|
|
*p1 = node->first_partition;
|
*p1 = node->first_partition;
|
*p2 = node->second_partition;
|
*p2 = node->second_partition;
|
ret = node->cost;
|
ret = node->cost;
|
free (node);
|
free (node);
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
|
|
/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
|
/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between
|
VAR and any other live partitions in VEC which are associated via TPA.
|
VAR and any other live partitions in VEC which are associated via TPA.
|
Reset the live bit in VEC. */
|
Reset the live bit in VEC. */
|
|
|
static inline void
|
static inline void
|
add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
|
add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
|
var_map map, bitmap vec, tree var)
|
var_map map, bitmap vec, tree var)
|
{
|
{
|
int p, y, first;
|
int p, y, first;
|
p = var_to_partition (map, var);
|
p = var_to_partition (map, var);
|
if (p != NO_PARTITION)
|
if (p != NO_PARTITION)
|
{
|
{
|
bitmap_clear_bit (vec, p);
|
bitmap_clear_bit (vec, p);
|
first = tpa_find_tree (tpa, p);
|
first = tpa_find_tree (tpa, p);
|
/* If find returns nothing, this object isn't interesting. */
|
/* If find returns nothing, this object isn't interesting. */
|
if (first == TPA_NONE)
|
if (first == TPA_NONE)
|
return;
|
return;
|
/* Only add interferences between objects in the same list. */
|
/* Only add interferences between objects in the same list. */
|
for (y = tpa_first_partition (tpa, first);
|
for (y = tpa_first_partition (tpa, first);
|
y != TPA_NONE;
|
y != TPA_NONE;
|
y = tpa_next_partition (tpa, y))
|
y = tpa_next_partition (tpa, y))
|
{
|
{
|
if (bitmap_bit_p (vec, y))
|
if (bitmap_bit_p (vec, y))
|
conflict_graph_add (graph, p, y);
|
conflict_graph_add (graph, p, y);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Return a conflict graph for the information contained in LIVE_INFO. Only
|
/* Return a conflict graph for the information contained in LIVE_INFO. Only
|
conflicts between items in the same TPA list are added. If optional
|
conflicts between items in the same TPA list are added. If optional
|
coalesce list CL is passed in, any copies encountered are added. */
|
coalesce list CL is passed in, any copies encountered are added. */
|
|
|
conflict_graph
|
conflict_graph
|
build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
|
build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
|
coalesce_list_p cl)
|
coalesce_list_p cl)
|
{
|
{
|
conflict_graph graph;
|
conflict_graph graph;
|
var_map map;
|
var_map map;
|
bitmap live;
|
bitmap live;
|
unsigned x, y, i;
|
unsigned x, y, i;
|
basic_block bb;
|
basic_block bb;
|
int *partition_link, *tpa_nodes;
|
int *partition_link, *tpa_nodes;
|
VEC(int,heap) *tpa_to_clear;
|
VEC(int,heap) *tpa_to_clear;
|
unsigned l;
|
unsigned l;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
map = live_var_map (liveinfo);
|
map = live_var_map (liveinfo);
|
graph = conflict_graph_new (num_var_partitions (map));
|
graph = conflict_graph_new (num_var_partitions (map));
|
|
|
if (tpa_num_trees (tpa) == 0)
|
if (tpa_num_trees (tpa) == 0)
|
return graph;
|
return graph;
|
|
|
live = BITMAP_ALLOC (NULL);
|
live = BITMAP_ALLOC (NULL);
|
|
|
partition_link = XCNEWVEC (int, num_var_partitions (map) + 1);
|
partition_link = XCNEWVEC (int, num_var_partitions (map) + 1);
|
tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa));
|
tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa));
|
tpa_to_clear = VEC_alloc (int, heap, 50);
|
tpa_to_clear = VEC_alloc (int, heap, 50);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
tree phi;
|
tree phi;
|
int idx;
|
int idx;
|
|
|
/* Start with live on exit temporaries. */
|
/* Start with live on exit temporaries. */
|
bitmap_copy (live, live_on_exit (liveinfo, bb));
|
bitmap_copy (live, live_on_exit (liveinfo, bb));
|
|
|
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
|
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
|
{
|
{
|
bool is_a_copy = false;
|
bool is_a_copy = false;
|
tree stmt = bsi_stmt (bsi);
|
tree stmt = bsi_stmt (bsi);
|
|
|
/* A copy between 2 partitions does not introduce an interference
|
/* A copy between 2 partitions does not introduce an interference
|
by itself. If they did, you would never be able to coalesce
|
by itself. If they did, you would never be able to coalesce
|
two things which are copied. If the two variables really do
|
two things which are copied. If the two variables really do
|
conflict, they will conflict elsewhere in the program.
|
conflict, they will conflict elsewhere in the program.
|
|
|
This is handled specially here since we may also be interested
|
This is handled specially here since we may also be interested
|
in copies between real variables and SSA_NAME variables. We may
|
in copies between real variables and SSA_NAME variables. We may
|
be interested in trying to coalesce SSA_NAME variables with
|
be interested in trying to coalesce SSA_NAME variables with
|
root variables in some cases. */
|
root variables in some cases. */
|
|
|
if (TREE_CODE (stmt) == MODIFY_EXPR)
|
if (TREE_CODE (stmt) == MODIFY_EXPR)
|
{
|
{
|
tree lhs = TREE_OPERAND (stmt, 0);
|
tree lhs = TREE_OPERAND (stmt, 0);
|
tree rhs = TREE_OPERAND (stmt, 1);
|
tree rhs = TREE_OPERAND (stmt, 1);
|
int p1, p2;
|
int p1, p2;
|
int bit;
|
int bit;
|
|
|
if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
|
if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
|
p1 = var_to_partition (map, lhs);
|
p1 = var_to_partition (map, lhs);
|
else
|
else
|
p1 = NO_PARTITION;
|
p1 = NO_PARTITION;
|
|
|
if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
|
if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
|
p2 = var_to_partition (map, rhs);
|
p2 = var_to_partition (map, rhs);
|
else
|
else
|
p2 = NO_PARTITION;
|
p2 = NO_PARTITION;
|
|
|
if (p1 != NO_PARTITION && p2 != NO_PARTITION)
|
if (p1 != NO_PARTITION && p2 != NO_PARTITION)
|
{
|
{
|
is_a_copy = true;
|
is_a_copy = true;
|
bit = bitmap_bit_p (live, p2);
|
bit = bitmap_bit_p (live, p2);
|
/* If the RHS is live, make it not live while we add
|
/* If the RHS is live, make it not live while we add
|
the conflicts, then make it live again. */
|
the conflicts, then make it live again. */
|
if (bit)
|
if (bit)
|
bitmap_clear_bit (live, p2);
|
bitmap_clear_bit (live, p2);
|
add_conflicts_if_valid (tpa, graph, map, live, lhs);
|
add_conflicts_if_valid (tpa, graph, map, live, lhs);
|
if (bit)
|
if (bit)
|
bitmap_set_bit (live, p2);
|
bitmap_set_bit (live, p2);
|
if (cl)
|
if (cl)
|
add_coalesce (cl, p1, p2,
|
add_coalesce (cl, p1, p2,
|
coalesce_cost (bb->frequency,
|
coalesce_cost (bb->frequency,
|
maybe_hot_bb_p (bb), false));
|
maybe_hot_bb_p (bb), false));
|
set_if_valid (map, live, rhs);
|
set_if_valid (map, live, rhs);
|
}
|
}
|
}
|
}
|
|
|
if (!is_a_copy)
|
if (!is_a_copy)
|
{
|
{
|
tree var;
|
tree var;
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
|
{
|
{
|
add_conflicts_if_valid (tpa, graph, map, live, var);
|
add_conflicts_if_valid (tpa, graph, map, live, var);
|
}
|
}
|
|
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
|
{
|
{
|
set_if_valid (map, live, var);
|
set_if_valid (map, live, var);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* If result of a PHI is unused, then the loops over the statements
|
/* If result of a PHI is unused, then the loops over the statements
|
will not record any conflicts. However, since the PHI node is
|
will not record any conflicts. However, since the PHI node is
|
going to be translated out of SSA form we must record a conflict
|
going to be translated out of SSA form we must record a conflict
|
between the result of the PHI and any variables with are live.
|
between the result of the PHI and any variables with are live.
|
Otherwise the out-of-ssa translation may create incorrect code. */
|
Otherwise the out-of-ssa translation may create incorrect code. */
|
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);
|
int p = var_to_partition (map, result);
|
int p = var_to_partition (map, result);
|
|
|
if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
|
if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
|
add_conflicts_if_valid (tpa, graph, map, live, result);
|
add_conflicts_if_valid (tpa, graph, map, live, result);
|
}
|
}
|
|
|
/* Anything which is still live at this point interferes.
|
/* Anything which is still live at this point interferes.
|
In order to implement this efficiently, only conflicts between
|
In order to implement this efficiently, only conflicts between
|
partitions which have the same TPA root need be added.
|
partitions which have the same TPA root need be added.
|
TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
|
TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero
|
entry points to an index into 'partition_link', which then indexes
|
entry points to an index into 'partition_link', which then indexes
|
into itself forming a linked list of partitions sharing a tpa root
|
into itself forming a linked list of partitions sharing a tpa root
|
which have been seen as live up to this point. Since partitions start
|
which have been seen as live up to this point. Since partitions start
|
at index zero, all entries in partition_link are (partition + 1).
|
at index zero, all entries in partition_link are (partition + 1).
|
|
|
Conflicts are added between the current partition and any already seen.
|
Conflicts are added between the current partition and any already seen.
|
tpa_clear contains all the tpa_roots processed, and these are the only
|
tpa_clear contains all the tpa_roots processed, and these are the only
|
entries which need to be zero'd out for a clean restart. */
|
entries which need to be zero'd out for a clean restart. */
|
|
|
EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
|
EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
|
{
|
{
|
i = tpa_find_tree (tpa, x);
|
i = tpa_find_tree (tpa, x);
|
if (i != (unsigned)TPA_NONE)
|
if (i != (unsigned)TPA_NONE)
|
{
|
{
|
int start = tpa_nodes[i];
|
int start = tpa_nodes[i];
|
/* If start is 0, a new root reference list is being started.
|
/* If start is 0, a new root reference list is being started.
|
Register it to be cleared. */
|
Register it to be cleared. */
|
if (!start)
|
if (!start)
|
VEC_safe_push (int, heap, tpa_to_clear, i);
|
VEC_safe_push (int, heap, tpa_to_clear, i);
|
|
|
/* Add interferences to other tpa members seen. */
|
/* Add interferences to other tpa members seen. */
|
for (y = start; y != 0; y = partition_link[y])
|
for (y = start; y != 0; y = partition_link[y])
|
conflict_graph_add (graph, x, y - 1);
|
conflict_graph_add (graph, x, y - 1);
|
tpa_nodes[i] = x + 1;
|
tpa_nodes[i] = x + 1;
|
partition_link[x + 1] = start;
|
partition_link[x + 1] = start;
|
}
|
}
|
}
|
}
|
|
|
/* Now clear the used tpa root references. */
|
/* Now clear the used tpa root references. */
|
for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
|
for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
|
tpa_nodes[idx] = 0;
|
tpa_nodes[idx] = 0;
|
VEC_truncate (int, tpa_to_clear, 0);
|
VEC_truncate (int, tpa_to_clear, 0);
|
}
|
}
|
|
|
free (tpa_nodes);
|
free (tpa_nodes);
|
free (partition_link);
|
free (partition_link);
|
VEC_free (int, heap, tpa_to_clear);
|
VEC_free (int, heap, tpa_to_clear);
|
BITMAP_FREE (live);
|
BITMAP_FREE (live);
|
return graph;
|
return graph;
|
}
|
}
|
|
|
|
|
/* This routine will attempt to coalesce the elements in TPA subject to the
|
/* This routine will attempt to coalesce the elements in TPA subject to the
|
conflicts found in GRAPH. If optional coalesce_list CL is provided,
|
conflicts found in GRAPH. If optional coalesce_list CL is provided,
|
only coalesces specified within the coalesce list are attempted. Otherwise
|
only coalesces specified within the coalesce list are attempted. Otherwise
|
an attempt is made to coalesce as many partitions within each TPA grouping
|
an attempt is made to coalesce as many partitions within each TPA grouping
|
as possible. If DEBUG is provided, debug output will be sent there. */
|
as possible. If DEBUG is provided, debug output will be sent there. */
|
|
|
void
|
void
|
coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
|
coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
|
coalesce_list_p cl, FILE *debug)
|
coalesce_list_p cl, FILE *debug)
|
{
|
{
|
int x, y, z, w;
|
int x, y, z, w;
|
tree var, tmp;
|
tree var, tmp;
|
|
|
/* Attempt to coalesce any items in a coalesce list. */
|
/* Attempt to coalesce any items in a coalesce list. */
|
if (cl)
|
if (cl)
|
{
|
{
|
while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
|
while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
|
{
|
{
|
if (debug)
|
if (debug)
|
{
|
{
|
fprintf (debug, "Coalesce list: (%d)", x);
|
fprintf (debug, "Coalesce list: (%d)", x);
|
print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
|
print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
|
fprintf (debug, " & (%d)", y);
|
fprintf (debug, " & (%d)", y);
|
print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
|
print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
|
}
|
}
|
|
|
w = tpa_find_tree (tpa, x);
|
w = tpa_find_tree (tpa, x);
|
z = tpa_find_tree (tpa, y);
|
z = tpa_find_tree (tpa, y);
|
if (w != z || w == TPA_NONE || z == TPA_NONE)
|
if (w != z || w == TPA_NONE || z == TPA_NONE)
|
{
|
{
|
if (debug)
|
if (debug)
|
{
|
{
|
if (w != z)
|
if (w != z)
|
fprintf (debug, ": Fail, Non-matching TPA's\n");
|
fprintf (debug, ": Fail, Non-matching TPA's\n");
|
if (w == TPA_NONE)
|
if (w == TPA_NONE)
|
fprintf (debug, ": Fail %d non TPA.\n", x);
|
fprintf (debug, ": Fail %d non TPA.\n", x);
|
else
|
else
|
fprintf (debug, ": Fail %d non TPA.\n", y);
|
fprintf (debug, ": Fail %d non TPA.\n", y);
|
}
|
}
|
continue;
|
continue;
|
}
|
}
|
var = partition_to_var (map, x);
|
var = partition_to_var (map, x);
|
tmp = partition_to_var (map, y);
|
tmp = partition_to_var (map, y);
|
x = var_to_partition (map, var);
|
x = var_to_partition (map, var);
|
y = var_to_partition (map, tmp);
|
y = var_to_partition (map, tmp);
|
if (debug)
|
if (debug)
|
fprintf (debug, " [map: %d, %d] ", x, y);
|
fprintf (debug, " [map: %d, %d] ", x, y);
|
if (x == y)
|
if (x == y)
|
{
|
{
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Already Coalesced.\n");
|
fprintf (debug, ": Already Coalesced.\n");
|
continue;
|
continue;
|
}
|
}
|
if (!conflict_graph_conflict_p (graph, x, y))
|
if (!conflict_graph_conflict_p (graph, x, y))
|
{
|
{
|
z = var_union (map, var, tmp);
|
z = var_union (map, var, tmp);
|
if (z == NO_PARTITION)
|
if (z == NO_PARTITION)
|
{
|
{
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Unable to perform partition union.\n");
|
fprintf (debug, ": Unable to perform partition union.\n");
|
continue;
|
continue;
|
}
|
}
|
|
|
/* z is the new combined partition. We need to remove the other
|
/* z is the new combined partition. We need to remove the other
|
partition from the list. Set x to be that other partition. */
|
partition from the list. Set x to be that other partition. */
|
if (z == x)
|
if (z == x)
|
{
|
{
|
conflict_graph_merge_regs (graph, x, y);
|
conflict_graph_merge_regs (graph, x, y);
|
w = tpa_find_tree (tpa, y);
|
w = tpa_find_tree (tpa, y);
|
tpa_remove_partition (tpa, w, y);
|
tpa_remove_partition (tpa, w, y);
|
}
|
}
|
else
|
else
|
{
|
{
|
conflict_graph_merge_regs (graph, y, x);
|
conflict_graph_merge_regs (graph, y, x);
|
w = tpa_find_tree (tpa, x);
|
w = tpa_find_tree (tpa, x);
|
tpa_remove_partition (tpa, w, x);
|
tpa_remove_partition (tpa, w, x);
|
}
|
}
|
|
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Success -> %d\n", z);
|
fprintf (debug, ": Success -> %d\n", z);
|
}
|
}
|
else
|
else
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Fail due to conflict\n");
|
fprintf (debug, ": Fail due to conflict\n");
|
}
|
}
|
/* If using a coalesce list, don't try to coalesce anything else. */
|
/* If using a coalesce list, don't try to coalesce anything else. */
|
return;
|
return;
|
}
|
}
|
|
|
for (x = 0; x < tpa_num_trees (tpa); x++)
|
for (x = 0; x < tpa_num_trees (tpa); x++)
|
{
|
{
|
while (tpa_first_partition (tpa, x) != TPA_NONE)
|
while (tpa_first_partition (tpa, x) != TPA_NONE)
|
{
|
{
|
int p1, p2;
|
int p1, p2;
|
/* Coalesce first partition with anything that doesn't conflict. */
|
/* Coalesce first partition with anything that doesn't conflict. */
|
y = tpa_first_partition (tpa, x);
|
y = tpa_first_partition (tpa, x);
|
tpa_remove_partition (tpa, x, y);
|
tpa_remove_partition (tpa, x, y);
|
|
|
var = partition_to_var (map, y);
|
var = partition_to_var (map, y);
|
/* p1 is the partition representative to which y belongs. */
|
/* p1 is the partition representative to which y belongs. */
|
p1 = var_to_partition (map, var);
|
p1 = var_to_partition (map, var);
|
|
|
for (z = tpa_next_partition (tpa, y);
|
for (z = tpa_next_partition (tpa, y);
|
z != TPA_NONE;
|
z != TPA_NONE;
|
z = tpa_next_partition (tpa, z))
|
z = tpa_next_partition (tpa, z))
|
{
|
{
|
tmp = partition_to_var (map, z);
|
tmp = partition_to_var (map, z);
|
/* p2 is the partition representative to which z belongs. */
|
/* p2 is the partition representative to which z belongs. */
|
p2 = var_to_partition (map, tmp);
|
p2 = var_to_partition (map, tmp);
|
if (debug)
|
if (debug)
|
{
|
{
|
fprintf (debug, "Coalesce : ");
|
fprintf (debug, "Coalesce : ");
|
print_generic_expr (debug, var, TDF_SLIM);
|
print_generic_expr (debug, var, TDF_SLIM);
|
fprintf (debug, " &");
|
fprintf (debug, " &");
|
print_generic_expr (debug, tmp, TDF_SLIM);
|
print_generic_expr (debug, tmp, TDF_SLIM);
|
fprintf (debug, " (%d ,%d)", p1, p2);
|
fprintf (debug, " (%d ,%d)", p1, p2);
|
}
|
}
|
|
|
/* If partitions are already merged, don't check for conflict. */
|
/* If partitions are already merged, don't check for conflict. */
|
if (tmp == var)
|
if (tmp == var)
|
{
|
{
|
tpa_remove_partition (tpa, x, z);
|
tpa_remove_partition (tpa, x, z);
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Already coalesced\n");
|
fprintf (debug, ": Already coalesced\n");
|
}
|
}
|
else
|
else
|
if (!conflict_graph_conflict_p (graph, p1, p2))
|
if (!conflict_graph_conflict_p (graph, p1, p2))
|
{
|
{
|
int v;
|
int v;
|
if (tpa_find_tree (tpa, y) == TPA_NONE
|
if (tpa_find_tree (tpa, y) == TPA_NONE
|
|| tpa_find_tree (tpa, z) == TPA_NONE)
|
|| tpa_find_tree (tpa, z) == TPA_NONE)
|
{
|
{
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Fail non-TPA member\n");
|
fprintf (debug, ": Fail non-TPA member\n");
|
continue;
|
continue;
|
}
|
}
|
if ((v = var_union (map, var, tmp)) == NO_PARTITION)
|
if ((v = var_union (map, var, tmp)) == NO_PARTITION)
|
{
|
{
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Fail cannot combine partitions\n");
|
fprintf (debug, ": Fail cannot combine partitions\n");
|
continue;
|
continue;
|
}
|
}
|
|
|
tpa_remove_partition (tpa, x, z);
|
tpa_remove_partition (tpa, x, z);
|
if (v == p1)
|
if (v == p1)
|
conflict_graph_merge_regs (graph, v, z);
|
conflict_graph_merge_regs (graph, v, z);
|
else
|
else
|
{
|
{
|
/* Update the first partition's representative. */
|
/* Update the first partition's representative. */
|
conflict_graph_merge_regs (graph, v, y);
|
conflict_graph_merge_regs (graph, v, y);
|
p1 = v;
|
p1 = v;
|
}
|
}
|
|
|
/* The root variable of the partition may be changed
|
/* The root variable of the partition may be changed
|
now. */
|
now. */
|
var = partition_to_var (map, p1);
|
var = partition_to_var (map, p1);
|
|
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Success -> %d\n", v);
|
fprintf (debug, ": Success -> %d\n", v);
|
}
|
}
|
else
|
else
|
if (debug)
|
if (debug)
|
fprintf (debug, ": Fail, Conflict\n");
|
fprintf (debug, ": Fail, Conflict\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Send debug info for coalesce list CL to file F. */
|
/* Send debug info for coalesce list CL to file F. */
|
|
|
void
|
void
|
dump_coalesce_list (FILE *f, coalesce_list_p cl)
|
dump_coalesce_list (FILE *f, coalesce_list_p cl)
|
{
|
{
|
partition_pair_p node;
|
partition_pair_p node;
|
int x, num;
|
int x, num;
|
tree var;
|
tree var;
|
|
|
if (cl->add_mode)
|
if (cl->add_mode)
|
{
|
{
|
fprintf (f, "Coalesce List:\n");
|
fprintf (f, "Coalesce List:\n");
|
num = num_var_partitions (cl->map);
|
num = num_var_partitions (cl->map);
|
for (x = 0; x < num; x++)
|
for (x = 0; x < num; x++)
|
{
|
{
|
node = cl->list[x];
|
node = cl->list[x];
|
if (node)
|
if (node)
|
{
|
{
|
fprintf (f, "[");
|
fprintf (f, "[");
|
print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
|
print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
|
fprintf (f, "] - ");
|
fprintf (f, "] - ");
|
for ( ; node; node = node->next)
|
for ( ; node; node = node->next)
|
{
|
{
|
var = partition_to_var (cl->map, node->second_partition);
|
var = partition_to_var (cl->map, node->second_partition);
|
print_generic_expr (f, var, TDF_SLIM);
|
print_generic_expr (f, var, TDF_SLIM);
|
fprintf (f, "(%1d), ", node->cost);
|
fprintf (f, "(%1d), ", node->cost);
|
}
|
}
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
fprintf (f, "Sorted Coalesce list:\n");
|
fprintf (f, "Sorted Coalesce list:\n");
|
for (node = cl->list[0]; node; node = node->next)
|
for (node = cl->list[0]; node; node = node->next)
|
{
|
{
|
fprintf (f, "(%d) ", node->cost);
|
fprintf (f, "(%d) ", node->cost);
|
var = partition_to_var (cl->map, node->first_partition);
|
var = partition_to_var (cl->map, node->first_partition);
|
print_generic_expr (f, var, TDF_SLIM);
|
print_generic_expr (f, var, TDF_SLIM);
|
fprintf (f, " : ");
|
fprintf (f, " : ");
|
var = partition_to_var (cl->map, node->second_partition);
|
var = partition_to_var (cl->map, node->second_partition);
|
print_generic_expr (f, var, TDF_SLIM);
|
print_generic_expr (f, var, TDF_SLIM);
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Output tree_partition_associator object TPA to file F.. */
|
/* Output tree_partition_associator object TPA to file F.. */
|
|
|
void
|
void
|
tpa_dump (FILE *f, tpa_p tpa)
|
tpa_dump (FILE *f, tpa_p tpa)
|
{
|
{
|
int x, i;
|
int x, i;
|
|
|
if (!tpa)
|
if (!tpa)
|
return;
|
return;
|
|
|
for (x = 0; x < tpa_num_trees (tpa); x++)
|
for (x = 0; x < tpa_num_trees (tpa); x++)
|
{
|
{
|
print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
|
print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
|
fprintf (f, " : (");
|
fprintf (f, " : (");
|
for (i = tpa_first_partition (tpa, x);
|
for (i = tpa_first_partition (tpa, x);
|
i != TPA_NONE;
|
i != TPA_NONE;
|
i = tpa_next_partition (tpa, i))
|
i = tpa_next_partition (tpa, i))
|
{
|
{
|
fprintf (f, "(%d)",i);
|
fprintf (f, "(%d)",i);
|
print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
|
print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
|
fprintf (f, " ");
|
fprintf (f, " ");
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
if (tpa_find_tree (tpa, i) != x)
|
if (tpa_find_tree (tpa, i) != x)
|
fprintf (f, "**find tree incorrectly set** ");
|
fprintf (f, "**find tree incorrectly set** ");
|
#endif
|
#endif
|
|
|
}
|
}
|
fprintf (f, ")\n");
|
fprintf (f, ")\n");
|
}
|
}
|
fflush (f);
|
fflush (f);
|
}
|
}
|
|
|
|
|
/* Output partition map MAP to file F. */
|
/* Output partition map MAP to file F. */
|
|
|
void
|
void
|
dump_var_map (FILE *f, var_map map)
|
dump_var_map (FILE *f, var_map map)
|
{
|
{
|
int t;
|
int t;
|
unsigned x, y;
|
unsigned x, y;
|
int p;
|
int p;
|
|
|
fprintf (f, "\nPartition map \n\n");
|
fprintf (f, "\nPartition map \n\n");
|
|
|
for (x = 0; x < map->num_partitions; x++)
|
for (x = 0; x < map->num_partitions; x++)
|
{
|
{
|
if (map->compact_to_partition != NULL)
|
if (map->compact_to_partition != NULL)
|
p = map->compact_to_partition[x];
|
p = map->compact_to_partition[x];
|
else
|
else
|
p = x;
|
p = x;
|
|
|
if (map->partition_to_var[p] == NULL_TREE)
|
if (map->partition_to_var[p] == NULL_TREE)
|
continue;
|
continue;
|
|
|
t = 0;
|
t = 0;
|
for (y = 1; y < num_ssa_names; y++)
|
for (y = 1; y < num_ssa_names; y++)
|
{
|
{
|
p = partition_find (map->var_partition, y);
|
p = partition_find (map->var_partition, y);
|
if (map->partition_to_compact)
|
if (map->partition_to_compact)
|
p = map->partition_to_compact[p];
|
p = map->partition_to_compact[p];
|
if (p == (int)x)
|
if (p == (int)x)
|
{
|
{
|
if (t++ == 0)
|
if (t++ == 0)
|
{
|
{
|
fprintf(f, "Partition %d (", x);
|
fprintf(f, "Partition %d (", x);
|
print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
|
print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
|
fprintf (f, " - ");
|
fprintf (f, " - ");
|
}
|
}
|
fprintf (f, "%d ", y);
|
fprintf (f, "%d ", y);
|
}
|
}
|
}
|
}
|
if (t != 0)
|
if (t != 0)
|
fprintf (f, ")\n");
|
fprintf (f, ")\n");
|
}
|
}
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
}
|
}
|
|
|
|
|
/* Output live range info LIVE to file F, controlled by FLAG. */
|
/* Output live range info LIVE to file F, controlled by FLAG. */
|
|
|
void
|
void
|
dump_live_info (FILE *f, tree_live_info_p live, int flag)
|
dump_live_info (FILE *f, tree_live_info_p live, int flag)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
unsigned i;
|
unsigned i;
|
var_map map = live->map;
|
var_map map = live->map;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
if ((flag & LIVEDUMP_ENTRY) && live->livein)
|
if ((flag & LIVEDUMP_ENTRY) && live->livein)
|
{
|
{
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
fprintf (f, "\nLive on entry to BB%d : ", bb->index);
|
fprintf (f, "\nLive on entry to BB%d : ", bb->index);
|
for (i = 0; i < num_var_partitions (map); i++)
|
for (i = 0; i < num_var_partitions (map); i++)
|
{
|
{
|
if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
|
if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
|
{
|
{
|
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
|
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
|
fprintf (f, " ");
|
fprintf (f, " ");
|
}
|
}
|
}
|
}
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
}
|
}
|
}
|
}
|
|
|
if ((flag & LIVEDUMP_EXIT) && live->liveout)
|
if ((flag & LIVEDUMP_EXIT) && live->liveout)
|
{
|
{
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
fprintf (f, "\nLive on exit from BB%d : ", bb->index);
|
fprintf (f, "\nLive on exit from BB%d : ", bb->index);
|
EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
|
{
|
{
|
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
|
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
|
fprintf (f, " ");
|
fprintf (f, " ");
|
}
|
}
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
void
|
void
|
register_ssa_partition_check (tree ssa_var)
|
register_ssa_partition_check (tree ssa_var)
|
{
|
{
|
gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
|
gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
|
if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
|
if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
|
{
|
{
|
fprintf (stderr, "Illegally registering a virtual SSA name :");
|
fprintf (stderr, "Illegally registering a virtual SSA name :");
|
print_generic_expr (stderr, ssa_var, TDF_SLIM);
|
print_generic_expr (stderr, ssa_var, TDF_SLIM);
|
fprintf (stderr, " in the SSA->Normal phase.\n");
|
fprintf (stderr, " in the SSA->Normal phase.\n");
|
internal_error ("SSA corruption");
|
internal_error ("SSA corruption");
|
}
|
}
|
}
|
}
|
#endif
|
#endif
|
|
|
