190075Sobrien/* Register conflict graph computation routines. 2169689Skan Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc. 390075Sobrien Contributed by CodeSourcery, LLC 490075Sobrien 590075SobrienThis file is part of GCC. 690075Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1190075Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1690075Sobrien 1790075SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2190075Sobrien 2290075Sobrien/* References: 2390075Sobrien 2490075Sobrien Building an Optimizing Compiler 2590075Sobrien Robert Morgan 2690075Sobrien Butterworth-Heinemann, 1998 */ 2790075Sobrien 2890075Sobrien#include "config.h" 2990075Sobrien#include "system.h" 30132718Skan#include "coretypes.h" 31132718Skan#include "tm.h" 3290075Sobrien#include "obstack.h" 3390075Sobrien#include "hashtab.h" 3490075Sobrien#include "rtl.h" 3590075Sobrien#include "hard-reg-set.h" 3690075Sobrien#include "basic-block.h" 3790075Sobrien 3890075Sobrien/* A register conflict graph is an undirected graph containing nodes 3990075Sobrien for some or all of the regs used in a function. Arcs represent 4090075Sobrien conflicts, i.e. two nodes are connected by an arc if there is a 4190075Sobrien point in the function at which the regs corresponding to the two 4290075Sobrien nodes are both live. 4390075Sobrien 4490075Sobrien The conflict graph is represented by the data structures described 4590075Sobrien in Morgan section 11.3.1. Nodes are not stored explicitly; only 4690075Sobrien arcs are. An arc stores the numbers of the regs it connects. 4790075Sobrien 4890075Sobrien Arcs can be located by two methods: 4990075Sobrien 5090075Sobrien - The two reg numbers for each arc are hashed into a single 5190075Sobrien value, and the arc is placed in a hash table according to this 5290075Sobrien value. This permits quick determination of whether a specific 5390075Sobrien conflict is present in the graph. 5490075Sobrien 5590075Sobrien - Additionally, the arc data structures are threaded by a set of 5690075Sobrien linked lists by single reg number. Since each arc references 5790075Sobrien two regs, there are two next pointers, one for the 5890075Sobrien smaller-numbered reg and one for the larger-numbered reg. This 5990075Sobrien permits the quick enumeration of conflicts for a single 6090075Sobrien register. 6190075Sobrien 6290075Sobrien Arcs are allocated from an obstack. */ 6390075Sobrien 6490075Sobrien/* An arc in a conflict graph. */ 6590075Sobrien 6690075Sobrienstruct conflict_graph_arc_def 6790075Sobrien{ 6890075Sobrien /* The next element of the list of conflicts involving the 6990075Sobrien smaller-numbered reg, as an index in the table of arcs of this 7090075Sobrien graph. Contains NULL if this is the tail. */ 7190075Sobrien struct conflict_graph_arc_def *smaller_next; 7290075Sobrien 7390075Sobrien /* The next element of the list of conflicts involving the 7490075Sobrien larger-numbered reg, as an index in the table of arcs of this 7590075Sobrien graph. Contains NULL if this is the tail. */ 7690075Sobrien struct conflict_graph_arc_def *larger_next; 7790075Sobrien 7890075Sobrien /* The smaller-numbered reg involved in this conflict. */ 7990075Sobrien int smaller; 8090075Sobrien 8190075Sobrien /* The larger-numbered reg involved in this conflict. */ 8290075Sobrien int larger; 8390075Sobrien}; 8490075Sobrien 8590075Sobrientypedef struct conflict_graph_arc_def *conflict_graph_arc; 8690075Sobrientypedef const struct conflict_graph_arc_def *const_conflict_graph_arc; 8790075Sobrien 8890075Sobrien 8990075Sobrien/* A conflict graph. */ 9090075Sobrien 9190075Sobrienstruct conflict_graph_def 9290075Sobrien{ 9390075Sobrien /* A hash table of arcs. Used to search for a specific conflict. */ 9490075Sobrien htab_t arc_hash_table; 9590075Sobrien 9690075Sobrien /* The number of regs this conflict graph handles. */ 9790075Sobrien int num_regs; 9890075Sobrien 9990075Sobrien /* For each reg, the arc at the head of a list that threads through 10090075Sobrien all the arcs involving that reg. An entry is NULL if no 10190075Sobrien conflicts exist involving that reg. */ 10290075Sobrien conflict_graph_arc *neighbor_heads; 10390075Sobrien 10490075Sobrien /* Arcs are allocated from here. */ 10590075Sobrien struct obstack arc_obstack; 10690075Sobrien}; 10790075Sobrien 10890075Sobrien/* The initial capacity (number of conflict arcs) for newly-created 10990075Sobrien conflict graphs. */ 11090075Sobrien#define INITIAL_ARC_CAPACITY 64 11190075Sobrien 11290075Sobrien 11390075Sobrien/* Computes the hash value of the conflict graph arc connecting regs 11490075Sobrien R1 and R2. R1 is assumed to be smaller or equal to R2. */ 11590075Sobrien#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) 11690075Sobrien 117132718Skanstatic hashval_t arc_hash (const void *); 118132718Skanstatic int arc_eq (const void *, const void *); 119132718Skanstatic int print_conflict (int, int, void *); 12090075Sobrien 12190075Sobrien/* Callback function to compute the hash value of an arc. Uses 12290075Sobrien current_graph to locate the graph to which the arc belongs. */ 12390075Sobrien 124117395Skanstatic hashval_t 125132718Skanarc_hash (const void *arcp) 12690075Sobrien{ 12790075Sobrien const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp; 12890075Sobrien 12990075Sobrien return CONFLICT_HASH_FN (arc->smaller, arc->larger); 13090075Sobrien} 13190075Sobrien 13290075Sobrien/* Callback function to determine the equality of two arcs in the hash 13390075Sobrien table. */ 13490075Sobrien 13590075Sobrienstatic int 136132718Skanarc_eq (const void *arcp1, const void *arcp2) 13790075Sobrien{ 13890075Sobrien const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1; 13990075Sobrien const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2; 14090075Sobrien 14190075Sobrien return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger; 14290075Sobrien} 14390075Sobrien 14490075Sobrien/* Creates an empty conflict graph to hold conflicts among NUM_REGS 14590075Sobrien registers. */ 14690075Sobrien 14790075Sobrienconflict_graph 148132718Skanconflict_graph_new (int num_regs) 14990075Sobrien{ 150169689Skan conflict_graph graph = XNEW (struct conflict_graph_def); 15190075Sobrien graph->num_regs = num_regs; 15290075Sobrien 15390075Sobrien /* Set up the hash table. No delete action is specified; memory 15490075Sobrien management of arcs is through the obstack. */ 15590075Sobrien graph->arc_hash_table 15690075Sobrien = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL); 15790075Sobrien 15890075Sobrien /* Create an obstack for allocating arcs. */ 15990075Sobrien obstack_init (&graph->arc_obstack); 16090075Sobrien 16190075Sobrien /* Create and zero the lookup table by register number. */ 162169689Skan graph->neighbor_heads = XCNEWVEC (conflict_graph_arc, num_regs); 16390075Sobrien 16490075Sobrien return graph; 16590075Sobrien} 16690075Sobrien 16790075Sobrien/* Deletes a conflict graph. */ 16890075Sobrien 16990075Sobrienvoid 170132718Skanconflict_graph_delete (conflict_graph graph) 17190075Sobrien{ 17290075Sobrien obstack_free (&graph->arc_obstack, NULL); 17390075Sobrien htab_delete (graph->arc_hash_table); 17490075Sobrien free (graph->neighbor_heads); 17590075Sobrien free (graph); 17690075Sobrien} 17790075Sobrien 17890075Sobrien/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be 179117395Skan distinct. Returns nonzero, unless the conflict is already present 18090075Sobrien in GRAPH, in which case it does nothing and returns zero. */ 18190075Sobrien 18290075Sobrienint 183132718Skanconflict_graph_add (conflict_graph graph, int reg1, int reg2) 18490075Sobrien{ 18590075Sobrien int smaller = MIN (reg1, reg2); 18690075Sobrien int larger = MAX (reg1, reg2); 18790075Sobrien struct conflict_graph_arc_def dummy; 18890075Sobrien conflict_graph_arc arc; 18990075Sobrien void **slot; 19090075Sobrien 19190075Sobrien /* A reg cannot conflict with itself. */ 192169689Skan gcc_assert (reg1 != reg2); 19390075Sobrien 19490075Sobrien dummy.smaller = smaller; 19590075Sobrien dummy.larger = larger; 19690075Sobrien slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT); 19790075Sobrien 19890075Sobrien /* If the conflict is already there, do nothing. */ 19990075Sobrien if (*slot != NULL) 20090075Sobrien return 0; 20190075Sobrien 20290075Sobrien /* Allocate an arc. */ 20390075Sobrien arc 204132718Skan = obstack_alloc (&graph->arc_obstack, 20590075Sobrien sizeof (struct conflict_graph_arc_def)); 20690075Sobrien 20790075Sobrien /* Record the reg numbers. */ 20890075Sobrien arc->smaller = smaller; 20990075Sobrien arc->larger = larger; 21090075Sobrien 211169689Skan /* Link the conflict into two lists, one for each reg. */ 21290075Sobrien arc->smaller_next = graph->neighbor_heads[smaller]; 21390075Sobrien graph->neighbor_heads[smaller] = arc; 21490075Sobrien arc->larger_next = graph->neighbor_heads[larger]; 21590075Sobrien graph->neighbor_heads[larger] = arc; 21690075Sobrien 21790075Sobrien /* Put it in the hash table. */ 21890075Sobrien *slot = (void *) arc; 21990075Sobrien 22090075Sobrien return 1; 22190075Sobrien} 22290075Sobrien 223117395Skan/* Returns nonzero if a conflict exists in GRAPH between regs REG1 22490075Sobrien and REG2. */ 22590075Sobrien 22690075Sobrienint 227132718Skanconflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2) 22890075Sobrien{ 22990075Sobrien /* Build an arc to search for. */ 23090075Sobrien struct conflict_graph_arc_def arc; 23190075Sobrien arc.smaller = MIN (reg1, reg2); 23290075Sobrien arc.larger = MAX (reg1, reg2); 23390075Sobrien 23490075Sobrien return htab_find (graph->arc_hash_table, (void *) &arc) != NULL; 23590075Sobrien} 23690075Sobrien 23790075Sobrien/* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is 23890075Sobrien passed back to ENUM_FN. */ 23990075Sobrien 24090075Sobrienvoid 241132718Skanconflict_graph_enum (conflict_graph graph, int reg, 242132718Skan conflict_graph_enum_fn enum_fn, void *extra) 24390075Sobrien{ 24490075Sobrien conflict_graph_arc arc = graph->neighbor_heads[reg]; 24590075Sobrien while (arc != NULL) 24690075Sobrien { 24790075Sobrien /* Invoke the callback. */ 24890075Sobrien if ((*enum_fn) (arc->smaller, arc->larger, extra)) 24990075Sobrien /* Stop if requested. */ 25090075Sobrien break; 25190075Sobrien 25290075Sobrien /* Which next pointer to follow depends on whether REG is the 25390075Sobrien smaller or larger reg in this conflict. */ 25490075Sobrien if (reg < arc->larger) 25590075Sobrien arc = arc->smaller_next; 25690075Sobrien else 25790075Sobrien arc = arc->larger_next; 25890075Sobrien } 25990075Sobrien} 26090075Sobrien 26190075Sobrien/* For each conflict between a register x and SRC in GRAPH, adds a 26290075Sobrien conflict to GRAPH between x and TARGET. */ 26390075Sobrien 26490075Sobrienvoid 265132718Skanconflict_graph_merge_regs (conflict_graph graph, int target, int src) 26690075Sobrien{ 26790075Sobrien conflict_graph_arc arc = graph->neighbor_heads[src]; 26890075Sobrien 26990075Sobrien if (target == src) 27090075Sobrien return; 27190075Sobrien 27290075Sobrien while (arc != NULL) 27390075Sobrien { 27490075Sobrien int other = arc->smaller; 27590075Sobrien 27690075Sobrien if (other == src) 27790075Sobrien other = arc->larger; 27890075Sobrien 27990075Sobrien conflict_graph_add (graph, target, other); 28090075Sobrien 28190075Sobrien /* Which next pointer to follow depends on whether REG is the 28290075Sobrien smaller or larger reg in this conflict. */ 28390075Sobrien if (src < arc->larger) 28490075Sobrien arc = arc->smaller_next; 28590075Sobrien else 28690075Sobrien arc = arc->larger_next; 28790075Sobrien } 28890075Sobrien} 28990075Sobrien 29090075Sobrien/* Holds context information while a conflict graph is being traversed 29190075Sobrien for printing. */ 29290075Sobrien 29390075Sobrienstruct print_context 29490075Sobrien{ 29590075Sobrien /* The file pointer to which we're printing. */ 29690075Sobrien FILE *fp; 29790075Sobrien 29890075Sobrien /* The reg whose conflicts we're printing. */ 29990075Sobrien int reg; 30090075Sobrien 30190075Sobrien /* Whether a conflict has already been printed for this reg. */ 30290075Sobrien int started; 30390075Sobrien}; 30490075Sobrien 30590075Sobrien/* Callback function when enumerating conflicts during printing. */ 30690075Sobrien 30790075Sobrienstatic int 308132718Skanprint_conflict (int reg1, int reg2, void *contextp) 30990075Sobrien{ 31090075Sobrien struct print_context *context = (struct print_context *) contextp; 31190075Sobrien int reg; 31290075Sobrien 31390075Sobrien /* If this is the first conflict printed for this reg, start a new 31490075Sobrien line. */ 31590075Sobrien if (! context->started) 31690075Sobrien { 31790075Sobrien fprintf (context->fp, " %d:", context->reg); 31890075Sobrien context->started = 1; 31990075Sobrien } 32090075Sobrien 32190075Sobrien /* Figure out the reg whose conflicts we're printing. The other reg 32290075Sobrien is the interesting one. */ 32390075Sobrien if (reg1 == context->reg) 32490075Sobrien reg = reg2; 32590075Sobrien else 326169689Skan { 327169689Skan gcc_assert (reg2 == context->reg); 328169689Skan reg = reg1; 329169689Skan } 33090075Sobrien 33190075Sobrien /* Print the conflict. */ 33290075Sobrien fprintf (context->fp, " %d", reg); 33390075Sobrien 33490075Sobrien /* Continue enumerating. */ 33590075Sobrien return 0; 33690075Sobrien} 33790075Sobrien 33890075Sobrien/* Prints the conflicts in GRAPH to FP. */ 33990075Sobrien 34090075Sobrienvoid 341132718Skanconflict_graph_print (conflict_graph graph, FILE *fp) 34290075Sobrien{ 34390075Sobrien int reg; 34490075Sobrien struct print_context context; 34590075Sobrien 34690075Sobrien context.fp = fp; 34790075Sobrien fprintf (fp, "Conflicts:\n"); 34890075Sobrien 34990075Sobrien /* Loop over registers supported in this graph. */ 35090075Sobrien for (reg = 0; reg < graph->num_regs; ++reg) 35190075Sobrien { 35290075Sobrien context.reg = reg; 35390075Sobrien context.started = 0; 35490075Sobrien 35590075Sobrien /* Scan the conflicts for reg, printing as we go. A label for 35690075Sobrien this line will be printed the first time a conflict is 35790075Sobrien printed for the reg; we won't start a new line if this reg 35890075Sobrien has no conflicts. */ 35990075Sobrien conflict_graph_enum (graph, reg, &print_conflict, &context); 36090075Sobrien 36190075Sobrien /* If this reg does have conflicts, end the line. */ 36290075Sobrien if (context.started) 36390075Sobrien fputc ('\n', fp); 36490075Sobrien } 36590075Sobrien} 366