conflict.c revision 132718
190075Sobrien/* Register conflict graph computation routines. 2132718Skan Copyright (C) 2000, 2003 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 1990075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2090075Sobrien02111-1307, 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 *); 120132718Skanstatic void mark_reg (rtx, rtx, void *); 12190075Sobrien 12290075Sobrien/* Callback function to compute the hash value of an arc. Uses 12390075Sobrien current_graph to locate the graph to which the arc belongs. */ 12490075Sobrien 125117395Skanstatic hashval_t 126132718Skanarc_hash (const void *arcp) 12790075Sobrien{ 12890075Sobrien const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp; 12990075Sobrien 13090075Sobrien return CONFLICT_HASH_FN (arc->smaller, arc->larger); 13190075Sobrien} 13290075Sobrien 13390075Sobrien/* Callback function to determine the equality of two arcs in the hash 13490075Sobrien table. */ 13590075Sobrien 13690075Sobrienstatic int 137132718Skanarc_eq (const void *arcp1, const void *arcp2) 13890075Sobrien{ 13990075Sobrien const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1; 14090075Sobrien const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2; 14190075Sobrien 14290075Sobrien return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger; 14390075Sobrien} 14490075Sobrien 14590075Sobrien/* Creates an empty conflict graph to hold conflicts among NUM_REGS 14690075Sobrien registers. */ 14790075Sobrien 14890075Sobrienconflict_graph 149132718Skanconflict_graph_new (int num_regs) 15090075Sobrien{ 151132718Skan conflict_graph graph = xmalloc (sizeof (struct conflict_graph_def)); 15290075Sobrien graph->num_regs = num_regs; 15390075Sobrien 15490075Sobrien /* Set up the hash table. No delete action is specified; memory 15590075Sobrien management of arcs is through the obstack. */ 15690075Sobrien graph->arc_hash_table 15790075Sobrien = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL); 15890075Sobrien 15990075Sobrien /* Create an obstack for allocating arcs. */ 16090075Sobrien obstack_init (&graph->arc_obstack); 16190075Sobrien 16290075Sobrien /* Create and zero the lookup table by register number. */ 163132718Skan graph->neighbor_heads = xcalloc (num_regs, sizeof (conflict_graph_arc)); 16490075Sobrien 16590075Sobrien return graph; 16690075Sobrien} 16790075Sobrien 16890075Sobrien/* Deletes a conflict graph. */ 16990075Sobrien 17090075Sobrienvoid 171132718Skanconflict_graph_delete (conflict_graph graph) 17290075Sobrien{ 17390075Sobrien obstack_free (&graph->arc_obstack, NULL); 17490075Sobrien htab_delete (graph->arc_hash_table); 17590075Sobrien free (graph->neighbor_heads); 17690075Sobrien free (graph); 17790075Sobrien} 17890075Sobrien 17990075Sobrien/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be 180117395Skan distinct. Returns nonzero, unless the conflict is already present 18190075Sobrien in GRAPH, in which case it does nothing and returns zero. */ 18290075Sobrien 18390075Sobrienint 184132718Skanconflict_graph_add (conflict_graph graph, int reg1, int reg2) 18590075Sobrien{ 18690075Sobrien int smaller = MIN (reg1, reg2); 18790075Sobrien int larger = MAX (reg1, reg2); 18890075Sobrien struct conflict_graph_arc_def dummy; 18990075Sobrien conflict_graph_arc arc; 19090075Sobrien void **slot; 19190075Sobrien 19290075Sobrien /* A reg cannot conflict with itself. */ 19390075Sobrien if (reg1 == reg2) 19490075Sobrien abort (); 19590075Sobrien 19690075Sobrien dummy.smaller = smaller; 19790075Sobrien dummy.larger = larger; 19890075Sobrien slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT); 19990075Sobrien 20090075Sobrien /* If the conflict is already there, do nothing. */ 20190075Sobrien if (*slot != NULL) 20290075Sobrien return 0; 20390075Sobrien 20490075Sobrien /* Allocate an arc. */ 20590075Sobrien arc 206132718Skan = obstack_alloc (&graph->arc_obstack, 20790075Sobrien sizeof (struct conflict_graph_arc_def)); 20890075Sobrien 20990075Sobrien /* Record the reg numbers. */ 21090075Sobrien arc->smaller = smaller; 21190075Sobrien arc->larger = larger; 21290075Sobrien 21390075Sobrien /* Link the conflict into into two lists, one for each reg. */ 21490075Sobrien arc->smaller_next = graph->neighbor_heads[smaller]; 21590075Sobrien graph->neighbor_heads[smaller] = arc; 21690075Sobrien arc->larger_next = graph->neighbor_heads[larger]; 21790075Sobrien graph->neighbor_heads[larger] = arc; 21890075Sobrien 21990075Sobrien /* Put it in the hash table. */ 22090075Sobrien *slot = (void *) arc; 22190075Sobrien 22290075Sobrien return 1; 22390075Sobrien} 22490075Sobrien 225117395Skan/* Returns nonzero if a conflict exists in GRAPH between regs REG1 22690075Sobrien and REG2. */ 22790075Sobrien 22890075Sobrienint 229132718Skanconflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2) 23090075Sobrien{ 23190075Sobrien /* Build an arc to search for. */ 23290075Sobrien struct conflict_graph_arc_def arc; 23390075Sobrien arc.smaller = MIN (reg1, reg2); 23490075Sobrien arc.larger = MAX (reg1, reg2); 23590075Sobrien 23690075Sobrien return htab_find (graph->arc_hash_table, (void *) &arc) != NULL; 23790075Sobrien} 23890075Sobrien 23990075Sobrien/* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is 24090075Sobrien passed back to ENUM_FN. */ 24190075Sobrien 24290075Sobrienvoid 243132718Skanconflict_graph_enum (conflict_graph graph, int reg, 244132718Skan conflict_graph_enum_fn enum_fn, void *extra) 24590075Sobrien{ 24690075Sobrien conflict_graph_arc arc = graph->neighbor_heads[reg]; 24790075Sobrien while (arc != NULL) 24890075Sobrien { 24990075Sobrien /* Invoke the callback. */ 25090075Sobrien if ((*enum_fn) (arc->smaller, arc->larger, extra)) 25190075Sobrien /* Stop if requested. */ 25290075Sobrien break; 25390075Sobrien 25490075Sobrien /* Which next pointer to follow depends on whether REG is the 25590075Sobrien smaller or larger reg in this conflict. */ 25690075Sobrien if (reg < arc->larger) 25790075Sobrien arc = arc->smaller_next; 25890075Sobrien else 25990075Sobrien arc = arc->larger_next; 26090075Sobrien } 26190075Sobrien} 26290075Sobrien 26390075Sobrien/* For each conflict between a register x and SRC in GRAPH, adds a 26490075Sobrien conflict to GRAPH between x and TARGET. */ 26590075Sobrien 26690075Sobrienvoid 267132718Skanconflict_graph_merge_regs (conflict_graph graph, int target, int src) 26890075Sobrien{ 26990075Sobrien conflict_graph_arc arc = graph->neighbor_heads[src]; 27090075Sobrien 27190075Sobrien if (target == src) 27290075Sobrien return; 27390075Sobrien 27490075Sobrien while (arc != NULL) 27590075Sobrien { 27690075Sobrien int other = arc->smaller; 27790075Sobrien 27890075Sobrien if (other == src) 27990075Sobrien other = arc->larger; 28090075Sobrien 28190075Sobrien conflict_graph_add (graph, target, other); 28290075Sobrien 28390075Sobrien /* Which next pointer to follow depends on whether REG is the 28490075Sobrien smaller or larger reg in this conflict. */ 28590075Sobrien if (src < arc->larger) 28690075Sobrien arc = arc->smaller_next; 28790075Sobrien else 28890075Sobrien arc = arc->larger_next; 28990075Sobrien } 29090075Sobrien} 29190075Sobrien 29290075Sobrien/* Holds context information while a conflict graph is being traversed 29390075Sobrien for printing. */ 29490075Sobrien 29590075Sobrienstruct print_context 29690075Sobrien{ 29790075Sobrien /* The file pointer to which we're printing. */ 29890075Sobrien FILE *fp; 29990075Sobrien 30090075Sobrien /* The reg whose conflicts we're printing. */ 30190075Sobrien int reg; 30290075Sobrien 30390075Sobrien /* Whether a conflict has already been printed for this reg. */ 30490075Sobrien int started; 30590075Sobrien}; 30690075Sobrien 30790075Sobrien/* Callback function when enumerating conflicts during printing. */ 30890075Sobrien 30990075Sobrienstatic int 310132718Skanprint_conflict (int reg1, int reg2, void *contextp) 31190075Sobrien{ 31290075Sobrien struct print_context *context = (struct print_context *) contextp; 31390075Sobrien int reg; 31490075Sobrien 31590075Sobrien /* If this is the first conflict printed for this reg, start a new 31690075Sobrien line. */ 31790075Sobrien if (! context->started) 31890075Sobrien { 31990075Sobrien fprintf (context->fp, " %d:", context->reg); 32090075Sobrien context->started = 1; 32190075Sobrien } 32290075Sobrien 32390075Sobrien /* Figure out the reg whose conflicts we're printing. The other reg 32490075Sobrien is the interesting one. */ 32590075Sobrien if (reg1 == context->reg) 32690075Sobrien reg = reg2; 32790075Sobrien else if (reg2 == context->reg) 32890075Sobrien reg = reg1; 32990075Sobrien else 33090075Sobrien abort (); 33190075Sobrien 33290075Sobrien /* Print the conflict. */ 33390075Sobrien fprintf (context->fp, " %d", reg); 33490075Sobrien 33590075Sobrien /* Continue enumerating. */ 33690075Sobrien return 0; 33790075Sobrien} 33890075Sobrien 33990075Sobrien/* Prints the conflicts in GRAPH to FP. */ 34090075Sobrien 34190075Sobrienvoid 342132718Skanconflict_graph_print (conflict_graph graph, FILE *fp) 34390075Sobrien{ 34490075Sobrien int reg; 34590075Sobrien struct print_context context; 34690075Sobrien 34790075Sobrien context.fp = fp; 34890075Sobrien fprintf (fp, "Conflicts:\n"); 34990075Sobrien 35090075Sobrien /* Loop over registers supported in this graph. */ 35190075Sobrien for (reg = 0; reg < graph->num_regs; ++reg) 35290075Sobrien { 35390075Sobrien context.reg = reg; 35490075Sobrien context.started = 0; 35590075Sobrien 35690075Sobrien /* Scan the conflicts for reg, printing as we go. A label for 35790075Sobrien this line will be printed the first time a conflict is 35890075Sobrien printed for the reg; we won't start a new line if this reg 35990075Sobrien has no conflicts. */ 36090075Sobrien conflict_graph_enum (graph, reg, &print_conflict, &context); 36190075Sobrien 36290075Sobrien /* If this reg does have conflicts, end the line. */ 36390075Sobrien if (context.started) 36490075Sobrien fputc ('\n', fp); 36590075Sobrien } 36690075Sobrien} 36790075Sobrien 36890075Sobrien/* Callback function for note_stores. */ 36990075Sobrien 37090075Sobrienstatic void 371132718Skanmark_reg (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *data) 37290075Sobrien{ 37390075Sobrien regset set = (regset) data; 37490075Sobrien 37590075Sobrien if (GET_CODE (reg) == SUBREG) 37690075Sobrien reg = SUBREG_REG (reg); 37790075Sobrien 37890075Sobrien /* We're only interested in regs. */ 37990075Sobrien if (GET_CODE (reg) != REG) 38090075Sobrien return; 38190075Sobrien 38290075Sobrien SET_REGNO_REG_SET (set, REGNO (reg)); 38390075Sobrien} 38490075Sobrien 38590075Sobrien/* Allocates a conflict graph and computes conflicts over the current 38690075Sobrien function for the registers set in REGS. The caller is responsible 38790075Sobrien for deallocating the return value. 38890075Sobrien 38990075Sobrien Preconditions: the flow graph must be in SSA form, and life 39090075Sobrien analysis (specifically, regs live at exit from each block) must be 39190075Sobrien up-to-date. 39290075Sobrien 39390075Sobrien This algorithm determines conflicts by walking the insns in each 39490075Sobrien block backwards. We maintain the set of live regs at each insn, 39590075Sobrien starting with the regs live on exit from the block. For each insn: 39690075Sobrien 39790075Sobrien 1. If a reg is set in this insns, it must be born here, since 39890075Sobrien we're in SSA. Therefore, it was not live before this insns, 39990075Sobrien so remove it from the set of live regs. 40090075Sobrien 40190075Sobrien 2. For each reg born in this insn, record a conflict between it 40290075Sobrien and every other reg live coming into this insn. For each 40390075Sobrien existing conflict, one of the two regs must be born while the 40490075Sobrien other is alive. See Morgan or elsewhere for a proof of this. 40590075Sobrien 40690075Sobrien 3. Regs clobbered by this insn must have been live coming into 40790075Sobrien it, so record them as such. 40890075Sobrien 40990075Sobrien The resulting conflict graph is not built for regs in REGS 41090075Sobrien themselves; rather, partition P is used to obtain the canonical reg 41190075Sobrien for each of these. The nodes of the conflict graph are these 41290075Sobrien canonical regs instead. */ 41390075Sobrien 41490075Sobrienconflict_graph 415132718Skanconflict_graph_compute (regset regs, partition p) 41690075Sobrien{ 41790075Sobrien conflict_graph graph = conflict_graph_new (max_reg_num ()); 41890075Sobrien regset_head live_head; 41990075Sobrien regset live = &live_head; 42090075Sobrien regset_head born_head; 42190075Sobrien regset born = &born_head; 422117395Skan basic_block bb; 42390075Sobrien 42490075Sobrien INIT_REG_SET (live); 42590075Sobrien INIT_REG_SET (born); 42690075Sobrien 427117395Skan FOR_EACH_BB_REVERSE (bb) 42890075Sobrien { 42990075Sobrien rtx insn; 43090075Sobrien rtx head; 43190075Sobrien 43290075Sobrien /* Start with the regs that are live on exit, limited to those 43390075Sobrien we're interested in. */ 43490075Sobrien COPY_REG_SET (live, bb->global_live_at_end); 43590075Sobrien AND_REG_SET (live, regs); 43690075Sobrien 43790075Sobrien /* Walk the instruction stream backwards. */ 438132718Skan head = BB_HEAD (bb); 439132718Skan insn = BB_END (bb); 440132718Skan for (insn = BB_END (bb); insn != head; insn = PREV_INSN (insn)) 44190075Sobrien { 44290075Sobrien int born_reg; 44390075Sobrien int live_reg; 44490075Sobrien rtx link; 44590075Sobrien 44690075Sobrien /* Are we interested in this insn? */ 44790075Sobrien if (INSN_P (insn)) 44890075Sobrien { 44990075Sobrien /* Determine which regs are set in this insn. Since 45090075Sobrien we're in SSA form, if a reg is set here it isn't set 45190075Sobrien anywhere else, so this insn is where the reg is born. */ 45290075Sobrien CLEAR_REG_SET (born); 45390075Sobrien note_stores (PATTERN (insn), mark_reg, born); 45490075Sobrien AND_REG_SET (born, regs); 45590075Sobrien 45690075Sobrien /* Regs born here were not live before this insn. */ 45790075Sobrien AND_COMPL_REG_SET (live, born); 45890075Sobrien 45990075Sobrien /* For every reg born here, add a conflict with every other 46090075Sobrien reg live coming into this insn. */ 46190075Sobrien EXECUTE_IF_SET_IN_REG_SET 46290075Sobrien (born, FIRST_PSEUDO_REGISTER, born_reg, 46390075Sobrien { 46490075Sobrien EXECUTE_IF_SET_IN_REG_SET 46590075Sobrien (live, FIRST_PSEUDO_REGISTER, live_reg, 46690075Sobrien { 46790075Sobrien /* Build the conflict graph in terms of canonical 46890075Sobrien regnos. */ 46990075Sobrien int b = partition_find (p, born_reg); 47090075Sobrien int l = partition_find (p, live_reg); 47190075Sobrien 47290075Sobrien if (b != l) 47390075Sobrien conflict_graph_add (graph, b, l); 47490075Sobrien }); 47590075Sobrien }); 47690075Sobrien 47790075Sobrien /* Morgan's algorithm checks the operands of the insn 47890075Sobrien and adds them to the set of live regs. Instead, we 47990075Sobrien use death information added by life analysis. Regs 48090075Sobrien dead after this instruction were live before it. */ 48190075Sobrien for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 48290075Sobrien if (REG_NOTE_KIND (link) == REG_DEAD) 48390075Sobrien { 48490075Sobrien unsigned int regno = REGNO (XEXP (link, 0)); 48590075Sobrien 48690075Sobrien if (REGNO_REG_SET_P (regs, regno)) 48790075Sobrien SET_REGNO_REG_SET (live, regno); 48890075Sobrien } 48990075Sobrien } 49090075Sobrien } 49190075Sobrien } 49290075Sobrien 49390075Sobrien FREE_REG_SET (live); 49490075Sobrien FREE_REG_SET (born); 49590075Sobrien 49690075Sobrien return graph; 49790075Sobrien} 498