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