1/* Register conflict graph computation routines. 2 Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by CodeSourcery, LLC 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* References: 23 24 Building an Optimizing Compiler 25 Robert Morgan 26 Butterworth-Heinemann, 1998 */ 27 28#include "config.h" 29#include "system.h" 30#include "coretypes.h" 31#include "tm.h" 32#include "obstack.h" 33#include "hashtab.h" 34#include "rtl.h" 35#include "hard-reg-set.h" 36#include "basic-block.h" 37 38/* A register conflict graph is an undirected graph containing nodes 39 for some or all of the regs used in a function. Arcs represent 40 conflicts, i.e. two nodes are connected by an arc if there is a 41 point in the function at which the regs corresponding to the two 42 nodes are both live. 43 44 The conflict graph is represented by the data structures described 45 in Morgan section 11.3.1. Nodes are not stored explicitly; only 46 arcs are. An arc stores the numbers of the regs it connects. 47 48 Arcs can be located by two methods: 49 50 - The two reg numbers for each arc are hashed into a single 51 value, and the arc is placed in a hash table according to this 52 value. This permits quick determination of whether a specific 53 conflict is present in the graph. 54 55 - Additionally, the arc data structures are threaded by a set of 56 linked lists by single reg number. Since each arc references 57 two regs, there are two next pointers, one for the 58 smaller-numbered reg and one for the larger-numbered reg. This 59 permits the quick enumeration of conflicts for a single 60 register. 61 62 Arcs are allocated from an obstack. */ 63 64/* An arc in a conflict graph. */ 65 66struct conflict_graph_arc_def 67{ 68 /* The next element of the list of conflicts involving the 69 smaller-numbered reg, as an index in the table of arcs of this 70 graph. Contains NULL if this is the tail. */ 71 struct conflict_graph_arc_def *smaller_next; 72 73 /* The next element of the list of conflicts involving the 74 larger-numbered reg, as an index in the table of arcs of this 75 graph. Contains NULL if this is the tail. */ 76 struct conflict_graph_arc_def *larger_next; 77 78 /* The smaller-numbered reg involved in this conflict. */ 79 int smaller; 80 81 /* The larger-numbered reg involved in this conflict. */ 82 int larger; 83}; 84 85typedef struct conflict_graph_arc_def *conflict_graph_arc; 86typedef const struct conflict_graph_arc_def *const_conflict_graph_arc; 87 88 89/* A conflict graph. */ 90 91struct conflict_graph_def 92{ 93 /* A hash table of arcs. Used to search for a specific conflict. */ 94 htab_t arc_hash_table; 95 96 /* The number of regs this conflict graph handles. */ 97 int num_regs; 98 99 /* For each reg, the arc at the head of a list that threads through 100 all the arcs involving that reg. An entry is NULL if no 101 conflicts exist involving that reg. */ 102 conflict_graph_arc *neighbor_heads; 103 104 /* Arcs are allocated from here. */ 105 struct obstack arc_obstack; 106}; 107 108/* The initial capacity (number of conflict arcs) for newly-created 109 conflict graphs. */ 110#define INITIAL_ARC_CAPACITY 64 111 112 113/* Computes the hash value of the conflict graph arc connecting regs 114 R1 and R2. R1 is assumed to be smaller or equal to R2. */ 115#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) 116 117static hashval_t arc_hash (const void *); 118static int arc_eq (const void *, const void *); 119static int print_conflict (int, int, void *); 120 121/* Callback function to compute the hash value of an arc. Uses 122 current_graph to locate the graph to which the arc belongs. */ 123 124static hashval_t 125arc_hash (const void *arcp) 126{ 127 const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp; 128 129 return CONFLICT_HASH_FN (arc->smaller, arc->larger); 130} 131 132/* Callback function to determine the equality of two arcs in the hash 133 table. */ 134 135static int 136arc_eq (const void *arcp1, const void *arcp2) 137{ 138 const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1; 139 const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2; 140 141 return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger; 142} 143 144/* Creates an empty conflict graph to hold conflicts among NUM_REGS 145 registers. */ 146 147conflict_graph 148conflict_graph_new (int num_regs) 149{ 150 conflict_graph graph = XNEW (struct conflict_graph_def); 151 graph->num_regs = num_regs; 152 153 /* Set up the hash table. No delete action is specified; memory 154 management of arcs is through the obstack. */ 155 graph->arc_hash_table 156 = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL); 157 158 /* Create an obstack for allocating arcs. */ 159 obstack_init (&graph->arc_obstack); 160 161 /* Create and zero the lookup table by register number. */ 162 graph->neighbor_heads = XCNEWVEC (conflict_graph_arc, num_regs); 163 164 return graph; 165} 166 167/* Deletes a conflict graph. */ 168 169void 170conflict_graph_delete (conflict_graph graph) 171{ 172 obstack_free (&graph->arc_obstack, NULL); 173 htab_delete (graph->arc_hash_table); 174 free (graph->neighbor_heads); 175 free (graph); 176} 177 178/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be 179 distinct. Returns nonzero, unless the conflict is already present 180 in GRAPH, in which case it does nothing and returns zero. */ 181 182int 183conflict_graph_add (conflict_graph graph, int reg1, int reg2) 184{ 185 int smaller = MIN (reg1, reg2); 186 int larger = MAX (reg1, reg2); 187 struct conflict_graph_arc_def dummy; 188 conflict_graph_arc arc; 189 void **slot; 190 191 /* A reg cannot conflict with itself. */ 192 gcc_assert (reg1 != reg2); 193 194 dummy.smaller = smaller; 195 dummy.larger = larger; 196 slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT); 197 198 /* If the conflict is already there, do nothing. */ 199 if (*slot != NULL) 200 return 0; 201 202 /* Allocate an arc. */ 203 arc 204 = obstack_alloc (&graph->arc_obstack, 205 sizeof (struct conflict_graph_arc_def)); 206 207 /* Record the reg numbers. */ 208 arc->smaller = smaller; 209 arc->larger = larger; 210 211 /* Link the conflict into two lists, one for each reg. */ 212 arc->smaller_next = graph->neighbor_heads[smaller]; 213 graph->neighbor_heads[smaller] = arc; 214 arc->larger_next = graph->neighbor_heads[larger]; 215 graph->neighbor_heads[larger] = arc; 216 217 /* Put it in the hash table. */ 218 *slot = (void *) arc; 219 220 return 1; 221} 222 223/* Returns nonzero if a conflict exists in GRAPH between regs REG1 224 and REG2. */ 225 226int 227conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2) 228{ 229 /* Build an arc to search for. */ 230 struct conflict_graph_arc_def arc; 231 arc.smaller = MIN (reg1, reg2); 232 arc.larger = MAX (reg1, reg2); 233 234 return htab_find (graph->arc_hash_table, (void *) &arc) != NULL; 235} 236 237/* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is 238 passed back to ENUM_FN. */ 239 240void 241conflict_graph_enum (conflict_graph graph, int reg, 242 conflict_graph_enum_fn enum_fn, void *extra) 243{ 244 conflict_graph_arc arc = graph->neighbor_heads[reg]; 245 while (arc != NULL) 246 { 247 /* Invoke the callback. */ 248 if ((*enum_fn) (arc->smaller, arc->larger, extra)) 249 /* Stop if requested. */ 250 break; 251 252 /* Which next pointer to follow depends on whether REG is the 253 smaller or larger reg in this conflict. */ 254 if (reg < arc->larger) 255 arc = arc->smaller_next; 256 else 257 arc = arc->larger_next; 258 } 259} 260 261/* For each conflict between a register x and SRC in GRAPH, adds a 262 conflict to GRAPH between x and TARGET. */ 263 264void 265conflict_graph_merge_regs (conflict_graph graph, int target, int src) 266{ 267 conflict_graph_arc arc = graph->neighbor_heads[src]; 268 269 if (target == src) 270 return; 271 272 while (arc != NULL) 273 { 274 int other = arc->smaller; 275 276 if (other == src) 277 other = arc->larger; 278 279 conflict_graph_add (graph, target, other); 280 281 /* Which next pointer to follow depends on whether REG is the 282 smaller or larger reg in this conflict. */ 283 if (src < arc->larger) 284 arc = arc->smaller_next; 285 else 286 arc = arc->larger_next; 287 } 288} 289 290/* Holds context information while a conflict graph is being traversed 291 for printing. */ 292 293struct print_context 294{ 295 /* The file pointer to which we're printing. */ 296 FILE *fp; 297 298 /* The reg whose conflicts we're printing. */ 299 int reg; 300 301 /* Whether a conflict has already been printed for this reg. */ 302 int started; 303}; 304 305/* Callback function when enumerating conflicts during printing. */ 306 307static int 308print_conflict (int reg1, int reg2, void *contextp) 309{ 310 struct print_context *context = (struct print_context *) contextp; 311 int reg; 312 313 /* If this is the first conflict printed for this reg, start a new 314 line. */ 315 if (! context->started) 316 { 317 fprintf (context->fp, " %d:", context->reg); 318 context->started = 1; 319 } 320 321 /* Figure out the reg whose conflicts we're printing. The other reg 322 is the interesting one. */ 323 if (reg1 == context->reg) 324 reg = reg2; 325 else 326 { 327 gcc_assert (reg2 == context->reg); 328 reg = reg1; 329 } 330 331 /* Print the conflict. */ 332 fprintf (context->fp, " %d", reg); 333 334 /* Continue enumerating. */ 335 return 0; 336} 337 338/* Prints the conflicts in GRAPH to FP. */ 339 340void 341conflict_graph_print (conflict_graph graph, FILE *fp) 342{ 343 int reg; 344 struct print_context context; 345 346 context.fp = fp; 347 fprintf (fp, "Conflicts:\n"); 348 349 /* Loop over registers supported in this graph. */ 350 for (reg = 0; reg < graph->num_regs; ++reg) 351 { 352 context.reg = reg; 353 context.started = 0; 354 355 /* Scan the conflicts for reg, printing as we go. A label for 356 this line will be printed the first time a conflict is 357 printed for the reg; we won't start a new line if this reg 358 has no conflicts. */ 359 conflict_graph_enum (graph, reg, &print_conflict, &context); 360 361 /* If this reg does have conflicts, end the line. */ 362 if (context.started) 363 fputc ('\n', fp); 364 } 365} 366