conflict.c revision 117395
1/* Register conflict graph computation routines. 2 Copyright (C) 2000 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, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, 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 "obstack.h" 31#include "hashtab.h" 32#include "rtl.h" 33#include "hard-reg-set.h" 34#include "basic-block.h" 35 36/* A register conflict graph is an undirected graph containing nodes 37 for some or all of the regs used in a function. Arcs represent 38 conflicts, i.e. two nodes are connected by an arc if there is a 39 point in the function at which the regs corresponding to the two 40 nodes are both live. 41 42 The conflict graph is represented by the data structures described 43 in Morgan section 11.3.1. Nodes are not stored explicitly; only 44 arcs are. An arc stores the numbers of the regs it connects. 45 46 Arcs can be located by two methods: 47 48 - The two reg numbers for each arc are hashed into a single 49 value, and the arc is placed in a hash table according to this 50 value. This permits quick determination of whether a specific 51 conflict is present in the graph. 52 53 - Additionally, the arc data structures are threaded by a set of 54 linked lists by single reg number. Since each arc references 55 two regs, there are two next pointers, one for the 56 smaller-numbered reg and one for the larger-numbered reg. This 57 permits the quick enumeration of conflicts for a single 58 register. 59 60 Arcs are allocated from an obstack. */ 61 62/* An arc in a conflict graph. */ 63 64struct conflict_graph_arc_def 65{ 66 /* The next element of the list of conflicts involving the 67 smaller-numbered reg, as an index in the table of arcs of this 68 graph. Contains NULL if this is the tail. */ 69 struct conflict_graph_arc_def *smaller_next; 70 71 /* The next element of the list of conflicts involving the 72 larger-numbered reg, as an index in the table of arcs of this 73 graph. Contains NULL if this is the tail. */ 74 struct conflict_graph_arc_def *larger_next; 75 76 /* The smaller-numbered reg involved in this conflict. */ 77 int smaller; 78 79 /* The larger-numbered reg involved in this conflict. */ 80 int larger; 81}; 82 83typedef struct conflict_graph_arc_def *conflict_graph_arc; 84typedef const struct conflict_graph_arc_def *const_conflict_graph_arc; 85 86 87/* A conflict graph. */ 88 89struct conflict_graph_def 90{ 91 /* A hash table of arcs. Used to search for a specific conflict. */ 92 htab_t arc_hash_table; 93 94 /* The number of regs this conflict graph handles. */ 95 int num_regs; 96 97 /* For each reg, the arc at the head of a list that threads through 98 all the arcs involving that reg. An entry is NULL if no 99 conflicts exist involving that reg. */ 100 conflict_graph_arc *neighbor_heads; 101 102 /* Arcs are allocated from here. */ 103 struct obstack arc_obstack; 104}; 105 106/* The initial capacity (number of conflict arcs) for newly-created 107 conflict graphs. */ 108#define INITIAL_ARC_CAPACITY 64 109 110 111/* Computes the hash value of the conflict graph arc connecting regs 112 R1 and R2. R1 is assumed to be smaller or equal to R2. */ 113#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) 114 115static hashval_t arc_hash PARAMS ((const void *)); 116static int arc_eq PARAMS ((const void *, const void *)); 117static int print_conflict PARAMS ((int, int, void *)); 118static void mark_reg PARAMS ((rtx, rtx, void *)); 119 120/* Callback function to compute the hash value of an arc. Uses 121 current_graph to locate the graph to which the arc belongs. */ 122 123static hashval_t 124arc_hash (arcp) 125 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 (arcp1, arcp2) 137 const void *arcp1; 138 const void *arcp2; 139{ 140 const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1; 141 const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2; 142 143 return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger; 144} 145 146/* Creates an empty conflict graph to hold conflicts among NUM_REGS 147 registers. */ 148 149conflict_graph 150conflict_graph_new (num_regs) 151 int num_regs; 152{ 153 conflict_graph graph 154 = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def)); 155 graph->num_regs = num_regs; 156 157 /* Set up the hash table. No delete action is specified; memory 158 management of arcs is through the obstack. */ 159 graph->arc_hash_table 160 = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL); 161 162 /* Create an obstack for allocating arcs. */ 163 obstack_init (&graph->arc_obstack); 164 165 /* Create and zero the lookup table by register number. */ 166 graph->neighbor_heads 167 = (conflict_graph_arc *) xmalloc (num_regs * sizeof (conflict_graph_arc)); 168 169 memset (graph->neighbor_heads, 0, num_regs * sizeof (conflict_graph_arc)); 170 return graph; 171} 172 173/* Deletes a conflict graph. */ 174 175void 176conflict_graph_delete (graph) 177 conflict_graph graph; 178{ 179 obstack_free (&graph->arc_obstack, NULL); 180 htab_delete (graph->arc_hash_table); 181 free (graph->neighbor_heads); 182 free (graph); 183} 184 185/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be 186 distinct. Returns nonzero, unless the conflict is already present 187 in GRAPH, in which case it does nothing and returns zero. */ 188 189int 190conflict_graph_add (graph, reg1, reg2) 191 conflict_graph graph; 192 int reg1; 193 int reg2; 194{ 195 int smaller = MIN (reg1, reg2); 196 int larger = MAX (reg1, reg2); 197 struct conflict_graph_arc_def dummy; 198 conflict_graph_arc arc; 199 void **slot; 200 201 /* A reg cannot conflict with itself. */ 202 if (reg1 == reg2) 203 abort (); 204 205 dummy.smaller = smaller; 206 dummy.larger = larger; 207 slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT); 208 209 /* If the conflict is already there, do nothing. */ 210 if (*slot != NULL) 211 return 0; 212 213 /* Allocate an arc. */ 214 arc 215 = (conflict_graph_arc) 216 obstack_alloc (&graph->arc_obstack, 217 sizeof (struct conflict_graph_arc_def)); 218 219 /* Record the reg numbers. */ 220 arc->smaller = smaller; 221 arc->larger = larger; 222 223 /* Link the conflict into into two lists, one for each reg. */ 224 arc->smaller_next = graph->neighbor_heads[smaller]; 225 graph->neighbor_heads[smaller] = arc; 226 arc->larger_next = graph->neighbor_heads[larger]; 227 graph->neighbor_heads[larger] = arc; 228 229 /* Put it in the hash table. */ 230 *slot = (void *) arc; 231 232 return 1; 233} 234 235/* Returns nonzero if a conflict exists in GRAPH between regs REG1 236 and REG2. */ 237 238int 239conflict_graph_conflict_p (graph, reg1, reg2) 240 conflict_graph graph; 241 int reg1; 242 int reg2; 243{ 244 /* Build an arc to search for. */ 245 struct conflict_graph_arc_def arc; 246 arc.smaller = MIN (reg1, reg2); 247 arc.larger = MAX (reg1, reg2); 248 249 return htab_find (graph->arc_hash_table, (void *) &arc) != NULL; 250} 251 252/* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is 253 passed back to ENUM_FN. */ 254 255void 256conflict_graph_enum (graph, reg, enum_fn, extra) 257 conflict_graph graph; 258 int reg; 259 conflict_graph_enum_fn enum_fn; 260 void *extra; 261{ 262 conflict_graph_arc arc = graph->neighbor_heads[reg]; 263 while (arc != NULL) 264 { 265 /* Invoke the callback. */ 266 if ((*enum_fn) (arc->smaller, arc->larger, extra)) 267 /* Stop if requested. */ 268 break; 269 270 /* Which next pointer to follow depends on whether REG is the 271 smaller or larger reg in this conflict. */ 272 if (reg < arc->larger) 273 arc = arc->smaller_next; 274 else 275 arc = arc->larger_next; 276 } 277} 278 279/* For each conflict between a register x and SRC in GRAPH, adds a 280 conflict to GRAPH between x and TARGET. */ 281 282void 283conflict_graph_merge_regs (graph, target, src) 284 conflict_graph graph; 285 int target; 286 int src; 287{ 288 conflict_graph_arc arc = graph->neighbor_heads[src]; 289 290 if (target == src) 291 return; 292 293 while (arc != NULL) 294 { 295 int other = arc->smaller; 296 297 if (other == src) 298 other = arc->larger; 299 300 conflict_graph_add (graph, target, other); 301 302 /* Which next pointer to follow depends on whether REG is the 303 smaller or larger reg in this conflict. */ 304 if (src < arc->larger) 305 arc = arc->smaller_next; 306 else 307 arc = arc->larger_next; 308 } 309} 310 311/* Holds context information while a conflict graph is being traversed 312 for printing. */ 313 314struct print_context 315{ 316 /* The file pointer to which we're printing. */ 317 FILE *fp; 318 319 /* The reg whose conflicts we're printing. */ 320 int reg; 321 322 /* Whether a conflict has already been printed for this reg. */ 323 int started; 324}; 325 326/* Callback function when enumerating conflicts during printing. */ 327 328static int 329print_conflict (reg1, reg2, contextp) 330 int reg1; 331 int reg2; 332 void *contextp; 333{ 334 struct print_context *context = (struct print_context *) contextp; 335 int reg; 336 337 /* If this is the first conflict printed for this reg, start a new 338 line. */ 339 if (! context->started) 340 { 341 fprintf (context->fp, " %d:", context->reg); 342 context->started = 1; 343 } 344 345 /* Figure out the reg whose conflicts we're printing. The other reg 346 is the interesting one. */ 347 if (reg1 == context->reg) 348 reg = reg2; 349 else if (reg2 == context->reg) 350 reg = reg1; 351 else 352 abort (); 353 354 /* Print the conflict. */ 355 fprintf (context->fp, " %d", reg); 356 357 /* Continue enumerating. */ 358 return 0; 359} 360 361/* Prints the conflicts in GRAPH to FP. */ 362 363void 364conflict_graph_print (graph, fp) 365 conflict_graph graph; 366 FILE *fp; 367{ 368 int reg; 369 struct print_context context; 370 371 context.fp = fp; 372 fprintf (fp, "Conflicts:\n"); 373 374 /* Loop over registers supported in this graph. */ 375 for (reg = 0; reg < graph->num_regs; ++reg) 376 { 377 context.reg = reg; 378 context.started = 0; 379 380 /* Scan the conflicts for reg, printing as we go. A label for 381 this line will be printed the first time a conflict is 382 printed for the reg; we won't start a new line if this reg 383 has no conflicts. */ 384 conflict_graph_enum (graph, reg, &print_conflict, &context); 385 386 /* If this reg does have conflicts, end the line. */ 387 if (context.started) 388 fputc ('\n', fp); 389 } 390} 391 392/* Callback function for note_stores. */ 393 394static void 395mark_reg (reg, setter, data) 396 rtx reg; 397 rtx setter ATTRIBUTE_UNUSED; 398 void *data; 399{ 400 regset set = (regset) data; 401 402 if (GET_CODE (reg) == SUBREG) 403 reg = SUBREG_REG (reg); 404 405 /* We're only interested in regs. */ 406 if (GET_CODE (reg) != REG) 407 return; 408 409 SET_REGNO_REG_SET (set, REGNO (reg)); 410} 411 412/* Allocates a conflict graph and computes conflicts over the current 413 function for the registers set in REGS. The caller is responsible 414 for deallocating the return value. 415 416 Preconditions: the flow graph must be in SSA form, and life 417 analysis (specifically, regs live at exit from each block) must be 418 up-to-date. 419 420 This algorithm determines conflicts by walking the insns in each 421 block backwards. We maintain the set of live regs at each insn, 422 starting with the regs live on exit from the block. For each insn: 423 424 1. If a reg is set in this insns, it must be born here, since 425 we're in SSA. Therefore, it was not live before this insns, 426 so remove it from the set of live regs. 427 428 2. For each reg born in this insn, record a conflict between it 429 and every other reg live coming into this insn. For each 430 existing conflict, one of the two regs must be born while the 431 other is alive. See Morgan or elsewhere for a proof of this. 432 433 3. Regs clobbered by this insn must have been live coming into 434 it, so record them as such. 435 436 The resulting conflict graph is not built for regs in REGS 437 themselves; rather, partition P is used to obtain the canonical reg 438 for each of these. The nodes of the conflict graph are these 439 canonical regs instead. */ 440 441conflict_graph 442conflict_graph_compute (regs, p) 443 regset regs; 444 partition p; 445{ 446 conflict_graph graph = conflict_graph_new (max_reg_num ()); 447 regset_head live_head; 448 regset live = &live_head; 449 regset_head born_head; 450 regset born = &born_head; 451 basic_block bb; 452 453 INIT_REG_SET (live); 454 INIT_REG_SET (born); 455 456 FOR_EACH_BB_REVERSE (bb) 457 { 458 rtx insn; 459 rtx head; 460 461 /* Start with the regs that are live on exit, limited to those 462 we're interested in. */ 463 COPY_REG_SET (live, bb->global_live_at_end); 464 AND_REG_SET (live, regs); 465 466 /* Walk the instruction stream backwards. */ 467 head = bb->head; 468 insn = bb->end; 469 for (insn = bb->end; insn != head; insn = PREV_INSN (insn)) 470 { 471 int born_reg; 472 int live_reg; 473 rtx link; 474 475 /* Are we interested in this insn? */ 476 if (INSN_P (insn)) 477 { 478 /* Determine which regs are set in this insn. Since 479 we're in SSA form, if a reg is set here it isn't set 480 anywhere else, so this insn is where the reg is born. */ 481 CLEAR_REG_SET (born); 482 note_stores (PATTERN (insn), mark_reg, born); 483 AND_REG_SET (born, regs); 484 485 /* Regs born here were not live before this insn. */ 486 AND_COMPL_REG_SET (live, born); 487 488 /* For every reg born here, add a conflict with every other 489 reg live coming into this insn. */ 490 EXECUTE_IF_SET_IN_REG_SET 491 (born, FIRST_PSEUDO_REGISTER, born_reg, 492 { 493 EXECUTE_IF_SET_IN_REG_SET 494 (live, FIRST_PSEUDO_REGISTER, live_reg, 495 { 496 /* Build the conflict graph in terms of canonical 497 regnos. */ 498 int b = partition_find (p, born_reg); 499 int l = partition_find (p, live_reg); 500 501 if (b != l) 502 conflict_graph_add (graph, b, l); 503 }); 504 }); 505 506 /* Morgan's algorithm checks the operands of the insn 507 and adds them to the set of live regs. Instead, we 508 use death information added by life analysis. Regs 509 dead after this instruction were live before it. */ 510 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 511 if (REG_NOTE_KIND (link) == REG_DEAD) 512 { 513 unsigned int regno = REGNO (XEXP (link, 0)); 514 515 if (REGNO_REG_SET_P (regs, regno)) 516 SET_REGNO_REG_SET (live, regno); 517 } 518 } 519 } 520 } 521 522 FREE_REG_SET (live); 523 FREE_REG_SET (born); 524 525 return graph; 526} 527