/* Control flow graph manipulation code for GNU compiler.
- Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 1987-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "obstack.h"
-#include "ggc.h"
-#include "hashtab.h"
+#include "backend.h"
#include "alloc-pool.h"
-#include "basic-block.h"
+#include "alias.h"
+#include "cfghooks.h"
+#include "tree.h"
+#include "hard-reg-set.h"
#include "df.h"
+#include "options.h"
+#include "cfganal.h"
#include "cfgloop.h" /* FIXME: For struct loop. */
#include "dumpfile.h"
init_flow (struct function *the_fun)
{
if (!the_fun->cfg)
- the_fun->cfg = ggc_alloc_cleared_control_flow_graph ();
- n_edges_for_function (the_fun) = 0;
- ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
- = ggc_alloc_cleared_basic_block_def ();
- ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
- EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
- = ggc_alloc_cleared_basic_block_def ();
- EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = EXIT_BLOCK;
- ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->next_bb
- = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun);
- EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->prev_bb
- = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun);
+ the_fun->cfg = ggc_cleared_alloc<control_flow_graph> ();
+ n_edges_for_fn (the_fun) = 0;
+ ENTRY_BLOCK_PTR_FOR_FN (the_fun)
+ = ggc_cleared_alloc<basic_block_def> ();
+ ENTRY_BLOCK_PTR_FOR_FN (the_fun)->index = ENTRY_BLOCK;
+ EXIT_BLOCK_PTR_FOR_FN (the_fun)
+ = ggc_cleared_alloc<basic_block_def> ();
+ EXIT_BLOCK_PTR_FOR_FN (the_fun)->index = EXIT_BLOCK;
+ ENTRY_BLOCK_PTR_FOR_FN (the_fun)->next_bb
+ = EXIT_BLOCK_PTR_FOR_FN (the_fun);
+ EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
+ = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
}
\f
/* Helper function for remove_edge and clear_edges. Frees edge structure
static void
free_edge (edge e)
{
- n_edges--;
+ n_edges_for_fn (cfun)--;
ggc_free (e);
}
edge e;
edge_iterator ei;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
FOR_EACH_EDGE (e, ei, bb->succs)
free_edge (e);
- VEC_truncate (edge, bb->succs, 0);
- VEC_truncate (edge, bb->preds, 0);
+ vec_safe_truncate (bb->succs, 0);
+ vec_safe_truncate (bb->preds, 0);
}
- FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
free_edge (e);
- VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
- VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
+ vec_safe_truncate (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds, 0);
+ vec_safe_truncate (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs, 0);
- gcc_assert (!n_edges);
+ gcc_assert (!n_edges_for_fn (cfun));
}
\f
/* Allocate memory for basic_block. */
alloc_block (void)
{
basic_block bb;
- bb = ggc_alloc_cleared_basic_block_def ();
+ bb = ggc_cleared_alloc<basic_block_def> ();
return bb;
}
{
int i;
- SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
- SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
+ SET_BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ SET_BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (cfun));
if (df)
df_compact_blocks ();
basic_block bb;
i = NUM_FIXED_BLOCKS;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- SET_BASIC_BLOCK (i, bb);
+ SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
bb->index = i;
i++;
}
- gcc_assert (i == n_basic_blocks);
+ gcc_assert (i == n_basic_blocks_for_fn (cfun));
- for (; i < last_basic_block; i++)
- SET_BASIC_BLOCK (i, NULL);
+ for (; i < last_basic_block_for_fn (cfun); i++)
+ SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
}
- last_basic_block = n_basic_blocks;
+ last_basic_block_for_fn (cfun) = n_basic_blocks_for_fn (cfun);
}
/* Remove block B from the basic block array. */
expunge_block (basic_block b)
{
unlink_block (b);
- SET_BASIC_BLOCK (b->index, NULL);
- n_basic_blocks--;
+ SET_BASIC_BLOCK_FOR_FN (cfun, b->index, NULL);
+ n_basic_blocks_for_fn (cfun)--;
/* We should be able to ggc_free here, but we are not.
The dead SSA_NAMES are left pointing to dead statements that are pointing
to dead basic blocks making garbage collector to die.
static inline void
connect_src (edge e)
{
- VEC_safe_push (edge, gc, e->src->succs, e);
+ vec_safe_push (e->src->succs, e);
df_mark_solutions_dirty ();
}
connect_dest (edge e)
{
basic_block dest = e->dest;
- VEC_safe_push (edge, gc, dest->preds, e);
+ vec_safe_push (dest->preds, e);
e->dest_idx = EDGE_COUNT (dest->preds) - 1;
df_mark_solutions_dirty ();
}
{
if (tmp == e)
{
- VEC_unordered_remove (edge, src->succs, ei.index);
+ src->succs->unordered_remove (ei.index);
df_mark_solutions_dirty ();
return;
}
basic_block dest = e->dest;
unsigned int dest_idx = e->dest_idx;
- VEC_unordered_remove (edge, dest->preds, dest_idx);
+ dest->preds->unordered_remove (dest_idx);
/* If we removed an edge in the middle of the edge vector, we need
to update dest_idx of the edge that moved into the "hole". */
unchecked_make_edge (basic_block src, basic_block dst, int flags)
{
edge e;
- e = ggc_alloc_cleared_edge_def ();
- n_edges++;
+ e = ggc_cleared_alloc<edge_def> ();
+ n_edges_for_fn (cfun)++;
e->src = src;
e->dest = dst;
cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
{
if (edge_cache == NULL
- || src == ENTRY_BLOCK_PTR
- || dst == EXIT_BLOCK_PTR)
+ || src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ || dst == EXIT_BLOCK_PTR_FOR_FN (cfun))
return make_edge (src, dst, flags);
/* Does the requested edge already exist? */
- if (! TEST_BIT (edge_cache, dst->index))
+ if (! bitmap_bit_p (edge_cache, dst->index))
{
/* The edge does not exist. Create one and update the
cache. */
- SET_BIT (edge_cache, dst->index);
+ bitmap_set_bit (edge_cache, dst->index);
return unchecked_make_edge (src, dst, flags);
}
{
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
bb->flags &= BB_FLAGS_TO_PRESERVE;
}
\f
int sum = 0;
gcov_type lsum;
edge_iterator ei;
+ struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
char *s_indent = (char *) alloca ((size_t) indent + 1);
memset ((void *) s_indent, ' ', (size_t) indent);
s_indent[indent] = '\0';
- if (profile_status == PROFILE_ABSENT)
+ if (profile_status_for_fn (fun) == PROFILE_ABSENT)
return;
- if (bb != EXIT_BLOCK_PTR)
+ if (bb != EXIT_BLOCK_PTR_FOR_FN (fun))
{
FOR_EACH_EDGE (e, ei, bb->succs)
sum += e->probability;
(flags & TDF_COMMENT) ? ";; " : "", s_indent,
(int) lsum, (int) bb->count);
}
- if (bb != ENTRY_BLOCK_PTR)
+ if (bb != ENTRY_BLOCK_PTR_FOR_FN (fun))
{
sum = 0;
FOR_EACH_EDGE (e, ei, bb->preds)
(flags & TDF_COMMENT) ? ";; " : "", s_indent,
(int) lsum, (int) bb->count);
}
+ if (BB_PARTITION (bb) == BB_COLD_PARTITION)
+ {
+ /* Warn about inconsistencies in the partitioning that are
+ currently caused by profile insanities created via optimization. */
+ if (!probably_never_executed_bb_p (fun, bb))
+ fprintf (file, "%s%sBlock in cold partition with hot count\n",
+ (flags & TDF_COMMENT) ? ";; " : "", s_indent);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (!probably_never_executed_edge_p (fun, e))
+ fprintf (file,
+ "%s%sBlock in cold partition with incoming hot edge\n",
+ (flags & TDF_COMMENT) ? ";; " : "", s_indent);
+ }
+ }
}
\f
void
&& (flags & TDF_SLIM) == 0)
do_details = true;
- /* ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
- Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency. */
if (side->index == ENTRY_BLOCK)
fputs (" ENTRY", file);
else if (side->index == EXIT_BLOCK)
if (e->count && do_details)
{
fputs (" count:", file);
- fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
+ fprintf (file, "%" PRId64, e->count);
}
if (e->flags && do_details)
fputc (')', file);
}
}
+
+DEBUG_FUNCTION void
+debug (edge_def &ref)
+{
+ /* FIXME (crowl): Is this desireable? */
+ dump_edge_info (stderr, &ref, 0, false);
+ dump_edge_info (stderr, &ref, 0, true);
+}
+
+DEBUG_FUNCTION void
+debug (edge_def *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
+}
\f
/* Simple routines to easily allocate AUX fields of basic blocks. */
{
basic_block bb;
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, cfun)
alloc_aux_for_block (bb, size);
}
}
{
basic_block bb;
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, cfun)
bb->aux = NULL;
}
{
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
{
edge e;
edge_iterator ei;
basic_block bb;
edge e;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
DEBUG_FUNCTION basic_block
debug_bb_n (int n)
{
- basic_block bb = BASIC_BLOCK (n);
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
debug_bb (bb);
return bb;
}
if (flags & TDF_COMMENT)
fputs (";; ", outf);
fprintf (outf, "%sbasic block %d, loop depth %d",
- s_indent, bb->index, bb->loop_depth);
+ s_indent, bb->index, bb_loop_depth (bb));
if (flags & TDF_DETAILS)
{
- fprintf (outf, ", count " HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) bb->count);
+ struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
+ fprintf (outf, ", count " "%" PRId64,
+ (int64_t) bb->count);
fprintf (outf, ", freq %i", bb->frequency);
- if (maybe_hot_bb_p (bb))
+ if (maybe_hot_bb_p (fun, bb))
fputs (", maybe hot", outf);
- if (probably_never_executed_bb_p (bb))
+ if (probably_never_executed_bb_p (fun, bb))
fputs (", probably never executed", outf);
}
fputc ('\n', outf);
- if (TDF_DETAILS)
- check_bb_profile (bb, outf, indent, flags);
if (flags & TDF_DETAILS)
{
+ check_bb_profile (bb, outf, indent, flags);
if (flags & TDF_COMMENT)
fputs (";; ", outf);
fprintf (outf, "%s prev block ", s_indent);
dump_edge_info (outf, e, flags, 0);
fputc ('\n', outf);
}
+ if (first)
+ fputc ('\n', outf);
}
if (do_footer)
dump_edge_info (outf, e, flags, 1);
fputc ('\n', outf);
}
+ if (first)
+ fputc ('\n', outf);
}
}
{
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
dump_bb_info (file, bb, 0,
flags & (TDF_COMMENT | TDF_DETAILS),
/* Compute the probability of TAKEN_EDGE being reached via threaded edge.
Watch for overflows. */
if (bb->frequency)
- prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
+ prob = GCOV_COMPUTE_SCALE (edge_frequency, bb->frequency);
else
prob = 0;
if (prob > taken_edge->probability)
/* numbers smaller than this value are safe to multiply without getting
64bit overflow. */
-#define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
+#define MAX_SAFE_MULTIPLIER (1 << (sizeof (int64_t) * 4 - 1))
/* Multiply all frequencies of basic blocks in array BBS of length NBBS
by NUM/DEN, in gcov_type arithmetic. More accurate than previous
}
}
-/* Data structures used to maintain mapping between basic blocks and
- copies. */
-static htab_t bb_original;
-static htab_t bb_copy;
-
-/* And between loops and copies. */
-static htab_t loop_copy;
-static alloc_pool original_copy_bb_pool;
+/* Helper types for hash tables. */
struct htab_bb_copy_original_entry
{
int index2;
};
-static hashval_t
-bb_copy_original_hash (const void *p)
+struct bb_copy_hasher : nofree_ptr_hash <htab_bb_copy_original_entry>
{
- const struct htab_bb_copy_original_entry *data
- = ((const struct htab_bb_copy_original_entry *)p);
+ static inline hashval_t hash (const htab_bb_copy_original_entry *);
+ static inline bool equal (const htab_bb_copy_original_entry *existing,
+ const htab_bb_copy_original_entry * candidate);
+};
+inline hashval_t
+bb_copy_hasher::hash (const htab_bb_copy_original_entry *data)
+{
return data->index1;
}
-static int
-bb_copy_original_eq (const void *p, const void *q)
-{
- const struct htab_bb_copy_original_entry *data
- = ((const struct htab_bb_copy_original_entry *)p);
- const struct htab_bb_copy_original_entry *data2
- = ((const struct htab_bb_copy_original_entry *)q);
+inline bool
+bb_copy_hasher::equal (const htab_bb_copy_original_entry *data,
+ const htab_bb_copy_original_entry *data2)
+{
return data->index1 == data2->index1;
}
+/* Data structures used to maintain mapping between basic blocks and
+ copies. */
+static hash_table<bb_copy_hasher> *bb_original;
+static hash_table<bb_copy_hasher> *bb_copy;
+
+/* And between loops and copies. */
+static hash_table<bb_copy_hasher> *loop_copy;
+static object_allocator<htab_bb_copy_original_entry> *original_copy_bb_pool;
+
/* Initialize the data structures to maintain mapping between blocks
and its copies. */
void
initialize_original_copy_tables (void)
{
- gcc_assert (!original_copy_bb_pool);
- original_copy_bb_pool
- = create_alloc_pool ("original_copy",
- sizeof (struct htab_bb_copy_original_entry), 10);
- bb_original = htab_create (10, bb_copy_original_hash,
- bb_copy_original_eq, NULL);
- bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
- loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
+ original_copy_bb_pool = new object_allocator<htab_bb_copy_original_entry>
+ ("original_copy");
+ bb_original = new hash_table<bb_copy_hasher> (10);
+ bb_copy = new hash_table<bb_copy_hasher> (10);
+ loop_copy = new hash_table<bb_copy_hasher> (10);
}
/* Free the data structures to maintain mapping between blocks and
free_original_copy_tables (void)
{
gcc_assert (original_copy_bb_pool);
- htab_delete (bb_copy);
- htab_delete (bb_original);
- htab_delete (loop_copy);
- free_alloc_pool (original_copy_bb_pool);
+ delete bb_copy;
+ bb_copy = NULL;
+ delete bb_original;
bb_copy = NULL;
- bb_original = NULL;
+ delete loop_copy;
loop_copy = NULL;
+ delete original_copy_bb_pool;
original_copy_bb_pool = NULL;
}
/* Removes the value associated with OBJ from table TAB. */
static void
-copy_original_table_clear (htab_t tab, unsigned obj)
+copy_original_table_clear (hash_table<bb_copy_hasher> *tab, unsigned obj)
{
- void **slot;
+ htab_bb_copy_original_entry **slot;
struct htab_bb_copy_original_entry key, *elt;
if (!original_copy_bb_pool)
return;
key.index1 = obj;
- slot = htab_find_slot (tab, &key, NO_INSERT);
+ slot = tab->find_slot (&key, NO_INSERT);
if (!slot)
return;
- elt = (struct htab_bb_copy_original_entry *) *slot;
- htab_clear_slot (tab, slot);
- pool_free (original_copy_bb_pool, elt);
+ elt = *slot;
+ tab->clear_slot (slot);
+ original_copy_bb_pool->remove (elt);
}
/* Sets the value associated with OBJ in table TAB to VAL.
Do nothing when data structures are not initialized. */
static void
-copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
+copy_original_table_set (hash_table<bb_copy_hasher> *tab,
+ unsigned obj, unsigned val)
{
struct htab_bb_copy_original_entry **slot;
struct htab_bb_copy_original_entry key;
return;
key.index1 = obj;
- slot = (struct htab_bb_copy_original_entry **)
- htab_find_slot (tab, &key, INSERT);
+ slot = tab->find_slot (&key, INSERT);
if (!*slot)
{
- *slot = (struct htab_bb_copy_original_entry *)
- pool_alloc (original_copy_bb_pool);
+ *slot = original_copy_bb_pool->allocate ();
(*slot)->index1 = obj;
}
(*slot)->index2 = val;
gcc_assert (original_copy_bb_pool);
key.index1 = bb->index;
- entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
+ entry = bb_original->find (&key);
if (entry)
- return BASIC_BLOCK (entry->index2);
+ return BASIC_BLOCK_FOR_FN (cfun, entry->index2);
else
return NULL;
}
gcc_assert (original_copy_bb_pool);
key.index1 = bb->index;
- entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
+ entry = bb_copy->find (&key);
if (entry)
- return BASIC_BLOCK (entry->index2);
+ return BASIC_BLOCK_FOR_FN (cfun, entry->index2);
else
return NULL;
}
gcc_assert (original_copy_bb_pool);
key.index1 = loop->num;
- entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
+ entry = loop_copy->find (&key);
if (entry)
- return get_loop (entry->index2);
+ return get_loop (cfun, entry->index2);
else
return NULL;
}