/* Tail merging for gimple.
- Copyright (C) 2011 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 "output.h"
-#include "flags.h"
-#include "function.h"
-#include "tree-flow.h"
-#include "timevar.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 "tree-pretty-print.h"
-#include "hashtab.h"
-#include "gimple-pretty-print.h"
#include "tree-ssa-sccvn.h"
-#include "tree-dump.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. */
+ 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::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;
#define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
#define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
+/* Returns true if the only effect a statement STMT has, is to define locally
+ used SSA_NAMEs. */
+
+static bool
+stmt_local_def (gimple *stmt)
+{
+ basic_block bb, def_bb;
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ tree val;
+ def_operand_p def_p;
+
+ 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);
+ if (def_p == NULL)
+ return false;
+
+ val = DEF_FROM_PTR (def_p);
+ if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
+ return false;
+
+ def_bb = gimple_bb (stmt);
+
+ FOR_EACH_IMM_USE_FAST (use_p, iter, val)
+ {
+ if (is_gimple_debug (USE_STMT (use_p)))
+ continue;
+ bb = gimple_bb (USE_STMT (use_p));
+ if (bb == def_bb)
+ continue;
+
+ if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
+ && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
+ continue;
+
+ return false;
+ }
+
+ return true;
+}
+
+/* Let GSI skip forwards over local defs. */
+
+static void
+gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
+{
+ gimple *stmt;
+
+ while (true)
+ {
+ if (gsi_end_p (*gsi))
+ return;
+ stmt = gsi_stmt (*gsi);
+ if (!stmt_local_def (stmt))
+ return;
+ gsi_next_nondebug (gsi);
+ }
+}
+
/* VAL1 and VAL2 are either:
- uses in BB1 and BB2, or
- phi alternatives for BB1 and BB2.
/* 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. */
-static int
-same_succ_print_traverse (void **ve, void *vfile)
+inline int
+ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
{
- const same_succ e = *((const same_succ *)ve);
- FILE *file = ((FILE*)vfile);
+ 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;
update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
}
-/* Returns whether VAL is used in the same bb as in which it is defined, or
- in the phi of a successor bb. */
-
-static bool
-local_def (tree val)
-{
- gimple stmt, def_stmt;
- basic_block bb, def_bb;
- imm_use_iterator iter;
- bool res;
-
- if (TREE_CODE (val) != SSA_NAME)
- return false;
- def_stmt = SSA_NAME_DEF_STMT (val);
- def_bb = gimple_bb (def_stmt);
-
- res = true;
- FOR_EACH_IMM_USE_STMT (stmt, iter, val)
- {
- bb = gimple_bb (stmt);
- if (bb == def_bb)
- continue;
- if (gimple_code (stmt) == GIMPLE_PHI
- && find_edge (def_bb, bb))
- continue;
- res = false;
- BREAK_FROM_IMM_USE_STMT (iter);
- }
- return res;
-}
-
/* Calculates hash value for same_succ VE. */
static hashval_t
-same_succ_hash (const void *ve)
+same_succ_hash (const same_succ *e)
{
- const_same_succ e = (const_same_succ)ve;
- 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);
stmt_update_dep_bb (stmt);
- if (is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
- && !gimple_has_side_effects (stmt))
+ if (stmt_local_def (stmt))
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);
- if (!is_gimple_reg (lhs))
+ if (virtual_operand_p (lhs))
continue;
update_dep_bb (bb, val);
}
}
- 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;
return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
}
-/* Compares SAME_SUCCs VE1 and VE2. */
+/* Compares SAME_SUCCs E1 and E2. */
-static int
-same_succ_equal (const void *ve1, const void *ve2)
+int
+same_succ::equal (const same_succ *e1, const same_succ *e2)
{
- const_same_succ e1 = (const_same_succ)ve1;
- const_same_succ e2 = (const_same_succ)ve2;
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;
gsi1 = gsi_start_nondebug_bb (bb1);
gsi2 = gsi_start_nondebug_bb (bb2);
+ gsi_advance_fw_nondebug_nonlocal (&gsi1);
+ gsi_advance_fw_nondebug_nonlocal (&gsi2);
while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
{
s1 = gsi_stmt (gsi1);
return 0;
gsi_next_nondebug (&gsi1);
gsi_next_nondebug (&gsi2);
+ gsi_advance_fw_nondebug_nonlocal (&gsi1);
+ gsi_advance_fw_nondebug_nonlocal (&gsi2);
}
return 1;
/* 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 VE. */
+/* Delete same_succ E. */
-static void
-same_succ_delete (void *ve)
+void
+same_succ::remove (same_succ *e)
{
- same_succ e = (same_succ)ve;
-
BITMAP_FREE (e->bbs);
BITMAP_FREE (e->succs);
BITMAP_FREE (e->inverse);
- VEC_free (int, heap, e->succ_flags);
+ e->succ_flags.release ();
- XDELETE (ve);
+ 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);
}
-/* Hash table with all same_succ entries. */
-
-static htab_t 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)
{
- htab_traverse (same_succ_htab, 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_succ_htab, 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_delete (same);
+ same_succ::remove (same);
}
/* Initializes worklist administration. */
init_worklist (void)
{
alloc_aux_for_blocks (sizeof (struct aux_bb_info));
- same_succ_htab
- = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
- same_succ_delete);
- 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 ();
- htab_delete (same_succ_htab);
+ 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
-delete_basic_block_same_succ (basic_block bb)
+mark_basic_block_deleted (basic_block bb)
{
edge e;
edge_iterator ei;
bitmap_set_bit (deleted_bb_preds, e->src->index);
}
+/* Removes BB from its corresponding same_succ. */
+
+static void
+same_succ_flush_bb (basic_block 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);
+ else
+ bitmap_clear_bit (same->bbs, bb->index);
+}
+
/* Removes all bbs in BBS from their corresponding same_succ. */
static void
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
- {
- basic_block bb = BASIC_BLOCK (i);
- same_succ same = BB_SAME_SUCC (bb);
- BB_SAME_SUCC (bb) = NULL;
- if (bitmap_single_bit_set_p (same->bbs))
- htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
- else
- bitmap_clear_bit (same->bbs, i);
- }
+ same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
}
-/* Delete all deleted_bbs. */
+/* Release the last vdef in BB, either normal or phi result. */
static void
-purge_bbs (void)
+release_last_vdef (basic_block bb)
{
- unsigned int i;
- bitmap_iterator bi;
+ for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
+ gsi_prev_nondebug (&i))
+ {
+ gimple *stmt = gsi_stmt (i);
+ if (gimple_vdef (stmt) == NULL_TREE)
+ continue;
+
+ mark_virtual_operand_for_renaming (gimple_vdef (stmt));
+ return;
+ }
- same_succ_flush_bbs (deleted_bbs);
+ for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
+ gsi_next (&i))
+ {
+ gphi *phi = i.phi ();
+ tree res = gimple_phi_result (phi);
- EXECUTE_IF_SET_IN_BITMAP (deleted_bbs, 0, i, bi)
- delete_basic_block (BASIC_BLOCK (i));
+ if (!virtual_operand_p (res))
+ continue;
- bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
- bitmap_clear (deleted_bbs);
+ 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);
bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
same_succ_flush_bbs (deleted_bb_preds);
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_delete (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_same_target_p (s1, s2))
+ return false;
+
+ 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;
- if (!gimple_call_same_target_p (s1, s2))
- return false;
- equal = true;
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 true;
lhs1 = gimple_get_lhs (s1);
lhs2 = gimple_get_lhs (s2);
- return (lhs1 != NULL_TREE && lhs2 != NULL_TREE
- && TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME
- && vn_valueize (lhs1) == vn_valueize (lhs2));
+ if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
+ return true;
+ if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
+ return false;
+ if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
+ return vn_valueize (lhs1) == vn_valueize (lhs2);
+ return operand_equal_p (lhs1, lhs2, 0);
case GIMPLE_ASSIGN:
lhs1 = gimple_get_lhs (s1);
lhs2 = gimple_get_lhs (s2);
- 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;
}
}
-/* Let GSI skip backwards over local defs. */
+/* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
+ Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
+ processed statements. */
static void
-gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
+gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
+ bool *vuse_escaped)
{
- gimple stmt;
+ gimple *stmt;
+ tree lvuse;
while (true)
{
if (gsi_end_p (*gsi))
return;
stmt = gsi_stmt (*gsi);
- if (!(is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
- && !gimple_has_side_effects (stmt)))
+
+ lvuse = gimple_vuse (stmt);
+ if (lvuse != NULL_TREE)
+ {
+ *vuse = lvuse;
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
+ *vuse_escaped = true;
+ }
+
+ if (!stmt_local_def (stmt))
return;
gsi_prev_nondebug (gsi);
}
}
+/* 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);
+ tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
+ bool vuse_escaped = false;
- gsi_advance_bw_nondebug_nonlocal (&gsi1);
- gsi_advance_bw_nondebug_nonlocal (&gsi2);
+ gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
+ gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
{
- if (!gimple_equal_p (same_succ, gsi_stmt (gsi1), 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;
+
+ if (!merge_stmts_p (stmt1, stmt2))
return;
gsi_prev_nondebug (&gsi1);
gsi_prev_nondebug (&gsi2);
- gsi_advance_bw_nondebug_nonlocal (&gsi1);
- gsi_advance_bw_nondebug_nonlocal (&gsi2);
+ gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
+ 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;
+ /* If the incoming vuses are not the same, and the vuse escaped into an
+ SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
+ which potentially means the semantics of one of the blocks will be changed.
+ TODO: make this check more precise. */
+ if (vuse_escaped && vuse1 != vuse2)
+ return;
+
if (dump_file)
fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
bb1->index, bb2->index);
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);
- if (!is_gimple_reg (lhs))
+ if (virtual_operand_p (lhs))
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;
return true;
phi = gimple_seq_first_stmt (phis);
- return is_gimple_reg (gimple_phi_result (phi));
+ return !virtual_operand_p (gimple_phi_result (phi));
}
/* Returns true if redirecting the incoming edges of FROM to TO maintains the
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))
{
}
}
-/* Create or update a vop phi in BB2. Use VUSE1 arguments for all the
- REDIRECTED_EDGES, or if VUSE1 is NULL_TREE, use BB_VOP_AT_EXIT. If a new
- phis is created, use the phi instead of VUSE2 in BB2. */
-
-static void
-update_vuses (tree vuse1, tree vuse2, basic_block bb2,
- VEC (edge,heap) *redirected_edges)
-{
- gimple stmt, phi = NULL;
- tree lhs = NULL_TREE, arg;
- unsigned int i;
- gimple def_stmt2;
- imm_use_iterator iter;
- use_operand_p use_p;
- edge_iterator ei;
- edge e;
-
- def_stmt2 = SSA_NAME_DEF_STMT (vuse2);
-
- if (gimple_bb (def_stmt2) == bb2)
- /* Update existing phi. */
- phi = def_stmt2;
- else
- {
- /* No need to create a phi with 2 equal arguments. */
- if (vuse1 == vuse2)
- return;
-
- /* Create a phi. */
- lhs = make_ssa_name (SSA_NAME_VAR (vuse2), NULL);
- VN_INFO_GET (lhs);
- phi = create_phi_node (lhs, bb2);
- SSA_NAME_DEF_STMT (lhs) = phi;
-
- /* Set default argument vuse2 for all preds. */
- FOR_EACH_EDGE (e, ei, bb2->preds)
- add_phi_arg (phi, vuse2, e, UNKNOWN_LOCATION);
- }
-
- /* Update phi. */
- for (i = 0; i < EDGE_COUNT (redirected_edges); ++i)
- {
- e = VEC_index (edge, redirected_edges, i);
- if (vuse1 != NULL_TREE)
- arg = vuse1;
- else
- arg = BB_VOP_AT_EXIT (e->src);
- add_phi_arg (phi, arg, e, UNKNOWN_LOCATION);
- }
-
- /* Return if we updated an existing phi. */
- if (gimple_bb (def_stmt2) == bb2)
- return;
-
- /* Replace relevant uses of vuse2 with the newly created phi. */
- FOR_EACH_IMM_USE_STMT (stmt, iter, vuse2)
- {
- if (stmt == phi)
- continue;
- if (gimple_code (stmt) != GIMPLE_PHI)
- if (gimple_bb (stmt) != bb2)
- continue;
-
- FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
- {
- if (gimple_code (stmt) == GIMPLE_PHI)
- {
- unsigned int pred_index = PHI_ARG_INDEX_FROM_USE (use_p);
- basic_block pred = EDGE_PRED (gimple_bb (stmt), pred_index)->src;
- if (pred != bb2)
- continue;
- }
- SET_USE (use_p, lhs);
- update_stmt (stmt);
- }
- }
-}
-
/* 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);
- if (is_gimple_reg (gimple_phi_result (stmt)))
+ stmt = gsi.phi ();
+ if (! virtual_operand_p (gimple_phi_result (stmt)))
continue;
return stmt;
}
return NULL;
}
-/* Returns the vop state at the entry of BB, if found in BB or a successor
- bb. */
+/* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
-static tree
-vop_at_entry (basic_block bb)
+static void
+replace_block_by (basic_block bb1, basic_block bb2)
{
- gimple bb_phi, succ_phi;
- gimple_stmt_iterator gsi;
- gimple stmt;
- tree vuse, vdef;
- basic_block succ;
+ edge pred_edge;
+ edge e1, e2;
+ edge_iterator ei;
+ unsigned int i;
+ gphi *bb2_phi;
+
+ bb2_phi = vop_phi (bb2);
- bb_phi = vop_phi (bb);
- if (bb_phi != NULL)
- return gimple_phi_result (bb_phi);
+ /* Mark the basic block as deleted. */
+ mark_basic_block_deleted (bb1);
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ /* Redirect the incoming edges of bb1 to bb2. */
+ for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
{
- stmt = gsi_stmt (gsi);
- vuse = gimple_vuse (stmt);
- vdef = gimple_vdef (stmt);
- if (vuse != NULL_TREE)
- return vuse;
- if (vdef != NULL_TREE)
- return NULL_TREE;
- }
+ pred_edge = EDGE_PRED (bb1, i - 1);
+ pred_edge = redirect_edge_and_branch (pred_edge, bb2);
+ gcc_assert (pred_edge != NULL);
- if (EDGE_COUNT (bb->succs) == 0)
- return NULL_TREE;
+ if (bb2_phi == NULL)
+ continue;
- succ = EDGE_SUCC (bb, 0)->dest;
- succ_phi = vop_phi (succ);
- return (succ_phi != NULL
- ? PHI_ARG_DEF_FROM_EDGE (succ_phi, find_edge (bb, succ))
- : NULL_TREE);
-}
+ /* The phi might have run out of capacity when the redirect added an
+ argument, which means it could have been replaced. Refresh it. */
+ bb2_phi = vop_phi (bb2);
-/* Redirect all edges from BB1 to BB2, marks BB1 for removal, and if
- UPDATE_VOPS, inserts vop phis. */
+ add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
+ pred_edge, UNKNOWN_LOCATION);
+ }
-static void
-replace_block_by (basic_block bb1, basic_block bb2, bool update_vops)
-{
- edge pred_edge;
- unsigned int i;
- tree phi_vuse1 = NULL_TREE, phi_vuse2 = NULL_TREE, arg;
- VEC (edge,heap) *redirected_edges = NULL;
- edge e;
- edge_iterator ei;
+ bb2->frequency += bb1->frequency;
+ if (bb2->frequency > BB_FREQ_MAX)
+ bb2->frequency = BB_FREQ_MAX;
- if (update_vops)
- {
- /* Find the vops at entry of bb1 and bb2. */
- phi_vuse1 = vop_at_entry (bb1);
- phi_vuse2 = vop_at_entry (bb2);
+ bb2->count += bb1->count;
- /* If one of the 2 not found, it means there's no need to update. */
- update_vops = phi_vuse1 != NULL_TREE && phi_vuse2 != NULL_TREE;
+ /* 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);
}
- if (update_vops && gimple_bb (SSA_NAME_DEF_STMT (phi_vuse1)) == bb1)
+ /* 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)
{
- /* If the vop at entry of bb1 is a phi, save the phi alternatives in
- BB_VOP_AT_EXIT, before we lose that information by redirecting the
- edges. */
- FOR_EACH_EDGE (e, ei, bb1->preds)
+ gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
+ while (!gsi_end_p (gsi1)
+ && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
{
- arg = PHI_ARG_DEF_FROM_EDGE (SSA_NAME_DEF_STMT (phi_vuse1), e);
- BB_VOP_AT_EXIT (e->src) = arg;
+ 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);
}
- phi_vuse1 = NULL;
}
- /* Mark the basic block for later deletion. */
- delete_basic_block_same_succ (bb1);
-
- if (update_vops)
- redirected_edges = VEC_alloc (edge, heap, 10);
+ /* Clear range info from all stmts in BB2 -- this transformation
+ could make them out of date. */
+ reset_flow_sensitive_info_in_bb (bb2);
- /* Redirect the incoming edges of bb1 to bb2. */
- for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
- {
- pred_edge = EDGE_PRED (bb1, i - 1);
- pred_edge = redirect_edge_and_branch (pred_edge, bb2);
- gcc_assert (pred_edge != NULL);
- if (update_vops)
- VEC_safe_push (edge, heap, redirected_edges, pred_edge);
- }
+ /* Do updates that use bb1, before deleting bb1. */
+ release_last_vdef (bb1);
+ same_succ_flush_bb (bb1);
- /* Update the vops. */
- if (update_vops)
- {
- update_vuses (phi_vuse1, phi_vuse2, bb2, redirected_edges);
- VEC_free (edge, heap, redirected_edges);
- }
+ delete_basic_block (bb1);
}
/* Bbs for which update_debug_stmt need to be called. */
static bitmap update_bbs;
/* For each cluster in all_clusters, merge all cluster->bbs. Returns
- number of bbs removed. Insert vop phis if UPDATE_VOPS. */
+ number of bbs removed. */
static int
-apply_clusters (bool update_vops)
+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, update_vops);
+ replace_block_by (bb1, bb2);
nr_bbs_removed++;
}
}
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;
}
}
bitmap_iterator bi;
unsigned int i;
- if (!MAY_HAVE_DEBUG_STMTS)
- return;
-
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 nr_bbs_removed;
bool loop_entered = false;
int iteration_nr = 0;
- bool update_vops = !symbol_marked_for_renaming (gimple_vop (cfun));
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);
- calculate_dominance_info (CDI_DOMINATORS);
+ if (!dom_info_available_p (CDI_DOMINATORS))
+ {
+ /* PRE can leave us with unreachable blocks, remove them now. */
+ delete_unreachable_blocks ();
+ calculate_dominance_info (CDI_DOMINATORS);
+ }
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 (update_vops);
+ nr_bbs_removed = apply_clusters ();
nr_bbs_removed_total += nr_bbs_removed;
if (nr_bbs_removed == 0)
break;
free_dominance_info (CDI_DOMINATORS);
- purge_bbs ();
if (iteration_nr == max_iterations)
break;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "htab collision / search: %f\n",
- htab_collisions (same_succ_htab));
+ same_succ_htab->collisions ());
if (nr_bbs_removed_total > 0)
{
- calculate_dominance_info (CDI_DOMINATORS);
- update_debug_stmts ();
+ if (MAY_HAVE_DEBUG_STMTS)
+ {
+ calculate_dominance_info (CDI_DOMINATORS);
+ update_debug_stmts ();
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_function_to_file (current_function_decl, dump_file, dump_flags);
}
- todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow
- | TODO_dump_func);
+ mark_virtual_operands_for_renaming (cfun);
}
delete_worklist ();
projects / thirdparty / gcc.git / blobdiff