/* Register conflict graph computation routines.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2003 Free Software Foundation, Inc.
Contributed by CodeSourcery, LLC
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC 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 version.
+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
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* References:
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "obstack.h"
#include "hashtab.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
-/* Use malloc to allocate obstack chunks. */
-#define obstack_chunk_alloc xmalloc
-#define obstack_chunk_free free
-
/* A register conflict graph is an undirected graph containing nodes
for some or all of the regs used in a function. Arcs represent
conflicts, i.e. two nodes are connected by an arc if there is a
};
typedef struct conflict_graph_arc_def *conflict_graph_arc;
+typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
/* A conflict graph. */
conflicts exist involving that reg. */
conflict_graph_arc *neighbor_heads;
- /* Arcs are allocated from here. */
+ /* Arcs are allocated from here. */
struct obstack arc_obstack;
};
R1 and R2. R1 is assumed to be smaller or equal to R2. */
#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
-static unsigned arc_hash PARAMS ((const void *));
-static int arc_eq PARAMS ((const void *, const void *));
-static int print_conflict PARAMS ((int, int, void *));
-static void mark_reg PARAMS ((rtx, rtx, void *));
+static hashval_t arc_hash (const void *);
+static int arc_eq (const void *, const void *);
+static int print_conflict (int, int, void *);
+static void mark_reg (rtx, rtx, void *);
\f
/* Callback function to compute the hash value of an arc. Uses
- current_graph to locate the graph to which the arc belongs. */
+ current_graph to locate the graph to which the arc belongs. */
-static unsigned
-arc_hash (arcp)
- const void *arcp;
+static hashval_t
+arc_hash (const void *arcp)
{
- conflict_graph_arc arc = (conflict_graph_arc) arcp;
+ const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
return CONFLICT_HASH_FN (arc->smaller, arc->larger);
}
table. */
static int
-arc_eq (arcp1, arcp2)
- const void *arcp1;
- const void *arcp2;
+arc_eq (const void *arcp1, const void *arcp2)
{
- conflict_graph_arc arc1 = (conflict_graph_arc) arcp1;
- conflict_graph_arc arc2 = (conflict_graph_arc) arcp2;
+ const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
+ const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
}
registers. */
conflict_graph
-conflict_graph_new (num_regs)
- int num_regs;
+conflict_graph_new (int num_regs)
{
- conflict_graph graph
- = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
+ conflict_graph graph = xmalloc (sizeof (struct conflict_graph_def));
graph->num_regs = num_regs;
/* Set up the hash table. No delete action is specified; memory
obstack_init (&graph->arc_obstack);
/* Create and zero the lookup table by register number. */
- graph->neighbor_heads
- = (conflict_graph_arc *) xmalloc (num_regs * sizeof (conflict_graph_arc));
+ graph->neighbor_heads = xcalloc (num_regs, sizeof (conflict_graph_arc));
- memset (graph->neighbor_heads, 0, num_regs * sizeof (conflict_graph_arc));
return graph;
}
/* Deletes a conflict graph. */
void
-conflict_graph_delete (graph)
- conflict_graph graph;
+conflict_graph_delete (conflict_graph graph)
{
obstack_free (&graph->arc_obstack, NULL);
htab_delete (graph->arc_hash_table);
}
/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
- distinct. Returns non-zero, unless the conflict is already present
+ distinct. Returns nonzero, unless the conflict is already present
in GRAPH, in which case it does nothing and returns zero. */
int
-conflict_graph_add (graph, reg1, reg2)
- conflict_graph graph;
- int reg1;
- int reg2;
+conflict_graph_add (conflict_graph graph, int reg1, int reg2)
{
int smaller = MIN (reg1, reg2);
int larger = MAX (reg1, reg2);
/* Allocate an arc. */
arc
- = (conflict_graph_arc)
- obstack_alloc (&graph->arc_obstack,
+ = obstack_alloc (&graph->arc_obstack,
sizeof (struct conflict_graph_arc_def));
/* Record the reg numbers. */
return 1;
}
-/* Returns non-zero if a conflict exists in GRAPH between regs REG1
+/* Returns nonzero if a conflict exists in GRAPH between regs REG1
and REG2. */
int
-conflict_graph_conflict_p (graph, reg1, reg2)
- conflict_graph graph;
- int reg1;
- int reg2;
+conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
{
/* Build an arc to search for. */
struct conflict_graph_arc_def arc;
passed back to ENUM_FN. */
void
-conflict_graph_enum (graph, reg, enum_fn, extra)
- conflict_graph graph;
- int reg;
- conflict_graph_enum_fn enum_fn;
- void *extra;
+conflict_graph_enum (conflict_graph graph, int reg,
+ conflict_graph_enum_fn enum_fn, void *extra)
{
conflict_graph_arc arc = graph->neighbor_heads[reg];
while (arc != NULL)
conflict to GRAPH between x and TARGET. */
void
-conflict_graph_merge_regs (graph, target, src)
- conflict_graph graph;
- int target;
- int src;
+conflict_graph_merge_regs (conflict_graph graph, int target, int src)
{
conflict_graph_arc arc = graph->neighbor_heads[src];
/* Callback function when enumerating conflicts during printing. */
static int
-print_conflict (reg1, reg2, contextp)
- int reg1;
- int reg2;
- void *contextp;
+print_conflict (int reg1, int reg2, void *contextp)
{
struct print_context *context = (struct print_context *) contextp;
int reg;
/* Prints the conflicts in GRAPH to FP. */
void
-conflict_graph_print (graph, fp)
- conflict_graph graph;
- FILE *fp;
+conflict_graph_print (conflict_graph graph, FILE *fp)
{
int reg;
struct print_context context;
/* Callback function for note_stores. */
static void
-mark_reg (reg, setter, data)
- rtx reg;
- rtx setter ATTRIBUTE_UNUSED;
- void *data;
+mark_reg (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *data)
{
regset set = (regset) data;
reg = SUBREG_REG (reg);
/* We're only interested in regs. */
- if (GET_CODE (reg) != REG)
+ if (!REG_P (reg))
return;
SET_REGNO_REG_SET (set, REGNO (reg));
canonical regs instead. */
conflict_graph
-conflict_graph_compute (regs, p)
- regset regs;
- partition p;
+conflict_graph_compute (regset regs, partition p)
{
- int b;
conflict_graph graph = conflict_graph_new (max_reg_num ());
+ regset_head live_head;
+ regset live = &live_head;
+ regset_head born_head;
+ regset born = &born_head;
+ basic_block bb;
+
+ INIT_REG_SET (live);
+ INIT_REG_SET (born);
- for (b = n_basic_blocks; --b >= 0; )
+ FOR_EACH_BB_REVERSE (bb)
{
- basic_block bb = BASIC_BLOCK (b);
- regset_head live_head;
- regset live = &live_head;
- regset_head born_head;
- regset born = &born_head;
rtx insn;
rtx head;
- INIT_REG_SET (live);
- INIT_REG_SET (born);
-
/* Start with the regs that are live on exit, limited to those
we're interested in. */
COPY_REG_SET (live, bb->global_live_at_end);
AND_REG_SET (live, regs);
/* Walk the instruction stream backwards. */
- head = bb->head;
- insn = bb->end;
- for (insn = bb->end; insn != head; insn = PREV_INSN (insn))
+ head = BB_HEAD (bb);
+ insn = BB_END (bb);
+ for (insn = BB_END (bb); insn != head; insn = PREV_INSN (insn))
{
int born_reg;
int live_reg;
{
/* Determine which regs are set in this insn. Since
we're in SSA form, if a reg is set here it isn't set
- anywhere elso, so this insn is where the reg is born. */
+ anywhere else, so this insn is where the reg is born. */
CLEAR_REG_SET (born);
note_stores (PATTERN (insn), mark_reg, born);
AND_REG_SET (born, regs);
}
}
+ FREE_REG_SET (live);
+ FREE_REG_SET (born);
+
return graph;
}