/* 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
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This file contains low level functions to manipulate the CFG and
analyze it. All other modules should not transform the data structure
#include "output.h"
#include "function.h"
#include "except.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "tm_p.h"
#include "obstack.h"
#include "ggc.h"
#include "hashtab.h"
#include "alloc-pool.h"
+#include "df.h"
#include "cfgloop.h"
+#include "tree-flow.h"
/* The obstack on which the flow graph components are allocated. */
/* Called once at initialization time. */
void
-init_flow (void)
+init_flow (struct function *the_fun)
{
- if (!cfun->cfg)
- cfun->cfg = GGC_CNEW (struct control_flow_graph);
- n_edges = 0;
- ENTRY_BLOCK_PTR = GGC_CNEW (struct basic_block_def);
- ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
- EXIT_BLOCK_PTR = GGC_CNEW (struct basic_block_def);
- EXIT_BLOCK_PTR->index = EXIT_BLOCK;
- ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
- EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
+ 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);
}
\f
/* Helper function for remove_edge and clear_edges. Frees edge structure
alloc_block (void)
{
basic_block bb;
- bb = GGC_CNEW (struct basic_block_def);
+ bb = ggc_alloc_cleared_basic_block_def ();
return bb;
}
compact_blocks (void)
{
int i;
- basic_block bb;
SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
- i = NUM_FIXED_BLOCKS;
- FOR_EACH_BB (bb)
+ if (df)
+ df_compact_blocks ();
+ else
{
- SET_BASIC_BLOCK (i, bb);
- bb->index = i;
- i++;
- }
-
- gcc_assert (i == n_basic_blocks);
+ basic_block bb;
- for (; i < last_basic_block; i++)
- SET_BASIC_BLOCK (i, NULL);
+ i = NUM_FIXED_BLOCKS;
+ FOR_EACH_BB (bb)
+ {
+ SET_BASIC_BLOCK (i, bb);
+ bb->index = i;
+ i++;
+ }
+ gcc_assert (i == n_basic_blocks);
+ for (; i < last_basic_block; i++)
+ SET_BASIC_BLOCK (i, NULL);
+ }
last_basic_block = n_basic_blocks;
}
connect_src (edge e)
{
VEC_safe_push (edge, gc, e->src->succs, e);
+ df_mark_solutions_dirty ();
}
/* Connect E to E->dest. */
basic_block dest = e->dest;
VEC_safe_push (edge, gc, dest->preds, e);
e->dest_idx = EDGE_COUNT (dest->preds) - 1;
+ df_mark_solutions_dirty ();
}
/* Disconnect edge E from E->src. */
ei_next (&ei);
}
+ df_mark_solutions_dirty ();
gcc_unreachable ();
}
to update dest_idx of the edge that moved into the "hole". */
if (dest_idx < EDGE_COUNT (dest->preds))
EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
+ df_mark_solutions_dirty ();
}
/* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
unchecked_make_edge (basic_block src, basic_block dst, int flags)
{
edge e;
- e = GGC_CNEW (struct edge_def);
+ e = ggc_alloc_cleared_edge_def ();
n_edges++;
e->src = src;
connect_dest (e);
execute_on_growing_pred (e);
-
return e;
}
/* This function will remove an edge from the flow graph. */
void
-remove_edge (edge e)
+remove_edge_raw (edge e)
{
remove_predictions_associated_with_edge (e);
execute_on_shrinking_pred (e);
disconnect_src (e);
disconnect_dest (e);
+ /* This is probably not needed, but it doesn't hurt. */
+ redirect_edge_var_map_clear (e);
+
free_edge (e);
}
s->probability = REG_BR_PROB_BASE;
s->count += e->count;
remove_edge (e);
+ redirect_edge_var_map_dup (s, e);
e = s;
}
else
connect_src (e);
}
-/* Clear all basic block flags, with the exception of partitioning. */
+/* Clear all basic block flags, with the exception of partitioning and
+ setjmp_target. */
void
clear_bb_flags (void)
{
basic_block bb;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
- bb->flags = (BB_PARTITION (bb) | (bb->flags & BB_DISABLE_SCHEDULE)
- | (bb->flags & BB_RTL));
+ bb->flags = (BB_PARTITION (bb)
+ | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
}
\f
/* Check the consistency of profile information. We can't do that
}
}
\f
+/* Write information about registers and basic blocks into FILE.
+ This is part of making a debugging dump. */
+
+void
+dump_regset (regset r, FILE *outf)
+{
+ unsigned i;
+ reg_set_iterator rsi;
+
+ if (r == NULL)
+ {
+ fputs (" (nil)", outf);
+ return;
+ }
+
+ EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
+ {
+ fprintf (outf, " %d", i);
+ if (i < FIRST_PSEUDO_REGISTER)
+ fprintf (outf, " [%s]",
+ reg_names[i]);
+ }
+}
+
+/* Print a human-readable representation of R on the standard error
+ stream. This function is designed to be used from within the
+ debugger. */
+
+DEBUG_FUNCTION void
+debug_regset (regset r)
+{
+ dump_regset (r, stderr);
+ putc ('\n', stderr);
+}
+
/* Emit basic block information for BB. HEADER is true if the user wants
the generic information and the predecessors, FOOTER is true if they want
the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
fprintf (file, ", freq %i", bb->frequency);
- if (maybe_hot_bb_p (bb))
- fprintf (file, ", maybe hot");
- if (probably_never_executed_bb_p (bb))
- fprintf (file, ", probably never executed");
- fprintf (file, ".\n");
+ /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
+ crash without cfun. */
+ if (cfun && maybe_hot_bb_p (bb))
+ fputs (", maybe hot", file);
+ if (cfun && probably_never_executed_bb_p (bb))
+ fputs (", probably never executed", file);
+ fputs (".\n", file);
fprintf (file, "%sPredecessors: ", prefix);
FOR_EACH_EDGE (e, ei, bb->preds)
dump_edge_info (file, e, 0);
+
+ if ((flags & TDF_DETAILS)
+ && (bb->flags & BB_RTL)
+ && df)
+ {
+ putc ('\n', file);
+ df_dump_top (bb, file);
+ }
}
if (footer)
fprintf (file, "\n%sSuccessors: ", prefix);
FOR_EACH_EDGE (e, ei, bb->succs)
dump_edge_info (file, e, 1);
- }
- if ((flags & TDF_DETAILS)
- && (bb->flags & BB_RTL))
- {
- if (bb->il.rtl->global_live_at_start && header)
+ if ((flags & TDF_DETAILS)
+ && (bb->flags & BB_RTL)
+ && df)
{
- fprintf (file, "\n%sRegisters live at start:", prefix);
- dump_regset (bb->il.rtl->global_live_at_start, file);
+ putc ('\n', file);
+ df_dump_bottom (bb, file);
}
+ }
+
+ putc ('\n', file);
+}
- if (bb->il.rtl->global_live_at_end && footer)
+/* Dump the register info to FILE. */
+
+void
+dump_reg_info (FILE *file)
+{
+ unsigned int i, max = max_reg_num ();
+ if (reload_completed)
+ return;
+
+ if (reg_info_p_size < max)
+ max = reg_info_p_size;
+
+ fprintf (file, "%d registers.\n", max);
+ for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
+ {
+ enum reg_class rclass, altclass;
+
+ if (regstat_n_sets_and_refs)
+ fprintf (file, "\nRegister %d used %d times across %d insns",
+ i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
+ else if (df)
+ fprintf (file, "\nRegister %d used %d times across %d insns",
+ i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
+
+ if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
+ fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
+ if (regstat_n_sets_and_refs)
+ fprintf (file, "; set %d time%s", REG_N_SETS (i),
+ (REG_N_SETS (i) == 1) ? "" : "s");
+ else if (df)
+ fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
+ (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
+ if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
+ fputs ("; user var", file);
+ if (REG_N_DEATHS (i) != 1)
+ fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
+ if (REG_N_CALLS_CROSSED (i) == 1)
+ fputs ("; crosses 1 call", file);
+ else if (REG_N_CALLS_CROSSED (i))
+ fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
+ if (REG_FREQ_CALLS_CROSSED (i))
+ fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
+ if (regno_reg_rtx[i] != NULL
+ && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
+ fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
+
+ rclass = reg_preferred_class (i);
+ altclass = reg_alternate_class (i);
+ if (rclass != GENERAL_REGS || altclass != ALL_REGS)
{
- fprintf (file, "\n%sRegisters live at end:", prefix);
- dump_regset (bb->il.rtl->global_live_at_end, file);
+ if (altclass == ALL_REGS || rclass == ALL_REGS)
+ fprintf (file, "; pref %s", reg_class_names[(int) rclass]);
+ else if (altclass == NO_REGS)
+ fprintf (file, "; %s or none", reg_class_names[(int) rclass]);
+ else
+ fprintf (file, "; pref %s, else %s",
+ reg_class_names[(int) rclass],
+ reg_class_names[(int) altclass]);
}
- }
- putc ('\n', file);
+ if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
+ fputs ("; pointer", file);
+ fputs (".\n", file);
+ }
}
+
void
dump_flow_info (FILE *file, int flags)
{
basic_block bb;
/* There are no pseudo registers after reload. Don't dump them. */
- if (reg_n_info && !reload_completed
- && (flags & TDF_DETAILS) != 0)
- {
- unsigned int i, max = max_reg_num ();
- fprintf (file, "%d registers.\n", max);
- for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
- if (REG_N_REFS (i))
- {
- enum reg_class prefclass, altclass;
-
- fprintf (file, "\nRegister %d used %d times across %d insns",
- i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
- if (REG_BASIC_BLOCK (i) >= 0)
- fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
- if (REG_N_SETS (i))
- fprintf (file, "; set %d time%s", REG_N_SETS (i),
- (REG_N_SETS (i) == 1) ? "" : "s");
- if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
- fprintf (file, "; user var");
- if (REG_N_DEATHS (i) != 1)
- fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
- if (REG_N_CALLS_CROSSED (i) == 1)
- fprintf (file, "; crosses 1 call");
- else if (REG_N_CALLS_CROSSED (i))
- fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
- if (regno_reg_rtx[i] != NULL
- && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
- fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
-
- prefclass = reg_preferred_class (i);
- altclass = reg_alternate_class (i);
- if (prefclass != GENERAL_REGS || altclass != ALL_REGS)
- {
- if (altclass == ALL_REGS || prefclass == ALL_REGS)
- fprintf (file, "; pref %s", reg_class_names[(int) prefclass]);
- else if (altclass == NO_REGS)
- fprintf (file, "; %s or none", reg_class_names[(int) prefclass]);
- else
- fprintf (file, "; pref %s, else %s",
- reg_class_names[(int) prefclass],
- reg_class_names[(int) altclass]);
- }
-
- if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
- fprintf (file, "; pointer");
- fprintf (file, ".\n");
- }
- }
+ if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
+ dump_reg_info (file);
fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
- FOR_EACH_BB (bb)
+ FOR_ALL_BB (bb)
{
dump_bb_info (bb, true, true, flags, "", file);
check_bb_profile (bb, file);
putc ('\n', file);
}
-void
+DEBUG_FUNCTION void
debug_flow_info (void)
{
dump_flow_info (stderr, TDF_DETAILS);
dump_edge_info (FILE *file, edge e, int do_succ)
{
basic_block side = (do_succ ? e->dest : e->src);
-
- if (side == ENTRY_BLOCK_PTR)
+ /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
+ if (cfun && side == ENTRY_BLOCK_PTR)
fputs (" ENTRY", file);
- else if (side == EXIT_BLOCK_PTR)
+ else if (cfun && side == EXIT_BLOCK_PTR)
fputs (" EXIT", file);
else
fprintf (file, " %d", side->index);
if (e->count)
{
- fprintf (file, " count:");
+ fputs (" count:", file);
fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
}
/* Allocate a memory block of SIZE as BB->aux. The obstack must
be first initialized by alloc_aux_for_blocks. */
-inline void
+static void
alloc_aux_for_block (basic_block bb, int size)
{
/* Verify that aux field is clear. */
{
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ FOR_ALL_BB (bb)
alloc_aux_for_block (bb, size);
}
}
{
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ FOR_ALL_BB (bb)
bb->aux = NULL;
}
/* Allocate a memory edge of SIZE as BB->aux. The obstack must
be first initialized by alloc_aux_for_edges. */
-inline void
+static void
alloc_aux_for_edge (edge e, int size)
{
/* Verify that aux field is clear. */
clear_aux_for_edges ();
}
-void
+DEBUG_FUNCTION void
debug_bb (basic_block bb)
{
dump_bb (bb, stderr, 0);
}
-basic_block
+DEBUG_FUNCTION basic_block
debug_bb_n (int n)
{
basic_block bb = BASIC_BLOCK (n);
bool first = true;
static const char * const bb_bitnames[] =
{
- "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
+ "new", "reachable", "irreducible_loop", "superblock",
+ "nosched", "hot", "cold", "dup", "xlabel", "rtl",
+ "fwdr", "nothrd"
};
const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
edge e;
if (bb->flags & (1 << i))
{
if (first)
- fprintf (file, " (");
+ fputs (" (", file);
else
- fprintf (file, ", ");
+ fputs (", ", file);
first = false;
- fprintf (file, bb_bitnames[i]);
+ fputs (bb_bitnames[i], file);
}
if (!first)
- fprintf (file, ")");
- fprintf (file, "\n");
+ putc (')', file);
+ putc ('\n', file);
- fprintf (file, "Predecessors: ");
+ fputs ("Predecessors: ", file);
FOR_EACH_EDGE (e, ei, bb->preds)
dump_edge_info (file, e, 0);
fprintf (file, "\nSuccessors: ");
FOR_EACH_EDGE (e, ei, bb->succs)
dump_edge_info (file, e, 1);
- fprintf (file, "\n\n");
+ fputs ("\n\n", file);
}
/* Dumps a brief description of cfg to FILE. */
FOR_EACH_EDGE (c, ei, bb->succs)
{
- c->probability = RDIV (c->probability * scale, 65536);
- if (c->probability > REG_BR_PROB_BASE)
+ /* Protect from overflow due to additional scaling. */
+ if (c->probability > prob)
c->probability = REG_BR_PROB_BASE;
+ else
+ {
+ c->probability = RDIV (c->probability * scale, 65536);
+ if (c->probability > REG_BR_PROB_BASE)
+ c->probability = REG_BR_PROB_BASE;
+ }
}
}
static hashval_t
bb_copy_original_hash (const void *p)
{
- struct htab_bb_copy_original_entry *data
- = ((struct htab_bb_copy_original_entry *)p);
+ const struct htab_bb_copy_original_entry *data
+ = ((const struct htab_bb_copy_original_entry *)p);
return data->index1;
}
static int
bb_copy_original_eq (const void *p, const void *q)
{
- struct htab_bb_copy_original_entry *data
- = ((struct htab_bb_copy_original_entry *)p);
- struct htab_bb_copy_original_entry *data2
- = ((struct htab_bb_copy_original_entry *)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);
return data->index1 == data2->index1;
}