X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fconflict.c;fp=gcc%2Fconflict.c;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=d1fb1293cf9f142f1bc8020201029bdb56bf389a;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/conflict.c b/gcc/conflict.c deleted file mode 100644 index d1fb1293..00000000 --- a/gcc/conflict.c +++ /dev/null @@ -1,531 +0,0 @@ -/* 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 *)); - -/* 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; -}