diff options
author | Alex Samuel <samuel@gcc.gnu.org> | 2000-04-06 21:22:49 +0000 |
---|---|---|
committer | Alex Samuel <samuel@gcc.gnu.org> | 2000-04-06 21:22:49 +0000 |
commit | 4e872036e8a62e1b7c3dbfa54cc7584fd61831b2 (patch) | |
tree | 03b76aa3f87cb424bd3389a8c22d97e1312c57ac /gcc/conflict.c | |
parent | 2c561874133f1756d49d993d7561a802bd8448eb (diff) | |
download | gcc-4e872036e8a62e1b7c3dbfa54cc7584fd61831b2.zip gcc-4e872036e8a62e1b7c3dbfa54cc7584fd61831b2.tar.gz gcc-4e872036e8a62e1b7c3dbfa54cc7584fd61831b2.tar.bz2 |
rtl.h (INSN_P): New macro.
* rtl.h (INSN_P): New macro.
(successor_phi_fn): New typedef.
(for_each_successor_phi): New prototype.
(in_ssa_form): New variable.
(PHI_NODE_P): Likewise.
* flow.c (calculate_global_regs_live): Add to new_live_at_end from
phi nodes in successors.
(mark_used_regs): Add PHI case.
(set_phi_alternative_reg): New function.
(life_analysis): Assert that dead code elimination is not selected
when in SSA form.
* toplev.c (to_ssa_time): New variable.
(from_ssa_time): Likewise.
(compile_file): Zero to_ssa_time and from_ssa_time.
Print time to convert to and from SSA.
(rest_of_compilation): Time convert_to_ssa and convert_from_ssa.
(print_time): Compute percent fraction as integer.
* ssa.c (PHI_NODE_P): Moved to rtl.h.
(convert_to_ssa): Check if we're already in SSA.
Don't eliminate dead code in life_analysis.
Rerun flow and life analysis at bottom.
(eliminate_phi): Use canonical regnos when adding nodes.
(mark_reg_in_phi): New function.
(mark_phi_and_copy_regs): Likewise.
(convert_from_ssa): Rerun life analysis at top.
Use coalesced partition.
Check for removing a phi node at the end of the block.
(compute_coalesced_reg_partition): New function.
(coalesce_regs_in_copies): Likewise.
(coalesce_reg_in_phi): Likewise.
(coalesce_regs_in_sucessor_phi_nodes): Likewise.
(for_each_successor_phi): Likewise.
(rename_context): New struct.
(rename_block): Use a rename_context with rename_insn_1. When
renaming sets of a subreg, emit a copy of the entire reg first.
(rename_insn_1): Treat data as a rename_context *. Save current
insn in set_data.
(rename_set_data): Add field set_insn.
* Makefile.in (HASHTAB_H): Move up in file.
(OBSTACK_H): New macro.
(collect2.o): Use OBSTACK_H in dependencies.
(sdbout.o): Likewise.
(emit-rtl.o): Likewise.
(simplify-rtx.o): Likewise.
(fix-header.o): Likewise.
(OBJS): Add conflict.o.
(conflict.o): New rule.
* basic-block.h: Include partition.h.
(conflict_graph): New typedef.
(conflict_graph_enum_fn): Likewise.
(conflict_graph_new): New prototype.
(conflict_graph_delete): Likewise.
(conflict_graph_add): Likewise.
(conflict_graph_conflict_p): Likewise.
(conflict_graph_enum): Likewise.
(conflict_graph_merge_regs): Likewise.
(conflict_graph_print): Likewise.
(conflict_graph_compute): Likewise.
* conflict.c: New file.
From-SVN: r32979
Diffstat (limited to 'gcc/conflict.c')
-rw-r--r-- | gcc/conflict.c | 535 |
1 files changed, 535 insertions, 0 deletions
diff --git a/gcc/conflict.c b/gcc/conflict.c new file mode 100644 index 0000000..51851a2 --- /dev/null +++ b/gcc/conflict.c @@ -0,0 +1,535 @@ +/* Register conflict graph computation routines. + Copyright (C) 2000 Free Software Foundation, Inc. + Contributed by CodeSourcery, LLC + + This file is part of GNU CC. + + 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. + + 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. + + 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. */ + +/* 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 "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; + + +/* 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 *arcp)); +static int arc_eq + PARAMS ((const void *arcp1, const void *arcp2)); +static int print_conflict + PARAMS ((int reg1, int reg2, void *contextp)); +static void mark_reg + PARAMS ((rtx reg, rtx setter, void *data)); + + +/* 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; +{ + conflict_graph_arc arc = (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; +{ + conflict_graph_arc arc1 = (conflict_graph_arc) arcp1; + conflict_graph_arc arc2 = (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); + conflict_graph_arc arc; + void **hash_table_slot; + + /* A reg cannot conflict with itself. */ + if (reg1 == reg2) + abort (); + + /* If the conflict is already there, do nothing. + + FIXME: This is a little wastful; it would be faster to look up the + conflict in the hash table, returning it if it exists and + inserting a new entry if it doesn't, all in one operation. This + would save an extra hash lookup. However, the hashtab interface + doesn't really allow this right now. */ + if (conflict_graph_conflict_p (graph, reg1, reg2)) + 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. */ + hash_table_slot = htab_find_slot (graph->arc_hash_table, + (void *) arc, 1); + *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 ()); + + for (b = n_basic_blocks; --b >= 0; ) + { + 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)) + { + 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 elso, so this insn is where the reg is born. */ + CLEAR_REG_SET (born); + note_stores (PATTERN (insn), mark_reg, (void *) born); +#ifdef AUTO_INC_DEC + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == REG_INC) + mark_reg (XEXP (link, 0), NULL_RTX, NULL); +#endif + 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) + { + int regno = REGNO (XEXP (link, 0)); + if (REGNO_REG_SET_P (regs, regno)) + SET_REGNO_REG_SET (live, regno); + } + } + } + } + + return graph; +} + |