1/* DDG - Data Dependence Graph implementation. 2 Copyright (C) 2004, 2005 3 Free Software Foundation, Inc. 4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING. If not, write to the Free 20Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2102110-1301, USA. */ 22 23 24#include "config.h" 25#include "system.h" 26#include "coretypes.h" 27#include "tm.h" 28#include "toplev.h" 29#include "rtl.h" 30#include "tm_p.h" 31#include "hard-reg-set.h" 32#include "regs.h" 33#include "function.h" 34#include "flags.h" 35#include "insn-config.h" 36#include "insn-attr.h" 37#include "except.h" 38#include "recog.h" 39#include "sched-int.h" 40#include "target.h" 41#include "cfglayout.h" 42#include "cfgloop.h" 43#include "sbitmap.h" 44#include "expr.h" 45#include "bitmap.h" 46#include "df.h" 47#include "ddg.h" 48 49/* A flag indicating that a ddg edge belongs to an SCC or not. */ 50enum edge_flag {NOT_IN_SCC = 0, IN_SCC}; 51 52/* Forward declarations. */ 53static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr); 54static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr); 55static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr); 56static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx); 57static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, 58 dep_type, dep_data_type, int); 59static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, 60 dep_data_type, int, int); 61static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr); 62 63/* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ 64static bool mem_ref_p; 65 66/* Auxiliary function for mem_read_insn_p. */ 67static int 68mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED) 69{ 70 if (MEM_P (*x)) 71 mem_ref_p = true; 72 return 0; 73} 74 75/* Auxiliary function for mem_read_insn_p. */ 76static void 77mark_mem_use_1 (rtx *x, void *data) 78{ 79 for_each_rtx (x, mark_mem_use, data); 80} 81 82/* Returns nonzero if INSN reads from memory. */ 83static bool 84mem_read_insn_p (rtx insn) 85{ 86 mem_ref_p = false; 87 note_uses (&PATTERN (insn), mark_mem_use_1, NULL); 88 return mem_ref_p; 89} 90 91static void 92mark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) 93{ 94 if (MEM_P (loc)) 95 mem_ref_p = true; 96} 97 98/* Returns nonzero if INSN writes to memory. */ 99static bool 100mem_write_insn_p (rtx insn) 101{ 102 mem_ref_p = false; 103 note_stores (PATTERN (insn), mark_mem_store, NULL); 104 return mem_ref_p; 105} 106 107/* Returns nonzero if X has access to memory. */ 108static bool 109rtx_mem_access_p (rtx x) 110{ 111 int i, j; 112 const char *fmt; 113 enum rtx_code code; 114 115 if (x == 0) 116 return false; 117 118 if (MEM_P (x)) 119 return true; 120 121 code = GET_CODE (x); 122 fmt = GET_RTX_FORMAT (code); 123 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 124 { 125 if (fmt[i] == 'e') 126 { 127 if (rtx_mem_access_p (XEXP (x, i))) 128 return true; 129 } 130 else if (fmt[i] == 'E') 131 for (j = 0; j < XVECLEN (x, i); j++) 132 { 133 if (rtx_mem_access_p (XVECEXP (x, i, j))) 134 return true; 135 } 136 } 137 return false; 138} 139 140/* Returns nonzero if INSN reads to or writes from memory. */ 141static bool 142mem_access_insn_p (rtx insn) 143{ 144 return rtx_mem_access_p (PATTERN (insn)); 145} 146 147/* Computes the dependence parameters (latency, distance etc.), creates 148 a ddg_edge and adds it to the given DDG. */ 149static void 150create_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node, 151 ddg_node_ptr dest_node, rtx link) 152{ 153 ddg_edge_ptr e; 154 int latency, distance = 0; 155 int interloop = (src_node->cuid >= dest_node->cuid); 156 dep_type t = TRUE_DEP; 157 dep_data_type dt = (mem_access_insn_p (src_node->insn) 158 && mem_access_insn_p (dest_node->insn) ? MEM_DEP 159 : REG_DEP); 160 161 /* For now we don't have an exact calculation of the distance, 162 so assume 1 conservatively. */ 163 if (interloop) 164 distance = 1; 165 166 gcc_assert (link); 167 168 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ 169 if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 170 t = ANTI_DEP; 171 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 172 t = OUTPUT_DEP; 173 latency = insn_cost (src_node->insn, link, dest_node->insn); 174 175 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); 176 177 if (interloop) 178 { 179 /* Some interloop dependencies are relaxed: 180 1. Every insn is output dependent on itself; ignore such deps. 181 2. Every true/flow dependence is an anti dependence in the 182 opposite direction with distance 1; such register deps 183 will be removed by renaming if broken --- ignore them. */ 184 if (!(t == OUTPUT_DEP && src_node == dest_node) 185 && !(t == ANTI_DEP && dt == REG_DEP)) 186 add_backarc_to_ddg (g, e); 187 else 188 free (e); 189 } 190 else if (t == ANTI_DEP && dt == REG_DEP) 191 free (e); /* We can fix broken anti register deps using reg-moves. */ 192 else 193 add_edge_to_ddg (g, e); 194} 195 196/* The same as the above function, but it doesn't require a link parameter. */ 197static void 198create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, 199 dep_type d_t, dep_data_type d_dt, int distance) 200{ 201 ddg_edge_ptr e; 202 int l; 203 rtx link = alloc_INSN_LIST (to->insn, NULL_RTX); 204 205 if (d_t == ANTI_DEP) 206 PUT_REG_NOTE_KIND (link, REG_DEP_ANTI); 207 else if (d_t == OUTPUT_DEP) 208 PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT); 209 210 l = insn_cost (from->insn, link, to->insn); 211 free_INSN_LIST_node (link); 212 213 e = create_ddg_edge (from, to, d_t, d_dt, l, distance); 214 if (distance > 0) 215 add_backarc_to_ddg (g, e); 216 else 217 add_edge_to_ddg (g, e); 218} 219 220 221/* Given a downwards exposed register def RD, add inter-loop true dependences 222 for all its uses in the next iteration, and an output dependence to the 223 first def of the next iteration. */ 224static void 225add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd) 226{ 227 int regno = DF_REF_REGNO (rd); 228 struct bb_info *bb_info = DF_BB_INFO (df, g->bb); 229 struct df_link *r_use; 230 int use_before_def = false; 231 rtx def_insn = DF_REF_INSN (rd); 232 ddg_node_ptr src_node = get_node_of_insn (g, def_insn); 233 234 /* Create and inter-loop true dependence between RD and each of its uses 235 that is upwards exposed in RD's block. */ 236 for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next) 237 { 238 if (bitmap_bit_p (bb_info->ru_gen, r_use->ref->id)) 239 { 240 rtx use_insn = DF_REF_INSN (r_use->ref); 241 ddg_node_ptr dest_node = get_node_of_insn (g, use_insn); 242 243 gcc_assert (src_node && dest_node); 244 245 /* Any such upwards exposed use appears before the rd def. */ 246 use_before_def = true; 247 create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP, 248 REG_DEP, 1); 249 } 250 } 251 252 /* Create an inter-loop output dependence between RD (which is the 253 last def in its block, being downwards exposed) and the first def 254 in its block. Avoid creating a self output dependence. Avoid creating 255 an output dependence if there is a dependence path between the two defs 256 starting with a true dependence followed by an anti dependence (i.e. if 257 there is a use between the two defs. */ 258 if (! use_before_def) 259 { 260 struct ref *def = df_bb_regno_first_def_find (df, g->bb, regno); 261 int i; 262 ddg_node_ptr dest_node; 263 264 if (!def || rd->id == def->id) 265 return; 266 267 /* Check if there are uses after RD. */ 268 for (i = src_node->cuid + 1; i < g->num_nodes; i++) 269 if (df_reg_used (df, g->nodes[i].insn, rd->reg)) 270 return; 271 272 dest_node = get_node_of_insn (g, def->insn); 273 create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1); 274 } 275} 276 277/* Given a register USE, add an inter-loop anti dependence to the first 278 (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed 279 by a def in the block. */ 280static void 281add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use) 282{ 283 int i; 284 int regno = DF_REF_REGNO (use); 285 struct ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno); 286 ddg_node_ptr use_node; 287 ddg_node_ptr def_node; 288 struct bb_info *bb_info; 289 290 bb_info = DF_BB_INFO (df, g->bb); 291 292 if (!first_def) 293 return; 294 295 use_node = get_node_of_insn (g, use->insn); 296 def_node = get_node_of_insn (g, first_def->insn); 297 298 gcc_assert (use_node && def_node); 299 300 /* Make sure there are no defs after USE. */ 301 for (i = use_node->cuid + 1; i < g->num_nodes; i++) 302 if (df_find_def (df, g->nodes[i].insn, use->reg)) 303 return; 304 /* We must not add ANTI dep when there is an intra-loop TRUE dep in 305 the opposite direction. If the first_def reaches the USE then there is 306 such a dep. */ 307 if (! bitmap_bit_p (bb_info->rd_gen, first_def->id)) 308 create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1); 309} 310 311/* Build inter-loop dependencies, by looking at DF analysis backwards. */ 312static void 313build_inter_loop_deps (ddg_ptr g, struct df *df) 314{ 315 unsigned rd_num, u_num; 316 struct bb_info *bb_info; 317 bitmap_iterator bi; 318 319 bb_info = DF_BB_INFO (df, g->bb); 320 321 /* Find inter-loop output and true deps by connecting downward exposed defs 322 to the first def of the BB and to upwards exposed uses. */ 323 EXECUTE_IF_SET_IN_BITMAP (bb_info->rd_gen, 0, rd_num, bi) 324 { 325 struct ref *rd = df->defs[rd_num]; 326 327 add_deps_for_def (g, df, rd); 328 } 329 330 /* Find inter-loop anti deps. We are interested in uses of the block that 331 appear below all defs; this implies that these uses are killed. */ 332 EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num, bi) 333 { 334 struct ref *use = df->uses[u_num]; 335 336 /* We are interested in uses of this BB. */ 337 if (BLOCK_FOR_INSN (use->insn) == g->bb) 338 add_deps_for_use (g, df,use); 339 } 340} 341 342/* Given two nodes, analyze their RTL insns and add inter-loop mem deps 343 to ddg G. */ 344static void 345add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) 346{ 347 if (mem_write_insn_p (from->insn)) 348 { 349 if (mem_read_insn_p (to->insn)) 350 create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1); 351 else if (from->cuid != to->cuid) 352 create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1); 353 } 354 else 355 { 356 if (mem_read_insn_p (to->insn)) 357 return; 358 else if (from->cuid != to->cuid) 359 { 360 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); 361 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); 362 } 363 } 364 365} 366 367/* Perform intra-block Data Dependency analysis and connect the nodes in 368 the DDG. We assume the loop has a single basic block. */ 369static void 370build_intra_loop_deps (ddg_ptr g) 371{ 372 int i; 373 /* Hold the dependency analysis state during dependency calculations. */ 374 struct deps tmp_deps; 375 rtx head, tail, link; 376 377 /* Build the dependence information, using the sched_analyze function. */ 378 init_deps_global (); 379 init_deps (&tmp_deps); 380 381 /* Do the intra-block data dependence analysis for the given block. */ 382 get_block_head_tail (g->bb->index, &head, &tail); 383 sched_analyze (&tmp_deps, head, tail); 384 385 /* Build intra-loop data dependencies using the scheduler dependency 386 analysis. */ 387 for (i = 0; i < g->num_nodes; i++) 388 { 389 ddg_node_ptr dest_node = &g->nodes[i]; 390 391 if (! INSN_P (dest_node->insn)) 392 continue; 393 394 for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1)) 395 { 396 ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0)); 397 398 if (!src_node) 399 continue; 400 401 add_forward_dependence (XEXP (link, 0), dest_node->insn, 402 REG_NOTE_KIND (link)); 403 create_ddg_dependence (g, src_node, dest_node, 404 INSN_DEPEND (src_node->insn)); 405 } 406 407 /* If this insn modifies memory, add an edge to all insns that access 408 memory. */ 409 if (mem_access_insn_p (dest_node->insn)) 410 { 411 int j; 412 413 for (j = 0; j <= i; j++) 414 { 415 ddg_node_ptr j_node = &g->nodes[j]; 416 if (mem_access_insn_p (j_node->insn)) 417 /* Don't bother calculating inter-loop dep if an intra-loop dep 418 already exists. */ 419 if (! TEST_BIT (dest_node->successors, j)) 420 add_inter_loop_mem_dep (g, dest_node, j_node); 421 } 422 } 423 } 424 425 /* Free the INSN_LISTs. */ 426 finish_deps_global (); 427 free_deps (&tmp_deps); 428} 429 430 431/* Given a basic block, create its DDG and return a pointer to a variable 432 of ddg type that represents it. 433 Initialize the ddg structure fields to the appropriate values. */ 434ddg_ptr 435create_ddg (basic_block bb, struct df *df, int closing_branch_deps) 436{ 437 ddg_ptr g; 438 rtx insn, first_note; 439 int i; 440 int num_nodes = 0; 441 442 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg)); 443 444 g->bb = bb; 445 g->closing_branch_deps = closing_branch_deps; 446 447 /* Count the number of insns in the BB. */ 448 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 449 insn = NEXT_INSN (insn)) 450 { 451 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE) 452 continue; 453 454 if (mem_read_insn_p (insn)) 455 g->num_loads++; 456 if (mem_write_insn_p (insn)) 457 g->num_stores++; 458 num_nodes++; 459 } 460 461 /* There is nothing to do for this BB. */ 462 if (num_nodes <= 1) 463 { 464 free (g); 465 return NULL; 466 } 467 468 /* Allocate the nodes array, and initialize the nodes. */ 469 g->num_nodes = num_nodes; 470 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); 471 g->closing_branch = NULL; 472 i = 0; 473 first_note = NULL_RTX; 474 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 475 insn = NEXT_INSN (insn)) 476 { 477 if (! INSN_P (insn)) 478 { 479 if (! first_note && NOTE_P (insn) 480 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) 481 first_note = insn; 482 continue; 483 } 484 if (JUMP_P (insn)) 485 { 486 gcc_assert (!g->closing_branch); 487 g->closing_branch = &g->nodes[i]; 488 } 489 else if (GET_CODE (PATTERN (insn)) == USE) 490 { 491 if (! first_note) 492 first_note = insn; 493 continue; 494 } 495 496 g->nodes[i].cuid = i; 497 g->nodes[i].successors = sbitmap_alloc (num_nodes); 498 sbitmap_zero (g->nodes[i].successors); 499 g->nodes[i].predecessors = sbitmap_alloc (num_nodes); 500 sbitmap_zero (g->nodes[i].predecessors); 501 g->nodes[i].first_note = (first_note ? first_note : insn); 502 g->nodes[i++].insn = insn; 503 first_note = NULL_RTX; 504 } 505 506 /* We must have found a branch in DDG. */ 507 gcc_assert (g->closing_branch); 508 509 510 /* Build the data dependency graph. */ 511 build_intra_loop_deps (g); 512 build_inter_loop_deps (g, df); 513 return g; 514} 515 516/* Free all the memory allocated for the DDG. */ 517void 518free_ddg (ddg_ptr g) 519{ 520 int i; 521 522 if (!g) 523 return; 524 525 for (i = 0; i < g->num_nodes; i++) 526 { 527 ddg_edge_ptr e = g->nodes[i].out; 528 529 while (e) 530 { 531 ddg_edge_ptr next = e->next_out; 532 533 free (e); 534 e = next; 535 } 536 sbitmap_free (g->nodes[i].successors); 537 sbitmap_free (g->nodes[i].predecessors); 538 } 539 if (g->num_backarcs > 0) 540 free (g->backarcs); 541 free (g->nodes); 542 free (g); 543} 544 545void 546print_ddg_edge (FILE *dump_file, ddg_edge_ptr e) 547{ 548 char dep_c; 549 550 switch (e->type) { 551 case OUTPUT_DEP : 552 dep_c = 'O'; 553 break; 554 case ANTI_DEP : 555 dep_c = 'A'; 556 break; 557 default: 558 dep_c = 'T'; 559 } 560 561 fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), 562 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); 563} 564 565/* Print the DDG nodes with there in/out edges to the dump file. */ 566void 567print_ddg (FILE *dump_file, ddg_ptr g) 568{ 569 int i; 570 571 for (i = 0; i < g->num_nodes; i++) 572 { 573 ddg_edge_ptr e; 574 575 print_rtl_single (dump_file, g->nodes[i].insn); 576 fprintf (dump_file, "OUT ARCS: "); 577 for (e = g->nodes[i].out; e; e = e->next_out) 578 print_ddg_edge (dump_file, e); 579 580 fprintf (dump_file, "\nIN ARCS: "); 581 for (e = g->nodes[i].in; e; e = e->next_in) 582 print_ddg_edge (dump_file, e); 583 584 fprintf (dump_file, "\n"); 585 } 586} 587 588/* Print the given DDG in VCG format. */ 589void 590vcg_print_ddg (FILE *dump_file, ddg_ptr g) 591{ 592 int src_cuid; 593 594 fprintf (dump_file, "graph: {\n"); 595 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) 596 { 597 ddg_edge_ptr e; 598 int src_uid = INSN_UID (g->nodes[src_cuid].insn); 599 600 fprintf (dump_file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); 601 print_rtl_single (dump_file, g->nodes[src_cuid].insn); 602 fprintf (dump_file, "\"}\n"); 603 for (e = g->nodes[src_cuid].out; e; e = e->next_out) 604 { 605 int dst_uid = INSN_UID (e->dest->insn); 606 int dst_cuid = e->dest->cuid; 607 608 /* Give the backarcs a different color. */ 609 if (e->distance > 0) 610 fprintf (dump_file, "backedge: {color: red "); 611 else 612 fprintf (dump_file, "edge: { "); 613 614 fprintf (dump_file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); 615 fprintf (dump_file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); 616 fprintf (dump_file, "label: \"%d_%d\"}\n", e->latency, e->distance); 617 } 618 } 619 fprintf (dump_file, "}\n"); 620} 621 622/* Create an edge and initialize it with given values. */ 623static ddg_edge_ptr 624create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, 625 dep_type t, dep_data_type dt, int l, int d) 626{ 627 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); 628 629 e->src = src; 630 e->dest = dest; 631 e->type = t; 632 e->data_type = dt; 633 e->latency = l; 634 e->distance = d; 635 e->next_in = e->next_out = NULL; 636 e->aux.info = 0; 637 return e; 638} 639 640/* Add the given edge to the in/out linked lists of the DDG nodes. */ 641static void 642add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) 643{ 644 ddg_node_ptr src = e->src; 645 ddg_node_ptr dest = e->dest; 646 647 /* Should have allocated the sbitmaps. */ 648 gcc_assert (src->successors && dest->predecessors); 649 650 SET_BIT (src->successors, dest->cuid); 651 SET_BIT (dest->predecessors, src->cuid); 652 e->next_in = dest->in; 653 dest->in = e; 654 e->next_out = src->out; 655 src->out = e; 656} 657 658 659 660/* Algorithm for computing the recurrence_length of an scc. We assume at 661 for now that cycles in the data dependence graph contain a single backarc. 662 This simplifies the algorithm, and can be generalized later. */ 663static void 664set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g) 665{ 666 int j; 667 int result = -1; 668 669 for (j = 0; j < scc->num_backarcs; j++) 670 { 671 ddg_edge_ptr backarc = scc->backarcs[j]; 672 int length; 673 int distance = backarc->distance; 674 ddg_node_ptr src = backarc->dest; 675 ddg_node_ptr dest = backarc->src; 676 677 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes); 678 if (length < 0 ) 679 { 680 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */ 681 continue; 682 } 683 length += backarc->latency; 684 result = MAX (result, (length / distance)); 685 } 686 scc->recurrence_length = result; 687} 688 689/* Create a new SCC given the set of its nodes. Compute its recurrence_length 690 and mark edges that belong to this scc as IN_SCC. */ 691static ddg_scc_ptr 692create_scc (ddg_ptr g, sbitmap nodes) 693{ 694 ddg_scc_ptr scc; 695 unsigned int u = 0; 696 sbitmap_iterator sbi; 697 698 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); 699 scc->backarcs = NULL; 700 scc->num_backarcs = 0; 701 scc->nodes = sbitmap_alloc (g->num_nodes); 702 sbitmap_copy (scc->nodes, nodes); 703 704 /* Mark the backarcs that belong to this SCC. */ 705 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi) 706 { 707 ddg_edge_ptr e; 708 ddg_node_ptr n = &g->nodes[u]; 709 710 for (e = n->out; e; e = e->next_out) 711 if (TEST_BIT (nodes, e->dest->cuid)) 712 { 713 e->aux.count = IN_SCC; 714 if (e->distance > 0) 715 add_backarc_to_scc (scc, e); 716 } 717 } 718 719 set_recurrence_length (scc, g); 720 return scc; 721} 722 723/* Cleans the memory allocation of a given SCC. */ 724static void 725free_scc (ddg_scc_ptr scc) 726{ 727 if (!scc) 728 return; 729 730 sbitmap_free (scc->nodes); 731 if (scc->num_backarcs > 0) 732 free (scc->backarcs); 733 free (scc); 734} 735 736 737/* Add a given edge known to be a backarc to the given DDG. */ 738static void 739add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) 740{ 741 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); 742 743 add_edge_to_ddg (g, e); 744 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); 745 g->backarcs[g->num_backarcs++] = e; 746} 747 748/* Add backarc to an SCC. */ 749static void 750add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) 751{ 752 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); 753 754 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); 755 scc->backarcs[scc->num_backarcs++] = e; 756} 757 758/* Add the given SCC to the DDG. */ 759static void 760add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) 761{ 762 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); 763 764 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); 765 g->sccs[g->num_sccs++] = scc; 766} 767 768/* Given the instruction INSN return the node that represents it. */ 769ddg_node_ptr 770get_node_of_insn (ddg_ptr g, rtx insn) 771{ 772 int i; 773 774 for (i = 0; i < g->num_nodes; i++) 775 if (insn == g->nodes[i].insn) 776 return &g->nodes[i]; 777 return NULL; 778} 779 780/* Given a set OPS of nodes in the DDG, find the set of their successors 781 which are not in OPS, and set their bits in SUCC. Bits corresponding to 782 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ 783void 784find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) 785{ 786 unsigned int i = 0; 787 sbitmap_iterator sbi; 788 789 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) 790 { 791 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); 792 sbitmap_a_or_b (succ, succ, node_succ); 793 }; 794 795 /* We want those that are not in ops. */ 796 sbitmap_difference (succ, succ, ops); 797} 798 799/* Given a set OPS of nodes in the DDG, find the set of their predecessors 800 which are not in OPS, and set their bits in PREDS. Bits corresponding to 801 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ 802void 803find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) 804{ 805 unsigned int i = 0; 806 sbitmap_iterator sbi; 807 808 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) 809 { 810 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); 811 sbitmap_a_or_b (preds, preds, node_preds); 812 }; 813 814 /* We want those that are not in ops. */ 815 sbitmap_difference (preds, preds, ops); 816} 817 818 819/* Compare function to be passed to qsort to order the backarcs in descending 820 recMII order. */ 821static int 822compare_sccs (const void *s1, const void *s2) 823{ 824 int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length; 825 int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length; 826 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); 827 828} 829 830/* Order the backarcs in descending recMII order using compare_sccs. */ 831static void 832order_sccs (ddg_all_sccs_ptr g) 833{ 834 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), 835 (int (*) (const void *, const void *)) compare_sccs); 836} 837 838/* Perform the Strongly Connected Components decomposing algorithm on the 839 DDG and return DDG_ALL_SCCS structure that contains them. */ 840ddg_all_sccs_ptr 841create_ddg_all_sccs (ddg_ptr g) 842{ 843 int i; 844 int num_nodes = g->num_nodes; 845 sbitmap from = sbitmap_alloc (num_nodes); 846 sbitmap to = sbitmap_alloc (num_nodes); 847 sbitmap scc_nodes = sbitmap_alloc (num_nodes); 848 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) 849 xmalloc (sizeof (struct ddg_all_sccs)); 850 851 sccs->ddg = g; 852 sccs->sccs = NULL; 853 sccs->num_sccs = 0; 854 855 for (i = 0; i < g->num_backarcs; i++) 856 { 857 ddg_scc_ptr scc; 858 ddg_edge_ptr backarc = g->backarcs[i]; 859 ddg_node_ptr src = backarc->src; 860 ddg_node_ptr dest = backarc->dest; 861 862 /* If the backarc already belongs to an SCC, continue. */ 863 if (backarc->aux.count == IN_SCC) 864 continue; 865 866 sbitmap_zero (from); 867 sbitmap_zero (to); 868 SET_BIT (from, dest->cuid); 869 SET_BIT (to, src->cuid); 870 871 if (find_nodes_on_paths (scc_nodes, g, from, to)) 872 { 873 scc = create_scc (g, scc_nodes); 874 add_scc_to_ddg (sccs, scc); 875 } 876 } 877 order_sccs (sccs); 878 sbitmap_free (from); 879 sbitmap_free (to); 880 sbitmap_free (scc_nodes); 881 return sccs; 882} 883 884/* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ 885void 886free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) 887{ 888 int i; 889 890 if (!all_sccs) 891 return; 892 893 for (i = 0; i < all_sccs->num_sccs; i++) 894 free_scc (all_sccs->sccs[i]); 895 896 free (all_sccs); 897} 898 899 900/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination 901 nodes - find all nodes that lie on paths from FROM to TO (not excluding 902 nodes from FROM and TO). Return nonzero if nodes exist. */ 903int 904find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) 905{ 906 int answer; 907 int change; 908 unsigned int u = 0; 909 int num_nodes = g->num_nodes; 910 sbitmap_iterator sbi; 911 912 sbitmap workset = sbitmap_alloc (num_nodes); 913 sbitmap reachable_from = sbitmap_alloc (num_nodes); 914 sbitmap reach_to = sbitmap_alloc (num_nodes); 915 sbitmap tmp = sbitmap_alloc (num_nodes); 916 917 sbitmap_copy (reachable_from, from); 918 sbitmap_copy (tmp, from); 919 920 change = 1; 921 while (change) 922 { 923 change = 0; 924 sbitmap_copy (workset, tmp); 925 sbitmap_zero (tmp); 926 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 927 { 928 ddg_edge_ptr e; 929 ddg_node_ptr u_node = &g->nodes[u]; 930 931 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) 932 { 933 ddg_node_ptr v_node = e->dest; 934 int v = v_node->cuid; 935 936 if (!TEST_BIT (reachable_from, v)) 937 { 938 SET_BIT (reachable_from, v); 939 SET_BIT (tmp, v); 940 change = 1; 941 } 942 } 943 } 944 } 945 946 sbitmap_copy (reach_to, to); 947 sbitmap_copy (tmp, to); 948 949 change = 1; 950 while (change) 951 { 952 change = 0; 953 sbitmap_copy (workset, tmp); 954 sbitmap_zero (tmp); 955 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 956 { 957 ddg_edge_ptr e; 958 ddg_node_ptr u_node = &g->nodes[u]; 959 960 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) 961 { 962 ddg_node_ptr v_node = e->src; 963 int v = v_node->cuid; 964 965 if (!TEST_BIT (reach_to, v)) 966 { 967 SET_BIT (reach_to, v); 968 SET_BIT (tmp, v); 969 change = 1; 970 } 971 } 972 } 973 } 974 975 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to); 976 sbitmap_free (workset); 977 sbitmap_free (reachable_from); 978 sbitmap_free (reach_to); 979 sbitmap_free (tmp); 980 return answer; 981} 982 983 984/* Updates the counts of U_NODE's successors (that belong to NODES) to be 985 at-least as large as the count of U_NODE plus the latency between them. 986 Sets a bit in TMP for each successor whose count was changed (increased). 987 Returns nonzero if any count was changed. */ 988static int 989update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp) 990{ 991 ddg_edge_ptr e; 992 int result = 0; 993 994 for (e = u_node->out; e; e = e->next_out) 995 { 996 ddg_node_ptr v_node = e->dest; 997 int v = v_node->cuid; 998 999 if (TEST_BIT (nodes, v) 1000 && (e->distance == 0) 1001 && (v_node->aux.count < u_node->aux.count + e->latency)) 1002 { 1003 v_node->aux.count = u_node->aux.count + e->latency; 1004 SET_BIT (tmp, v); 1005 result = 1; 1006 } 1007 } 1008 return result; 1009} 1010 1011 1012/* Find the length of a longest path from SRC to DEST in G, 1013 going only through NODES, and disregarding backarcs. */ 1014int 1015longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes) 1016{ 1017 int i; 1018 unsigned int u = 0; 1019 int change = 1; 1020 int result; 1021 int num_nodes = g->num_nodes; 1022 sbitmap workset = sbitmap_alloc (num_nodes); 1023 sbitmap tmp = sbitmap_alloc (num_nodes); 1024 1025 1026 /* Data will hold the distance of the longest path found so far from 1027 src to each node. Initialize to -1 = less than minimum. */ 1028 for (i = 0; i < g->num_nodes; i++) 1029 g->nodes[i].aux.count = -1; 1030 g->nodes[src].aux.count = 0; 1031 1032 sbitmap_zero (tmp); 1033 SET_BIT (tmp, src); 1034 1035 while (change) 1036 { 1037 sbitmap_iterator sbi; 1038 1039 change = 0; 1040 sbitmap_copy (workset, tmp); 1041 sbitmap_zero (tmp); 1042 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 1043 { 1044 ddg_node_ptr u_node = &g->nodes[u]; 1045 1046 change |= update_dist_to_successors (u_node, nodes, tmp); 1047 } 1048 } 1049 result = g->nodes[dest].aux.count; 1050 sbitmap_free (workset); 1051 sbitmap_free (tmp); 1052 return result; 1053} 1054