/* Tail merging for gimple.
- Copyright (C) 2011, 2012 Free Software Foundation, Inc.
+ Copyright (C) 2011-2017 Free Software Foundation, Inc.
Contributed by Tom de Vries (tom@codesourcery.com)
This file is part of GCC.
# BLOCK 7 freq:10000
# PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
- 6 [100.0%] (fallthru,exec)
+ 6 [100.0%] (fallthru,exec)
# PT = nonlocal null
# ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
# .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
- .MEMD.3923_18(6)>
+ .MEMD.3923_18(6)>
# VUSE <.MEMD.3923_11>
return ctxD.2601_1;
# SUCC: EXIT [100.0%]
- handle blocks with gimple_reg phi_nodes.
+ PASS PLACEMENT
+ This 'pass' is not a stand-alone gimple pass, but runs as part of
+ pass_pre, in order to share the value numbering.
+
+
SWITCHES
- ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
#include "tree.h"
-#include "tm_p.h"
-#include "basic-block.h"
-#include "flags.h"
-#include "function.h"
-#include "tree-flow.h"
-#include "bitmap.h"
-#include "tree-ssa-alias.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "fold-const.h"
+#include "trans-mem.h"
+#include "cfganal.h"
+#include "cfgcleanup.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-into-ssa.h"
#include "params.h"
-#include "hash-table.h"
-#include "gimple-pretty-print.h"
#include "tree-ssa-sccvn.h"
-#include "tree-dump.h"
-
-/* ??? This currently runs as part of tree-ssa-pre. Why is this not
- a stand-alone GIMPLE pass? */
-#include "tree-pass.h"
+#include "cfgloop.h"
+#include "tree-eh.h"
/* Describes a group of bbs with the same successors. The successor bbs are
cached in succs, and the successor edge flags are cached in succ_flags.
- If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
+ If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
it's marked in inverse.
Additionally, the hash value for the struct is cached in hashval, and
in_worklist indicates whether it's currently part of worklist. */
-struct same_succ_def
+struct same_succ : pointer_hash <same_succ>
{
/* The bbs that have the same successor bbs. */
bitmap bbs;
bb. */
bitmap inverse;
/* The edge flags for each of the successor bbs. */
- VEC (int, heap) *succ_flags;
+ vec<int> succ_flags;
/* Indicates whether the struct is currently in the worklist. */
bool in_worklist;
/* The hash value of the struct. */
hashval_t hashval;
/* hash_table support. */
- typedef same_succ_def value_type;
- typedef same_succ_def compare_type;
- static inline hashval_t hash (const value_type *);
- static int equal (const value_type *, const compare_type *);
- static void remove (value_type *);
+ static inline hashval_t hash (const same_succ *);
+ static int equal (const same_succ *, const same_succ *);
+ static void remove (same_succ *);
};
-typedef struct same_succ_def *same_succ;
-typedef const struct same_succ_def *const_same_succ;
/* hash routine for hash_table support, returns hashval of E. */
inline hashval_t
-same_succ_def::hash (const value_type *e)
+same_succ::hash (const same_succ *e)
{
return e->hashval;
}
/* A group of bbs where 1 bb from bbs can replace the other bbs. */
-struct bb_cluster_def
+struct bb_cluster
{
/* The bbs in the cluster. */
bitmap bbs;
/* The bb to replace the cluster with. */
basic_block rep_bb;
};
-typedef struct bb_cluster_def *bb_cluster;
-typedef const struct bb_cluster_def *const_bb_cluster;
/* Per bb-info. */
/* The number of non-debug statements in the bb. */
int size;
/* The same_succ that this bb is a member of. */
- same_succ bb_same_succ;
+ same_succ *bb_same_succ;
/* The cluster that this bb is a member of. */
- bb_cluster cluster;
+ bb_cluster *cluster;
/* The vop state at the exit of a bb. This is shortlived data, used to
communicate data between update_block_by and update_vuses. */
tree vop_at_exit;
used SSA_NAMEs. */
static bool
-stmt_local_def (gimple stmt)
+stmt_local_def (gimple *stmt)
{
basic_block bb, def_bb;
imm_use_iterator iter;
tree val;
def_operand_p def_p;
- if (gimple_has_side_effects (stmt))
+ if (gimple_vdef (stmt) != NULL_TREE
+ || gimple_has_side_effects (stmt)
+ || gimple_could_trap_p_1 (stmt, false, false)
+ || gimple_vuse (stmt) != NULL_TREE)
return false;
def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
static void
gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
{
- gimple stmt;
+ gimple *stmt;
while (true)
{
stmt = gsi_stmt (*gsi);
if (!stmt_local_def (stmt))
return;
- gsi_next_nondebug (gsi);
+ gsi_next_nondebug (gsi);
}
}
/* Prints E to FILE. */
static void
-same_succ_print (FILE *file, const same_succ e)
+same_succ_print (FILE *file, const same_succ *e)
{
unsigned int i;
bitmap_print (file, e->bbs, "bbs:", "\n");
bitmap_print (file, e->succs, "succs:", "\n");
bitmap_print (file, e->inverse, "inverse:", "\n");
fprintf (file, "flags:");
- for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
- fprintf (file, " %x", VEC_index (int, e->succ_flags, i));
+ for (i = 0; i < e->succ_flags.length (); ++i)
+ fprintf (file, " %x", e->succ_flags[i]);
fprintf (file, "\n");
}
/* Prints same_succ VE to VFILE. */
inline int
-ssa_same_succ_print_traverse (same_succ *pe, FILE *file)
+ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
{
- const same_succ e = *pe;
+ const same_succ *e = *pe;
same_succ_print (file, e);
return 1;
}
/* Update BB_DEP_BB, given the dependencies in STMT. */
static void
-stmt_update_dep_bb (gimple stmt)
+stmt_update_dep_bb (gimple *stmt)
{
ssa_op_iter iter;
use_operand_p use;
/* Calculates hash value for same_succ VE. */
static hashval_t
-same_succ_hash (const_same_succ e)
+same_succ_hash (const same_succ *e)
{
- hashval_t hashval = bitmap_hash (e->succs);
+ inchash::hash hstate (bitmap_hash (e->succs));
int flags;
unsigned int i;
unsigned int first = bitmap_first_set_bit (e->bbs);
- basic_block bb = BASIC_BLOCK (first);
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
int size = 0;
- gimple_stmt_iterator gsi;
- gimple stmt;
+ gimple *stmt;
tree arg;
unsigned int s;
bitmap_iterator bs;
- for (gsi = gsi_start_nondebug_bb (bb);
+ for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
!gsi_end_p (gsi); gsi_next_nondebug (&gsi))
{
stmt = gsi_stmt (gsi);
continue;
size++;
- hashval = iterative_hash_hashval_t (gimple_code (stmt), hashval);
+ hstate.add_int (gimple_code (stmt));
if (is_gimple_assign (stmt))
- hashval = iterative_hash_hashval_t (gimple_assign_rhs_code (stmt),
- hashval);
+ hstate.add_int (gimple_assign_rhs_code (stmt));
if (!is_gimple_call (stmt))
continue;
if (gimple_call_internal_p (stmt))
- hashval = iterative_hash_hashval_t
- ((hashval_t) gimple_call_internal_fn (stmt), hashval);
+ hstate.add_int (gimple_call_internal_fn (stmt));
else
- hashval = iterative_hash_expr (gimple_call_fn (stmt), hashval);
+ {
+ inchash::add_expr (gimple_call_fn (stmt), hstate);
+ if (gimple_call_chain (stmt))
+ inchash::add_expr (gimple_call_chain (stmt), hstate);
+ }
for (i = 0; i < gimple_call_num_args (stmt); i++)
{
arg = gimple_call_arg (stmt, i);
arg = vn_valueize (arg);
- hashval = iterative_hash_expr (arg, hashval);
+ inchash::add_expr (arg, hstate);
}
}
- hashval = iterative_hash_hashval_t (size, hashval);
+ hstate.add_int (size);
BB_SIZE (bb) = size;
- for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
+ for (i = 0; i < e->succ_flags.length (); ++i)
{
- flags = VEC_index (int, e->succ_flags, i);
+ flags = e->succ_flags[i];
flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
- hashval = iterative_hash_hashval_t (flags, hashval);
+ hstate.add_int (flags);
}
EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
{
- int n = find_edge (bb, BASIC_BLOCK (s))->dest_idx;
- for (gsi = gsi_start_phis (BASIC_BLOCK (s)); !gsi_end_p (gsi);
+ int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
+ for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
+ !gsi_end_p (gsi);
gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
tree lhs = gimple_phi_result (phi);
tree val = gimple_phi_arg_def (phi, n);
}
}
- return hashval;
+ return hstate.end ();
}
/* Returns true if E1 and E2 have 2 successors, and if the successor flags
the other edge flags. */
static bool
-inverse_flags (const_same_succ e1, const_same_succ e2)
+inverse_flags (const same_succ *e1, const same_succ *e2)
{
int f1a, f1b, f2a, f2b;
int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
- if (VEC_length (int, e1->succ_flags) != 2)
+ if (e1->succ_flags.length () != 2)
return false;
- f1a = VEC_index (int, e1->succ_flags, 0);
- f1b = VEC_index (int, e1->succ_flags, 1);
- f2a = VEC_index (int, e2->succ_flags, 0);
- f2b = VEC_index (int, e2->succ_flags, 1);
+ f1a = e1->succ_flags[0];
+ f1b = e1->succ_flags[1];
+ f2a = e2->succ_flags[0];
+ f2b = e2->succ_flags[1];
if (f1a == f2a && f1b == f2b)
return false;
/* Compares SAME_SUCCs E1 and E2. */
int
-same_succ_def::equal (const value_type *e1, const compare_type *e2)
+same_succ::equal (const same_succ *e1, const same_succ *e2)
{
unsigned int i, first1, first2;
gimple_stmt_iterator gsi1, gsi2;
- gimple s1, s2;
+ gimple *s1, *s2;
basic_block bb1, bb2;
+ if (e1 == e2)
+ return 1;
+
if (e1->hashval != e2->hashval)
return 0;
- if (VEC_length (int, e1->succ_flags) != VEC_length (int, e2->succ_flags))
+ if (e1->succ_flags.length () != e2->succ_flags.length ())
return 0;
if (!bitmap_equal_p (e1->succs, e2->succs))
if (!inverse_flags (e1, e2))
{
- for (i = 0; i < VEC_length (int, e1->succ_flags); ++i)
- if (VEC_index (int, e1->succ_flags, i)
- != VEC_index (int, e1->succ_flags, i))
+ for (i = 0; i < e1->succ_flags.length (); ++i)
+ if (e1->succ_flags[i] != e2->succ_flags[i])
return 0;
}
first1 = bitmap_first_set_bit (e1->bbs);
first2 = bitmap_first_set_bit (e2->bbs);
- bb1 = BASIC_BLOCK (first1);
- bb2 = BASIC_BLOCK (first2);
+ bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
+ bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
if (BB_SIZE (bb1) != BB_SIZE (bb2))
return 0;
/* Alloc and init a new SAME_SUCC. */
-static same_succ
+static same_succ *
same_succ_alloc (void)
{
- same_succ same = XNEW (struct same_succ_def);
+ same_succ *same = XNEW (struct same_succ);
same->bbs = BITMAP_ALLOC (NULL);
same->succs = BITMAP_ALLOC (NULL);
same->inverse = BITMAP_ALLOC (NULL);
- same->succ_flags = VEC_alloc (int, heap, 10);
+ same->succ_flags.create (10);
same->in_worklist = false;
return same;
/* Delete same_succ E. */
void
-same_succ_def::remove (same_succ e)
+same_succ::remove (same_succ *e)
{
BITMAP_FREE (e->bbs);
BITMAP_FREE (e->succs);
BITMAP_FREE (e->inverse);
- VEC_free (int, heap, e->succ_flags);
+ e->succ_flags.release ();
XDELETE (e);
}
/* Reset same_succ SAME. */
static void
-same_succ_reset (same_succ same)
+same_succ_reset (same_succ *same)
{
bitmap_clear (same->bbs);
bitmap_clear (same->succs);
bitmap_clear (same->inverse);
- VEC_truncate (int, same->succ_flags, 0);
+ same->succ_flags.truncate (0);
}
-static hash_table <same_succ_def> same_succ_htab;
+static hash_table<same_succ> *same_succ_htab;
/* Array that is used to store the edge flags for a successor. */
DEBUG_FUNCTION void
debug_same_succ ( void)
{
- same_succ_htab.traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
+ same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
}
-DEF_VEC_P (same_succ);
-DEF_VEC_ALLOC_P (same_succ, heap);
/* Vector of bbs to process. */
-static VEC (same_succ, heap) *worklist;
+static vec<same_succ *> worklist;
/* Prints worklist to FILE. */
print_worklist (FILE *file)
{
unsigned int i;
- for (i = 0; i < VEC_length (same_succ, worklist); ++i)
- same_succ_print (file, VEC_index (same_succ, worklist, i));
+ for (i = 0; i < worklist.length (); ++i)
+ same_succ_print (file, worklist[i]);
}
/* Adds SAME to worklist. */
static void
-add_to_worklist (same_succ same)
+add_to_worklist (same_succ *same)
{
if (same->in_worklist)
return;
return;
same->in_worklist = true;
- VEC_safe_push (same_succ, heap, worklist, same);
+ worklist.safe_push (same);
}
/* Add BB to same_succ_htab. */
static void
-find_same_succ_bb (basic_block bb, same_succ *same_p)
+find_same_succ_bb (basic_block bb, same_succ **same_p)
{
unsigned int j;
bitmap_iterator bj;
- same_succ same = *same_p;
- same_succ *slot;
+ same_succ *same = *same_p;
+ same_succ **slot;
edge_iterator ei;
edge e;
- if (bb == NULL)
+ if (bb == NULL
+ /* Be conservative with loop structure. It's not evident that this test
+ is sufficient. Before tail-merge, we've just called
+ loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
+ set, so there's no guarantee that the loop->latch value is still valid.
+ But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
+ start of pre, we've kept that property intact throughout pre, and are
+ keeping it throughout tail-merge using this test. */
+ || bb->loop_father->latch == bb)
return;
bitmap_set_bit (same->bbs, bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
same_succ_edge_flags[index] = e->flags;
}
EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
- VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
+ same->succ_flags.safe_push (same_succ_edge_flags[j]);
same->hashval = same_succ_hash (same);
- slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
+ slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
if (*slot == NULL)
{
*slot = same;
static void
find_same_succ (void)
{
- same_succ same = same_succ_alloc ();
+ same_succ *same = same_succ_alloc ();
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
find_same_succ_bb (bb, &same);
if (same == NULL)
same = same_succ_alloc ();
}
- same_succ_def::remove (same);
+ same_succ::remove (same);
}
/* Initializes worklist administration. */
init_worklist (void)
{
alloc_aux_for_blocks (sizeof (struct aux_bb_info));
- same_succ_htab.create (n_basic_blocks);
- same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
+ same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
+ same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
deleted_bbs = BITMAP_ALLOC (NULL);
deleted_bb_preds = BITMAP_ALLOC (NULL);
- worklist = VEC_alloc (same_succ, heap, n_basic_blocks);
+ worklist.create (n_basic_blocks_for_fn (cfun));
find_same_succ ();
if (dump_file && (dump_flags & TDF_DETAILS))
delete_worklist (void)
{
free_aux_for_blocks ();
- same_succ_htab.dispose ();
+ delete same_succ_htab;
+ same_succ_htab = NULL;
XDELETEVEC (same_succ_edge_flags);
same_succ_edge_flags = NULL;
BITMAP_FREE (deleted_bbs);
BITMAP_FREE (deleted_bb_preds);
- VEC_free (same_succ, heap, worklist);
+ worklist.release ();
}
/* Mark BB as deleted, and mark its predecessors. */
static void
same_succ_flush_bb (basic_block bb)
{
- same_succ same = BB_SAME_SUCC (bb);
+ same_succ *same = BB_SAME_SUCC (bb);
BB_SAME_SUCC (bb) = NULL;
if (bitmap_single_bit_set_p (same->bbs))
- same_succ_htab.remove_elt_with_hash (same, same->hashval);
+ same_succ_htab->remove_elt_with_hash (same, same->hashval);
else
bitmap_clear_bit (same->bbs, bb->index);
}
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
- same_succ_flush_bb (BASIC_BLOCK (i));
+ same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
}
/* Release the last vdef in BB, either normal or phi result. */
static void
release_last_vdef (basic_block bb)
{
- gimple_stmt_iterator i;
-
- for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
+ for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
+ gsi_prev_nondebug (&i))
{
- gimple stmt = gsi_stmt (i);
+ gimple *stmt = gsi_stmt (i);
if (gimple_vdef (stmt) == NULL_TREE)
continue;
return;
}
- for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
+ for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
+ gsi_next (&i))
{
- gimple phi = gsi_stmt (i);
+ gphi *phi = i.phi ();
tree res = gimple_phi_result (phi);
if (!virtual_operand_p (res))
mark_virtual_phi_result_for_renaming (phi);
return;
}
-
}
/* For deleted_bb_preds, find bbs with same successors. */
unsigned int i;
bitmap_iterator bi;
basic_block bb;
- same_succ same;
+ same_succ *same;
bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
bitmap_clear (deleted_bbs);
same = same_succ_alloc ();
EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
{
- bb = BASIC_BLOCK (i);
+ bb = BASIC_BLOCK_FOR_FN (cfun, i);
gcc_assert (bb != NULL);
find_same_succ_bb (bb, &same);
if (same == NULL)
same = same_succ_alloc ();
}
- same_succ_def::remove (same);
+ same_succ::remove (same);
bitmap_clear (deleted_bb_preds);
}
/* Prints cluster C to FILE. */
static void
-print_cluster (FILE *file, bb_cluster c)
+print_cluster (FILE *file, bb_cluster *c)
{
if (c == NULL)
return;
/* Prints cluster C to stderr. */
-extern void debug_cluster (bb_cluster);
+extern void debug_cluster (bb_cluster *);
DEBUG_FUNCTION void
-debug_cluster (bb_cluster c)
+debug_cluster (bb_cluster *c)
{
print_cluster (stderr, c);
}
/* Update C->rep_bb, given that BB is added to the cluster. */
static void
-update_rep_bb (bb_cluster c, basic_block bb)
+update_rep_bb (bb_cluster *c, basic_block bb)
{
/* Initial. */
if (c->rep_bb == NULL)
/* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
static void
-add_bb_to_cluster (bb_cluster c, basic_block bb)
+add_bb_to_cluster (bb_cluster *c, basic_block bb)
{
edge e;
edge_iterator ei;
/* Allocate and init new cluster. */
-static bb_cluster
+static bb_cluster *
new_cluster (void)
{
- bb_cluster c;
- c = XCNEW (struct bb_cluster_def);
+ bb_cluster *c;
+ c = XCNEW (bb_cluster);
c->bbs = BITMAP_ALLOC (NULL);
c->preds = BITMAP_ALLOC (NULL);
c->rep_bb = NULL;
/* Delete clusters. */
static void
-delete_cluster (bb_cluster c)
+delete_cluster (bb_cluster *c)
{
if (c == NULL)
return;
XDELETE (c);
}
-DEF_VEC_P (bb_cluster);
-DEF_VEC_ALLOC_P (bb_cluster, heap);
/* Array that contains all clusters. */
-static VEC (bb_cluster, heap) *all_clusters;
+static vec<bb_cluster *> all_clusters;
/* Allocate all cluster vectors. */
static void
alloc_cluster_vectors (void)
{
- all_clusters = VEC_alloc (bb_cluster, heap, n_basic_blocks);
+ all_clusters.create (n_basic_blocks_for_fn (cfun));
}
/* Reset all cluster vectors. */
{
unsigned int i;
basic_block bb;
- for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
- delete_cluster (VEC_index (bb_cluster, all_clusters, i));
- VEC_truncate (bb_cluster, all_clusters, 0);
- FOR_EACH_BB (bb)
+ for (i = 0; i < all_clusters.length (); ++i)
+ delete_cluster (all_clusters[i]);
+ all_clusters.truncate (0);
+ FOR_EACH_BB_FN (bb, cfun)
BB_CLUSTER (bb) = NULL;
}
delete_cluster_vectors (void)
{
unsigned int i;
- for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
- delete_cluster (VEC_index (bb_cluster, all_clusters, i));
- VEC_free (bb_cluster, heap, all_clusters);
+ for (i = 0; i < all_clusters.length (); ++i)
+ delete_cluster (all_clusters[i]);
+ all_clusters.release ();
}
/* Merge cluster C2 into C1. */
static void
-merge_clusters (bb_cluster c1, bb_cluster c2)
+merge_clusters (bb_cluster *c1, bb_cluster *c2)
{
bitmap_ior_into (c1->bbs, c2->bbs);
bitmap_ior_into (c1->preds, c2->preds);
set_cluster (basic_block bb1, basic_block bb2)
{
basic_block merge_bb, other_bb;
- bb_cluster merge, old, c;
+ bb_cluster *merge, *old, *c;
if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
{
add_bb_to_cluster (c, bb2);
BB_CLUSTER (bb1) = c;
BB_CLUSTER (bb2) = c;
- c->index = VEC_length (bb_cluster, all_clusters);
- VEC_safe_push (bb_cluster, heap, all_clusters, c);
+ c->index = all_clusters.length ();
+ all_clusters.safe_push (c);
}
else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
{
merge = BB_CLUSTER (bb1);
merge_clusters (merge, old);
EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
- BB_CLUSTER (BASIC_BLOCK (i)) = merge;
- VEC_replace (bb_cluster, all_clusters, old->index, NULL);
+ BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
+ all_clusters[old->index] = NULL;
update_rep_bb (merge, old->rep_bb);
delete_cluster (old);
}
gcc_unreachable ();
}
+/* Return true if gimple operands T1 and T2 have the same value. */
+
+static bool
+gimple_operand_equal_value_p (tree t1, tree t2)
+{
+ if (t1 == t2)
+ return true;
+
+ if (t1 == NULL_TREE
+ || t2 == NULL_TREE)
+ return false;
+
+ if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
+ return true;
+
+ return gvn_uses_equal (t1, t2);
+}
+
/* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
gimple_bb (s2) are members of SAME_SUCC. */
static bool
-gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
+gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
{
unsigned int i;
tree lhs1, lhs2;
basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
tree t1, t2;
- bool equal, inv_cond;
+ bool inv_cond;
enum tree_code code1, code2;
if (gimple_code (s1) != gimple_code (s2))
switch (gimple_code (s1))
{
case GIMPLE_CALL:
- if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
- return false;
if (!gimple_call_same_target_p (s1, s2))
- return false;
-
- /* Eventually, we'll significantly complicate the CFG by adding
- back edges to properly model the effects of transaction restart.
- For the bulk of optimization this does not matter, but what we
- cannot recover from is tail merging blocks between two separate
- transactions. Avoid that by making commit not match. */
- if (gimple_call_builtin_p (s1, BUILT_IN_TM_COMMIT))
return false;
- equal = true;
+ t1 = gimple_call_chain (s1);
+ t2 = gimple_call_chain (s2);
+ if (!gimple_operand_equal_value_p (t1, t2))
+ return false;
+
+ if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
+ return false;
+
for (i = 0; i < gimple_call_num_args (s1); ++i)
{
t1 = gimple_call_arg (s1, i);
t2 = gimple_call_arg (s2, i);
- if (operand_equal_p (t1, t2, 0))
- continue;
- if (gvn_uses_equal (t1, t2))
- continue;
- equal = false;
- break;
+ if (!gimple_operand_equal_value_p (t1, t2))
+ return false;
}
- if (!equal)
- return false;
lhs1 = gimple_get_lhs (s1);
lhs2 = gimple_get_lhs (s2);
case GIMPLE_ASSIGN:
lhs1 = gimple_get_lhs (s1);
lhs2 = gimple_get_lhs (s2);
- if (gimple_vdef (s1))
- {
- if (vn_valueize (gimple_vdef (s1)) != vn_valueize (gimple_vdef (s2)))
- return false;
- if (TREE_CODE (lhs1) != SSA_NAME
- && TREE_CODE (lhs2) != SSA_NAME)
- return true;
- }
- return (TREE_CODE (lhs1) == SSA_NAME
- && TREE_CODE (lhs2) == SSA_NAME
- && vn_valueize (lhs1) == vn_valueize (lhs2));
+ if (TREE_CODE (lhs1) != SSA_NAME
+ && TREE_CODE (lhs2) != SSA_NAME)
+ return (operand_equal_p (lhs1, lhs2, 0)
+ && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
+ gimple_assign_rhs1 (s2)));
+ else if (TREE_CODE (lhs1) == SSA_NAME
+ && TREE_CODE (lhs2) == SSA_NAME)
+ return operand_equal_p (gimple_assign_rhs1 (s1),
+ gimple_assign_rhs1 (s2), 0);
+ return false;
case GIMPLE_COND:
t1 = gimple_cond_lhs (s1);
t2 = gimple_cond_lhs (s2);
- if (!operand_equal_p (t1, t2, 0)
- && !gvn_uses_equal (t1, t2))
+ if (!gimple_operand_equal_value_p (t1, t2))
return false;
t1 = gimple_cond_rhs (s1);
t2 = gimple_cond_rhs (s2);
- if (!operand_equal_p (t1, t2, 0)
- && !gvn_uses_equal (t1, t2))
+ if (!gimple_operand_equal_value_p (t1, t2))
return false;
code1 = gimple_expr_code (s1);
!= bitmap_bit_p (same_succ->inverse, bb2->index));
if (inv_cond)
{
- bool honor_nans
- = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1))));
+ bool honor_nans = HONOR_NANS (t1);
code2 = invert_tree_comparison (code2, honor_nans);
}
return code1 == code2;
gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
bool *vuse_escaped)
{
- gimple stmt;
+ gimple *stmt;
tree lvuse;
while (true)
}
}
+/* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
+ STMT2 are allowed to be merged. */
+
+static bool
+merge_stmts_p (gimple *stmt1, gimple *stmt2)
+{
+ /* What could be better than this here is to blacklist the bb
+ containing the stmt, when encountering the stmt f.i. in
+ same_succ_hash. */
+ if (is_tm_ending (stmt1))
+ return false;
+
+ /* Verify EH landing pads. */
+ if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
+ return false;
+
+ if (is_gimple_call (stmt1)
+ && gimple_call_internal_p (stmt1))
+ switch (gimple_call_internal_fn (stmt1))
+ {
+ case IFN_UBSAN_NULL:
+ case IFN_UBSAN_BOUNDS:
+ case IFN_UBSAN_VPTR:
+ case IFN_UBSAN_CHECK_ADD:
+ case IFN_UBSAN_CHECK_SUB:
+ case IFN_UBSAN_CHECK_MUL:
+ case IFN_UBSAN_OBJECT_SIZE:
+ case IFN_ASAN_CHECK:
+ /* For these internal functions, gimple_location is an implicit
+ parameter, which will be used explicitly after expansion.
+ Merging these statements may cause confusing line numbers in
+ sanitizer messages. */
+ return gimple_location (stmt1) == gimple_location (stmt2);
+ default:
+ break;
+ }
+
+ return true;
+}
+
/* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
clusters them. */
static void
-find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
+find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
{
gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
{
- gimple stmt1 = gsi_stmt (gsi1);
- gimple stmt2 = gsi_stmt (gsi2);
+ gimple *stmt1 = gsi_stmt (gsi1);
+ gimple *stmt2 = gsi_stmt (gsi2);
+
+ if (gimple_code (stmt1) == GIMPLE_LABEL
+ && gimple_code (stmt2) == GIMPLE_LABEL)
+ break;
if (!gimple_equal_p (same_succ, stmt1, stmt2))
return;
- // We cannot tail-merge the builtins that end transactions.
- // ??? The alternative being unsharing of BBs in the tm_init pass.
- if (flag_tm
- && is_gimple_call (stmt1)
- && (gimple_call_flags (stmt1) & ECF_TM_BUILTIN)
- && is_tm_ending_fndecl (gimple_call_fndecl (stmt1)))
+ if (!merge_stmts_p (stmt1, stmt2))
return;
gsi_prev_nondebug (&gsi1);
gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
}
+ while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
+ {
+ tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
+ if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
+ return;
+ gsi_prev (&gsi1);
+ }
+ while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
+ {
+ tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
+ if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
+ return;
+ gsi_prev (&gsi2);
+ }
if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
return;
same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
{
int n1 = e1->dest_idx, n2 = e2->dest_idx;
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
tree lhs = gimple_phi_result (phi);
tree val1 = gimple_phi_arg_def (phi, n1);
tree val2 = gimple_phi_arg_def (phi, n2);
continue;
if (operand_equal_for_phi_arg_p (val1, val2))
- continue;
+ continue;
if (gvn_uses_equal (val1, val2))
continue;
phi alternatives for BB1 and BB2 are equal. */
static bool
-same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
+same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
{
unsigned int s;
bitmap_iterator bs;
EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
{
- succ = BASIC_BLOCK (s);
+ succ = BASIC_BLOCK_FOR_FN (cfun, s);
e1 = find_edge (bb1, succ);
e2 = find_edge (bb2, succ);
if (e1->flags & EDGE_COMPLEX
bb_has_non_vop_phi (basic_block bb)
{
gimple_seq phis = phi_nodes (bb);
- gimple phi;
+ gimple *phi;
if (phis == NULL)
return false;
basic_block cd, dep_bb = BB_DEP_BB (to);
edge_iterator ei;
edge e;
- bitmap from_preds = BITMAP_ALLOC (NULL);
if (dep_bb == NULL)
return true;
+ bitmap from_preds = BITMAP_ALLOC (NULL);
FOR_EACH_EDGE (e, ei, from->preds)
bitmap_set_bit (from_preds, e->src->index);
cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
/* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
static void
-find_clusters_1 (same_succ same_succ)
+find_clusters_1 (same_succ *same_succ)
{
basic_block bb1, bb2;
unsigned int i, j;
EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
{
- bb1 = BASIC_BLOCK (i);
+ bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
/* TODO: handle blocks with phi-nodes. We'll have to find corresponding
phi-nodes in bb1 and bb2, with the same alternatives for the same
preds. */
- if (bb_has_non_vop_phi (bb1))
+ if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1))
continue;
nr_comparisons = 0;
EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
{
- bb2 = BASIC_BLOCK (j);
+ bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
- if (bb_has_non_vop_phi (bb2))
+ if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2))
continue;
if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
continue;
- /* Limit quadratic behaviour. */
+ /* Limit quadratic behavior. */
nr_comparisons++;
if (nr_comparisons > max_comparisons)
break;
continue;
find_duplicate (same_succ, bb1, bb2);
- }
+ }
}
}
static void
find_clusters (void)
{
- same_succ same;
+ same_succ *same;
- while (!VEC_empty (same_succ, worklist))
+ while (!worklist.is_empty ())
{
- same = VEC_pop (same_succ, worklist);
+ same = worklist.pop ();
same->in_worklist = false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
/* Returns the vop phi of BB, if any. */
-static gimple
+static gphi *
vop_phi (basic_block bb)
{
- gimple stmt;
- gimple_stmt_iterator gsi;
+ gphi *stmt;
+ gphi_iterator gsi;
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- stmt = gsi_stmt (gsi);
+ stmt = gsi.phi ();
if (! virtual_operand_p (gimple_phi_result (stmt)))
continue;
return stmt;
replace_block_by (basic_block bb1, basic_block bb2)
{
edge pred_edge;
+ edge e1, e2;
+ edge_iterator ei;
unsigned int i;
- gimple bb2_phi;
+ gphi *bb2_phi;
bb2_phi = vop_phi (bb2);
bb2->count += bb1->count;
+ /* Merge the outgoing edge counts from bb1 onto bb2. */
+ gcov_type out_sum = 0;
+ FOR_EACH_EDGE (e1, ei, bb1->succs)
+ {
+ e2 = find_edge (bb2, e1->dest);
+ gcc_assert (e2);
+ e2->count += e1->count;
+ out_sum += e2->count;
+ }
+ /* Recompute the edge probabilities from the new merged edge count.
+ Use the sum of the new merged edge counts computed above instead
+ of bb2's merged count, in case there are profile count insanities
+ making the bb count inconsistent with the edge weights. */
+ FOR_EACH_EDGE (e2, ei, bb2->succs)
+ {
+ e2->probability = GCOV_COMPUTE_SCALE (e2->count, out_sum);
+ }
+
+ /* Move over any user labels from bb1 after the bb2 labels. */
+ gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
+ if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
+ {
+ gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
+ while (!gsi_end_p (gsi1)
+ && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
+ {
+ tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
+ gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
+ if (DECL_ARTIFICIAL (label))
+ gsi_next (&gsi1);
+ else
+ gsi_move_before (&gsi1, &gsi2);
+ }
+ }
+
+ /* Clear range info from all stmts in BB2 -- this transformation
+ could make them out of date. */
+ reset_flow_sensitive_info_in_bb (bb2);
+
/* Do updates that use bb1, before deleting bb1. */
release_last_vdef (bb1);
same_succ_flush_bb (bb1);
apply_clusters (void)
{
basic_block bb1, bb2;
- bb_cluster c;
+ bb_cluster *c;
unsigned int i, j;
bitmap_iterator bj;
int nr_bbs_removed = 0;
- for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
+ for (i = 0; i < all_clusters.length (); ++i)
{
- c = VEC_index (bb_cluster, all_clusters, i);
+ c = all_clusters[i];
if (c == NULL)
continue;
bitmap_clear_bit (c->bbs, bb2->index);
EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
{
- bb1 = BASIC_BLOCK (j);
+ bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
bitmap_clear_bit (update_bbs, bb1->index);
replace_block_by (bb1, bb2);
defs. */
static void
-update_debug_stmt (gimple stmt)
+update_debug_stmt (gimple *stmt)
{
use_operand_p use_p;
ssa_op_iter oi;
- basic_block bbdef, bbuse;
- gimple def_stmt;
- tree name;
+ basic_block bbuse;
if (!gimple_debug_bind_p (stmt))
return;
bbuse = gimple_bb (stmt);
FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
{
- name = USE_FROM_PTR (use_p);
- gcc_assert (TREE_CODE (name) == SSA_NAME);
-
- def_stmt = SSA_NAME_DEF_STMT (name);
- gcc_assert (def_stmt != NULL);
-
- bbdef = gimple_bb (def_stmt);
+ tree name = USE_FROM_PTR (use_p);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ basic_block bbdef = gimple_bb (def_stmt);
if (bbdef == NULL || bbuse == bbdef
|| dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
continue;
gimple_debug_bind_reset_value (stmt);
update_stmt (stmt);
+ break;
}
}
EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
{
- gimple stmt;
+ gimple *stmt;
gimple_stmt_iterator gsi;
- bb = BASIC_BLOCK (i);
+ bb = BASIC_BLOCK_FOR_FN (cfun, i);
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
stmt = gsi_stmt (gsi);
int iteration_nr = 0;
int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
- if (!flag_tree_tail_merge || max_iterations == 0)
+ if (!flag_tree_tail_merge
+ || max_iterations == 0)
return 0;
timevar_push (TV_TREE_TAIL_MERGE);
}
init_worklist ();
- while (!VEC_empty (same_succ, worklist))
+ while (!worklist.is_empty ())
{
if (!loop_entered)
{
fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
find_clusters ();
- gcc_assert (VEC_empty (same_succ, worklist));
- if (VEC_empty (bb_cluster, all_clusters))
+ gcc_assert (worklist.is_empty ());
+ if (all_clusters.is_empty ())
break;
nr_bbs_removed = apply_clusters ();
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "htab collision / search: %f\n",
- same_succ_htab.collisions ());
+ same_succ_htab->collisions ());
if (nr_bbs_removed_total > 0)
{
dump_function_to_file (current_function_decl, dump_file, dump_flags);
}
- todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow);
mark_virtual_operands_for_renaming (cfun);
}
projects / thirdparty / gcc.git / blobdiff