+++ /dev/null
-/* Register conflict graph computation routines.
- Copyright (C) 2000 Free Software Foundation, Inc.
- Contributed by CodeSourcery, LLC
-
-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
-version.
-
-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 GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
-
-/* References:
-
- Building an Optimizing Compiler
- Robert Morgan
- Butterworth-Heinemann, 1998 */
-
-#include "config.h"
-#include "system.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
- point in the function at which the regs corresponding to the two
- nodes are both live.
-
- The conflict graph is represented by the data structures described
- in Morgan section 11.3.1. Nodes are not stored explicitly; only
- arcs are. An arc stores the numbers of the regs it connects.
-
- Arcs can be located by two methods:
-
- - The two reg numbers for each arc are hashed into a single
- value, and the arc is placed in a hash table according to this
- value. This permits quick determination of whether a specific
- conflict is present in the graph.
-
- - Additionally, the arc data structures are threaded by a set of
- linked lists by single reg number. Since each arc references
- two regs, there are two next pointers, one for the
- smaller-numbered reg and one for the larger-numbered reg. This
- permits the quick enumeration of conflicts for a single
- register.
-
- Arcs are allocated from an obstack. */
-
-/* An arc in a conflict graph. */
-
-struct conflict_graph_arc_def
-{
- /* The next element of the list of conflicts involving the
- smaller-numbered reg, as an index in the table of arcs of this
- graph. Contains NULL if this is the tail. */
- struct conflict_graph_arc_def *smaller_next;
-
- /* The next element of the list of conflicts involving the
- larger-numbered reg, as an index in the table of arcs of this
- graph. Contains NULL if this is the tail. */
- struct conflict_graph_arc_def *larger_next;
-
- /* The smaller-numbered reg involved in this conflict. */
- int smaller;
-
- /* The larger-numbered reg involved in this conflict. */
- int larger;
-};
-
-typedef struct conflict_graph_arc_def *conflict_graph_arc;
-typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
-
-
-/* A conflict graph. */
-
-struct conflict_graph_def
-{
- /* A hash table of arcs. Used to search for a specific conflict. */
- htab_t arc_hash_table;
-
- /* The number of regs this conflict graph handles. */
- int num_regs;
-
- /* For each reg, the arc at the head of a list that threads through
- all the arcs involving that reg. An entry is NULL if no
- conflicts exist involving that reg. */
- conflict_graph_arc *neighbor_heads;
-
- /* Arcs are allocated from here. */
- struct obstack arc_obstack;
-};
-
-/* The initial capacity (number of conflict arcs) for newly-created
- conflict graphs. */
-#define INITIAL_ARC_CAPACITY 64
-
-
-/* Computes the hash value of the conflict graph arc connecting regs
- 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 *));
-\f
-/* Callback function to compute the hash value of an arc. Uses
- current_graph to locate the graph to which the arc belongs. */
-
-static unsigned
-arc_hash (arcp)
- const void *arcp;
-{
- const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
-
- return CONFLICT_HASH_FN (arc->smaller, arc->larger);
-}
-
-/* Callback function to determine the equality of two arcs in the hash
- table. */
-
-static int
-arc_eq (arcp1, arcp2)
- const void *arcp1;
- const void *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;
-}
-
-/* Creates an empty conflict graph to hold conflicts among NUM_REGS
- registers. */
-
-conflict_graph
-conflict_graph_new (num_regs)
- int num_regs;
-{
- conflict_graph graph
- = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
- graph->num_regs = num_regs;
-
- /* Set up the hash table. No delete action is specified; memory
- management of arcs is through the obstack. */
- graph->arc_hash_table
- = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
-
- /* Create an obstack for allocating arcs. */
- 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));
-
- 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;
-{
- obstack_free (&graph->arc_obstack, NULL);
- htab_delete (graph->arc_hash_table);
- free (graph->neighbor_heads);
- free (graph);
-}
-
-/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
- distinct. Returns non-zero, 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;
-{
- int smaller = MIN (reg1, reg2);
- int larger = MAX (reg1, reg2);
- struct conflict_graph_arc_def dummy;
- conflict_graph_arc arc;
- void **slot;
-
- /* A reg cannot conflict with itself. */
- if (reg1 == reg2)
- abort ();
-
- dummy.smaller = smaller;
- dummy.larger = larger;
- slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
-
- /* If the conflict is already there, do nothing. */
- if (*slot != NULL)
- return 0;
-
- /* Allocate an arc. */
- arc
- = (conflict_graph_arc)
- obstack_alloc (&graph->arc_obstack,
- sizeof (struct conflict_graph_arc_def));
-
- /* Record the reg numbers. */
- arc->smaller = smaller;
- arc->larger = larger;
-
- /* Link the conflict into into two lists, one for each reg. */
- arc->smaller_next = graph->neighbor_heads[smaller];
- graph->neighbor_heads[smaller] = arc;
- arc->larger_next = graph->neighbor_heads[larger];
- graph->neighbor_heads[larger] = arc;
-
- /* Put it in the hash table. */
- *slot = (void *) arc;
-
- return 1;
-}
-
-/* Returns non-zero 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;
-{
- /* Build an arc to search for. */
- struct conflict_graph_arc_def arc;
- arc.smaller = MIN (reg1, reg2);
- arc.larger = MAX (reg1, reg2);
-
- return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
-}
-
-/* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
- 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_arc arc = graph->neighbor_heads[reg];
- while (arc != NULL)
- {
- /* Invoke the callback. */
- if ((*enum_fn) (arc->smaller, arc->larger, extra))
- /* Stop if requested. */
- break;
-
- /* Which next pointer to follow depends on whether REG is the
- smaller or larger reg in this conflict. */
- if (reg < arc->larger)
- arc = arc->smaller_next;
- else
- arc = arc->larger_next;
- }
-}
-
-/* For each conflict between a register x and SRC in GRAPH, adds a
- conflict to GRAPH between x and TARGET. */
-
-void
-conflict_graph_merge_regs (graph, target, src)
- conflict_graph graph;
- int target;
- int src;
-{
- conflict_graph_arc arc = graph->neighbor_heads[src];
-
- if (target == src)
- return;
-
- while (arc != NULL)
- {
- int other = arc->smaller;
-
- if (other == src)
- other = arc->larger;
-
- conflict_graph_add (graph, target, other);
-
- /* Which next pointer to follow depends on whether REG is the
- smaller or larger reg in this conflict. */
- if (src < arc->larger)
- arc = arc->smaller_next;
- else
- arc = arc->larger_next;
- }
-}
-
-/* Holds context information while a conflict graph is being traversed
- for printing. */
-
-struct print_context
-{
- /* The file pointer to which we're printing. */
- FILE *fp;
-
- /* The reg whose conflicts we're printing. */
- int reg;
-
- /* Whether a conflict has already been printed for this reg. */
- int started;
-};
-
-/* Callback function when enumerating conflicts during printing. */
-
-static int
-print_conflict (reg1, reg2, contextp)
- int reg1;
- int reg2;
- void *contextp;
-{
- struct print_context *context = (struct print_context *) contextp;
- int reg;
-
- /* If this is the first conflict printed for this reg, start a new
- line. */
- if (! context->started)
- {
- fprintf (context->fp, " %d:", context->reg);
- context->started = 1;
- }
-
- /* Figure out the reg whose conflicts we're printing. The other reg
- is the interesting one. */
- if (reg1 == context->reg)
- reg = reg2;
- else if (reg2 == context->reg)
- reg = reg1;
- else
- abort ();
-
- /* Print the conflict. */
- fprintf (context->fp, " %d", reg);
-
- /* Continue enumerating. */
- return 0;
-}
-
-/* Prints the conflicts in GRAPH to FP. */
-
-void
-conflict_graph_print (graph, fp)
- conflict_graph graph;
- FILE *fp;
-{
- int reg;
- struct print_context context;
-
- context.fp = fp;
- fprintf (fp, "Conflicts:\n");
-
- /* Loop over registers supported in this graph. */
- for (reg = 0; reg < graph->num_regs; ++reg)
- {
- context.reg = reg;
- context.started = 0;
-
- /* Scan the conflicts for reg, printing as we go. A label for
- this line will be printed the first time a conflict is
- printed for the reg; we won't start a new line if this reg
- has no conflicts. */
- conflict_graph_enum (graph, reg, &print_conflict, &context);
-
- /* If this reg does have conflicts, end the line. */
- if (context.started)
- fputc ('\n', fp);
- }
-}
-
-/* Callback function for note_stores. */
-
-static void
-mark_reg (reg, setter, data)
- rtx reg;
- rtx setter ATTRIBUTE_UNUSED;
- void *data;
-{
- regset set = (regset) data;
-
- if (GET_CODE (reg) == SUBREG)
- reg = SUBREG_REG (reg);
-
- /* We're only interested in regs. */
- if (GET_CODE (reg) != REG)
- return;
-
- SET_REGNO_REG_SET (set, REGNO (reg));
-}
-
-/* Allocates a conflict graph and computes conflicts over the current
- function for the registers set in REGS. The caller is responsible
- for deallocating the return value.
-
- Preconditions: the flow graph must be in SSA form, and life
- analysis (specifically, regs live at exit from each block) must be
- up-to-date.
-
- This algorithm determines conflicts by walking the insns in each
- block backwards. We maintain the set of live regs at each insn,
- starting with the regs live on exit from the block. For each insn:
-
- 1. If a reg is set in this insns, it must be born here, since
- we're in SSA. Therefore, it was not live before this insns,
- so remove it from the set of live regs.
-
- 2. For each reg born in this insn, record a conflict between it
- and every other reg live coming into this insn. For each
- existing conflict, one of the two regs must be born while the
- other is alive. See Morgan or elsewhere for a proof of this.
-
- 3. Regs clobbered by this insn must have been live coming into
- it, so record them as such.
-
- The resulting conflict graph is not built for regs in REGS
- themselves; rather, partition P is used to obtain the canonical reg
- for each of these. The nodes of the conflict graph are these
- canonical regs instead. */
-
-conflict_graph
-conflict_graph_compute (regs, p)
- 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;
-
- INIT_REG_SET (live);
- INIT_REG_SET (born);
-
- for (b = n_basic_blocks; --b >= 0; )
- {
- basic_block bb = BASIC_BLOCK (b);
- rtx insn;
- rtx head;
-
- /* 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))
- {
- int born_reg;
- int live_reg;
- rtx link;
-
- /* Are we interested in this insn? */
- if (INSN_P (insn))
- {
- /* 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 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);
-
- /* Regs born here were not live before this insn. */
- AND_COMPL_REG_SET (live, born);
-
- /* For every reg born here, add a conflict with every other
- reg live coming into this insn. */
- EXECUTE_IF_SET_IN_REG_SET
- (born, FIRST_PSEUDO_REGISTER, born_reg,
- {
- EXECUTE_IF_SET_IN_REG_SET
- (live, FIRST_PSEUDO_REGISTER, live_reg,
- {
- /* Build the conflict graph in terms of canonical
- regnos. */
- int b = partition_find (p, born_reg);
- int l = partition_find (p, live_reg);
-
- if (b != l)
- conflict_graph_add (graph, b, l);
- });
- });
-
- /* Morgan's algorithm checks the operands of the insn
- and adds them to the set of live regs. Instead, we
- use death information added by life analysis. Regs
- dead after this instruction were live before it. */
- for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
- if (REG_NOTE_KIND (link) == REG_DEAD)
- {
- unsigned int regno = REGNO (XEXP (link, 0));
-
- if (REGNO_REG_SET_P (regs, regno))
- SET_REGNO_REG_SET (live, regno);
- }
- }
- }
- }
-
- FREE_REG_SET (live);
- FREE_REG_SET (born);
-
- return graph;
-}
projects / msp430-gcc.git / blobdiff