1/* DDG - Data Dependence Graph implementation. 2 Copyright (C) 2004, 2005, 2006 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 df_ref *rd) 226{ 227 int regno = DF_REF_REGNO (rd); 228 struct df_ru_bb_info *bb_info = DF_RU_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->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 df_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_find_use (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 df_ref *use) 282{ 283 int i; 284 int regno = DF_REF_REGNO (use); 285 struct df_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 df_rd_bb_info *bb_info; 289 290 bb_info = DF_RD_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->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 df_rd_bb_info *rd_bb_info; 317 struct df_ru_bb_info *ru_bb_info; 318 bitmap_iterator bi; 319 320 rd_bb_info = DF_RD_BB_INFO (df, g->bb); 321 322 /* Find inter-loop output and true deps by connecting downward exposed defs 323 to the first def of the BB and to upwards exposed uses. */ 324 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi) 325 { 326 struct df_ref *rd = DF_DEFS_GET (df, rd_num); 327 328 add_deps_for_def (g, df, rd); 329 } 330 331 ru_bb_info = DF_RU_BB_INFO (df, g->bb); 332 333 /* Find inter-loop anti deps. We are interested in uses of the block that 334 appear below all defs; this implies that these uses are killed. */ 335 EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi) 336 { 337 struct df_ref *use = DF_USES_GET (df, u_num); 338 339 /* We are interested in uses of this BB. */ 340 if (BLOCK_FOR_INSN (use->insn) == g->bb) 341 add_deps_for_use (g, df, use); 342 } 343} 344 345/* Given two nodes, analyze their RTL insns and add inter-loop mem deps 346 to ddg G. */ 347static void 348add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) 349{ 350 if (mem_write_insn_p (from->insn)) 351 { 352 if (mem_read_insn_p (to->insn)) 353 create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1); 354 else if (from->cuid != to->cuid) 355 create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1); 356 } 357 else 358 { 359 if (mem_read_insn_p (to->insn)) 360 return; 361 else if (from->cuid != to->cuid) 362 { 363 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); 364 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); 365 } 366 } 367 368} 369 370/* Perform intra-block Data Dependency analysis and connect the nodes in 371 the DDG. We assume the loop has a single basic block. */ 372static void 373build_intra_loop_deps (ddg_ptr g) 374{ 375 int i; 376 /* Hold the dependency analysis state during dependency calculations. */ 377 struct deps tmp_deps; 378 rtx head, tail, link; 379 380 /* Build the dependence information, using the sched_analyze function. */ 381 init_deps_global (); 382 init_deps (&tmp_deps); 383 384 /* Do the intra-block data dependence analysis for the given block. */ 385 get_ebb_head_tail (g->bb, g->bb, &head, &tail); 386 sched_analyze (&tmp_deps, head, tail); 387 388 /* Build intra-loop data dependencies using the scheduler dependency 389 analysis. */ 390 for (i = 0; i < g->num_nodes; i++) 391 { 392 ddg_node_ptr dest_node = &g->nodes[i]; 393 394 if (! INSN_P (dest_node->insn)) 395 continue; 396 397 for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1)) 398 { 399 ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0)); 400 401 if (!src_node) 402 continue; 403 404 add_forw_dep (dest_node->insn, link); 405 create_ddg_dependence (g, src_node, dest_node, 406 INSN_DEPEND (src_node->insn)); 407 } 408 409 /* If this insn modifies memory, add an edge to all insns that access 410 memory. */ 411 if (mem_access_insn_p (dest_node->insn)) 412 { 413 int j; 414 415 for (j = 0; j <= i; j++) 416 { 417 ddg_node_ptr j_node = &g->nodes[j]; 418 if (mem_access_insn_p (j_node->insn)) 419 /* Don't bother calculating inter-loop dep if an intra-loop dep 420 already exists. */ 421 if (! TEST_BIT (dest_node->successors, j)) 422 add_inter_loop_mem_dep (g, dest_node, j_node); 423 } 424 } 425 } 426 427 /* Free the INSN_LISTs. */ 428 finish_deps_global (); 429 free_deps (&tmp_deps); 430} 431 432 433/* Given a basic block, create its DDG and return a pointer to a variable 434 of ddg type that represents it. 435 Initialize the ddg structure fields to the appropriate values. */ 436ddg_ptr 437create_ddg (basic_block bb, struct df *df, int closing_branch_deps) 438{ 439 ddg_ptr g; 440 rtx insn, first_note; 441 int i; 442 int num_nodes = 0; 443 444 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg)); 445 446 g->bb = bb; 447 g->closing_branch_deps = closing_branch_deps; 448 449 /* Count the number of insns in the BB. */ 450 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 451 insn = NEXT_INSN (insn)) 452 { 453 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE) 454 continue; 455 456 if (mem_read_insn_p (insn)) 457 g->num_loads++; 458 if (mem_write_insn_p (insn)) 459 g->num_stores++; 460 num_nodes++; 461 } 462 463 /* There is nothing to do for this BB. */ 464 if (num_nodes <= 1) 465 { 466 free (g); 467 return NULL; 468 } 469 470 /* Allocate the nodes array, and initialize the nodes. */ 471 g->num_nodes = num_nodes; 472 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); 473 g->closing_branch = NULL; 474 i = 0; 475 first_note = NULL_RTX; 476 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 477 insn = NEXT_INSN (insn)) 478 { 479 if (! INSN_P (insn)) 480 { 481 if (! first_note && NOTE_P (insn) 482 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) 483 first_note = insn; 484 continue; 485 } 486 if (JUMP_P (insn)) 487 { 488 gcc_assert (!g->closing_branch); 489 g->closing_branch = &g->nodes[i]; 490 } 491 else if (GET_CODE (PATTERN (insn)) == USE) 492 { 493 if (! first_note) 494 first_note = insn; 495 continue; 496 } 497 498 g->nodes[i].cuid = i; 499 g->nodes[i].successors = sbitmap_alloc (num_nodes); 500 sbitmap_zero (g->nodes[i].successors); 501 g->nodes[i].predecessors = sbitmap_alloc (num_nodes); 502 sbitmap_zero (g->nodes[i].predecessors); 503 g->nodes[i].first_note = (first_note ? first_note : insn); 504 g->nodes[i++].insn = insn; 505 first_note = NULL_RTX; 506 } 507 508 /* We must have found a branch in DDG. */ 509 gcc_assert (g->closing_branch); 510 511 512 /* Build the data dependency graph. */ 513 build_intra_loop_deps (g); 514 build_inter_loop_deps (g, df); 515 return g; 516} 517 518/* Free all the memory allocated for the DDG. */ 519void 520free_ddg (ddg_ptr g) 521{ 522 int i; 523 524 if (!g) 525 return; 526 527 for (i = 0; i < g->num_nodes; i++) 528 { 529 ddg_edge_ptr e = g->nodes[i].out; 530 531 while (e) 532 { 533 ddg_edge_ptr next = e->next_out; 534 535 free (e); 536 e = next; 537 } 538 sbitmap_free (g->nodes[i].successors); 539 sbitmap_free (g->nodes[i].predecessors); 540 } 541 if (g->num_backarcs > 0) 542 free (g->backarcs); 543 free (g->nodes); 544 free (g); 545} 546 547void 548print_ddg_edge (FILE *file, ddg_edge_ptr e) 549{ 550 char dep_c; 551 552 switch (e->type) { 553 case OUTPUT_DEP : 554 dep_c = 'O'; 555 break; 556 case ANTI_DEP : 557 dep_c = 'A'; 558 break; 559 default: 560 dep_c = 'T'; 561 } 562 563 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), 564 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); 565} 566 567/* Print the DDG nodes with there in/out edges to the dump file. */ 568void 569print_ddg (FILE *file, ddg_ptr g) 570{ 571 int i; 572 573 for (i = 0; i < g->num_nodes; i++) 574 { 575 ddg_edge_ptr e; 576 577 print_rtl_single (file, g->nodes[i].insn); 578 fprintf (file, "OUT ARCS: "); 579 for (e = g->nodes[i].out; e; e = e->next_out) 580 print_ddg_edge (file, e); 581 582 fprintf (file, "\nIN ARCS: "); 583 for (e = g->nodes[i].in; e; e = e->next_in) 584 print_ddg_edge (file, e); 585 586 fprintf (file, "\n"); 587 } 588} 589 590/* Print the given DDG in VCG format. */ 591void 592vcg_print_ddg (FILE *file, ddg_ptr g) 593{ 594 int src_cuid; 595 596 fprintf (file, "graph: {\n"); 597 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) 598 { 599 ddg_edge_ptr e; 600 int src_uid = INSN_UID (g->nodes[src_cuid].insn); 601 602 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); 603 print_rtl_single (file, g->nodes[src_cuid].insn); 604 fprintf (file, "\"}\n"); 605 for (e = g->nodes[src_cuid].out; e; e = e->next_out) 606 { 607 int dst_uid = INSN_UID (e->dest->insn); 608 int dst_cuid = e->dest->cuid; 609 610 /* Give the backarcs a different color. */ 611 if (e->distance > 0) 612 fprintf (file, "backedge: {color: red "); 613 else 614 fprintf (file, "edge: { "); 615 616 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); 617 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); 618 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance); 619 } 620 } 621 fprintf (file, "}\n"); 622} 623 624/* Create an edge and initialize it with given values. */ 625static ddg_edge_ptr 626create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, 627 dep_type t, dep_data_type dt, int l, int d) 628{ 629 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); 630 631 e->src = src; 632 e->dest = dest; 633 e->type = t; 634 e->data_type = dt; 635 e->latency = l; 636 e->distance = d; 637 e->next_in = e->next_out = NULL; 638 e->aux.info = 0; 639 return e; 640} 641 642/* Add the given edge to the in/out linked lists of the DDG nodes. */ 643static void 644add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) 645{ 646 ddg_node_ptr src = e->src; 647 ddg_node_ptr dest = e->dest; 648 649 /* Should have allocated the sbitmaps. */ 650 gcc_assert (src->successors && dest->predecessors); 651 652 SET_BIT (src->successors, dest->cuid); 653 SET_BIT (dest->predecessors, src->cuid); 654 e->next_in = dest->in; 655 dest->in = e; 656 e->next_out = src->out; 657 src->out = e; 658} 659 660 661 662/* Algorithm for computing the recurrence_length of an scc. We assume at 663 for now that cycles in the data dependence graph contain a single backarc. 664 This simplifies the algorithm, and can be generalized later. */ 665static void 666set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g) 667{ 668 int j; 669 int result = -1; 670 671 for (j = 0; j < scc->num_backarcs; j++) 672 { 673 ddg_edge_ptr backarc = scc->backarcs[j]; 674 int length; 675 int distance = backarc->distance; 676 ddg_node_ptr src = backarc->dest; 677 ddg_node_ptr dest = backarc->src; 678 679 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes); 680 if (length < 0 ) 681 { 682 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */ 683 continue; 684 } 685 length += backarc->latency; 686 result = MAX (result, (length / distance)); 687 } 688 scc->recurrence_length = result; 689} 690 691/* Create a new SCC given the set of its nodes. Compute its recurrence_length 692 and mark edges that belong to this scc as IN_SCC. */ 693static ddg_scc_ptr 694create_scc (ddg_ptr g, sbitmap nodes) 695{ 696 ddg_scc_ptr scc; 697 unsigned int u = 0; 698 sbitmap_iterator sbi; 699 700 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); 701 scc->backarcs = NULL; 702 scc->num_backarcs = 0; 703 scc->nodes = sbitmap_alloc (g->num_nodes); 704 sbitmap_copy (scc->nodes, nodes); 705 706 /* Mark the backarcs that belong to this SCC. */ 707 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi) 708 { 709 ddg_edge_ptr e; 710 ddg_node_ptr n = &g->nodes[u]; 711 712 for (e = n->out; e; e = e->next_out) 713 if (TEST_BIT (nodes, e->dest->cuid)) 714 { 715 e->aux.count = IN_SCC; 716 if (e->distance > 0) 717 add_backarc_to_scc (scc, e); 718 } 719 } 720 721 set_recurrence_length (scc, g); 722 return scc; 723} 724 725/* Cleans the memory allocation of a given SCC. */ 726static void 727free_scc (ddg_scc_ptr scc) 728{ 729 if (!scc) 730 return; 731 732 sbitmap_free (scc->nodes); 733 if (scc->num_backarcs > 0) 734 free (scc->backarcs); 735 free (scc); 736} 737 738 739/* Add a given edge known to be a backarc to the given DDG. */ 740static void 741add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) 742{ 743 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); 744 745 add_edge_to_ddg (g, e); 746 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); 747 g->backarcs[g->num_backarcs++] = e; 748} 749 750/* Add backarc to an SCC. */ 751static void 752add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) 753{ 754 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); 755 756 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); 757 scc->backarcs[scc->num_backarcs++] = e; 758} 759 760/* Add the given SCC to the DDG. */ 761static void 762add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) 763{ 764 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); 765 766 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); 767 g->sccs[g->num_sccs++] = scc; 768} 769 770/* Given the instruction INSN return the node that represents it. */ 771ddg_node_ptr 772get_node_of_insn (ddg_ptr g, rtx insn) 773{ 774 int i; 775 776 for (i = 0; i < g->num_nodes; i++) 777 if (insn == g->nodes[i].insn) 778 return &g->nodes[i]; 779 return NULL; 780} 781 782/* Given a set OPS of nodes in the DDG, find the set of their successors 783 which are not in OPS, and set their bits in SUCC. Bits corresponding to 784 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ 785void 786find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) 787{ 788 unsigned int i = 0; 789 sbitmap_iterator sbi; 790 791 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) 792 { 793 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); 794 sbitmap_a_or_b (succ, succ, node_succ); 795 }; 796 797 /* We want those that are not in ops. */ 798 sbitmap_difference (succ, succ, ops); 799} 800 801/* Given a set OPS of nodes in the DDG, find the set of their predecessors 802 which are not in OPS, and set their bits in PREDS. Bits corresponding to 803 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ 804void 805find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) 806{ 807 unsigned int i = 0; 808 sbitmap_iterator sbi; 809 810 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) 811 { 812 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); 813 sbitmap_a_or_b (preds, preds, node_preds); 814 }; 815 816 /* We want those that are not in ops. */ 817 sbitmap_difference (preds, preds, ops); 818} 819 820 821/* Compare function to be passed to qsort to order the backarcs in descending 822 recMII order. */ 823static int 824compare_sccs (const void *s1, const void *s2) 825{ 826 int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length; 827 int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length; 828 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); 829 830} 831 832/* Order the backarcs in descending recMII order using compare_sccs. */ 833static void 834order_sccs (ddg_all_sccs_ptr g) 835{ 836 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), 837 (int (*) (const void *, const void *)) compare_sccs); 838} 839 840/* Perform the Strongly Connected Components decomposing algorithm on the 841 DDG and return DDG_ALL_SCCS structure that contains them. */ 842ddg_all_sccs_ptr 843create_ddg_all_sccs (ddg_ptr g) 844{ 845 int i; 846 int num_nodes = g->num_nodes; 847 sbitmap from = sbitmap_alloc (num_nodes); 848 sbitmap to = sbitmap_alloc (num_nodes); 849 sbitmap scc_nodes = sbitmap_alloc (num_nodes); 850 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) 851 xmalloc (sizeof (struct ddg_all_sccs)); 852 853 sccs->ddg = g; 854 sccs->sccs = NULL; 855 sccs->num_sccs = 0; 856 857 for (i = 0; i < g->num_backarcs; i++) 858 { 859 ddg_scc_ptr scc; 860 ddg_edge_ptr backarc = g->backarcs[i]; 861 ddg_node_ptr src = backarc->src; 862 ddg_node_ptr dest = backarc->dest; 863 864 /* If the backarc already belongs to an SCC, continue. */ 865 if (backarc->aux.count == IN_SCC) 866 continue; 867 868 sbitmap_zero (from); 869 sbitmap_zero (to); 870 SET_BIT (from, dest->cuid); 871 SET_BIT (to, src->cuid); 872 873 if (find_nodes_on_paths (scc_nodes, g, from, to)) 874 { 875 scc = create_scc (g, scc_nodes); 876 add_scc_to_ddg (sccs, scc); 877 } 878 } 879 order_sccs (sccs); 880 sbitmap_free (from); 881 sbitmap_free (to); 882 sbitmap_free (scc_nodes); 883 return sccs; 884} 885 886/* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ 887void 888free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) 889{ 890 int i; 891 892 if (!all_sccs) 893 return; 894 895 for (i = 0; i < all_sccs->num_sccs; i++) 896 free_scc (all_sccs->sccs[i]); 897 898 free (all_sccs); 899} 900 901 902/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination 903 nodes - find all nodes that lie on paths from FROM to TO (not excluding 904 nodes from FROM and TO). Return nonzero if nodes exist. */ 905int 906find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) 907{ 908 int answer; 909 int change; 910 unsigned int u = 0; 911 int num_nodes = g->num_nodes; 912 sbitmap_iterator sbi; 913 914 sbitmap workset = sbitmap_alloc (num_nodes); 915 sbitmap reachable_from = sbitmap_alloc (num_nodes); 916 sbitmap reach_to = sbitmap_alloc (num_nodes); 917 sbitmap tmp = sbitmap_alloc (num_nodes); 918 919 sbitmap_copy (reachable_from, from); 920 sbitmap_copy (tmp, from); 921 922 change = 1; 923 while (change) 924 { 925 change = 0; 926 sbitmap_copy (workset, tmp); 927 sbitmap_zero (tmp); 928 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 929 { 930 ddg_edge_ptr e; 931 ddg_node_ptr u_node = &g->nodes[u]; 932 933 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) 934 { 935 ddg_node_ptr v_node = e->dest; 936 int v = v_node->cuid; 937 938 if (!TEST_BIT (reachable_from, v)) 939 { 940 SET_BIT (reachable_from, v); 941 SET_BIT (tmp, v); 942 change = 1; 943 } 944 } 945 } 946 } 947 948 sbitmap_copy (reach_to, to); 949 sbitmap_copy (tmp, to); 950 951 change = 1; 952 while (change) 953 { 954 change = 0; 955 sbitmap_copy (workset, tmp); 956 sbitmap_zero (tmp); 957 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 958 { 959 ddg_edge_ptr e; 960 ddg_node_ptr u_node = &g->nodes[u]; 961 962 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) 963 { 964 ddg_node_ptr v_node = e->src; 965 int v = v_node->cuid; 966 967 if (!TEST_BIT (reach_to, v)) 968 { 969 SET_BIT (reach_to, v); 970 SET_BIT (tmp, v); 971 change = 1; 972 } 973 } 974 } 975 } 976 977 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to); 978 sbitmap_free (workset); 979 sbitmap_free (reachable_from); 980 sbitmap_free (reach_to); 981 sbitmap_free (tmp); 982 return answer; 983} 984 985 986/* Updates the counts of U_NODE's successors (that belong to NODES) to be 987 at-least as large as the count of U_NODE plus the latency between them. 988 Sets a bit in TMP for each successor whose count was changed (increased). 989 Returns nonzero if any count was changed. */ 990static int 991update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp) 992{ 993 ddg_edge_ptr e; 994 int result = 0; 995 996 for (e = u_node->out; e; e = e->next_out) 997 { 998 ddg_node_ptr v_node = e->dest; 999 int v = v_node->cuid; 1000 1001 if (TEST_BIT (nodes, v) 1002 && (e->distance == 0) 1003 && (v_node->aux.count < u_node->aux.count + e->latency)) 1004 { 1005 v_node->aux.count = u_node->aux.count + e->latency; 1006 SET_BIT (tmp, v); 1007 result = 1; 1008 } 1009 } 1010 return result; 1011} 1012 1013 1014/* Find the length of a longest path from SRC to DEST in G, 1015 going only through NODES, and disregarding backarcs. */ 1016int 1017longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes) 1018{ 1019 int i; 1020 unsigned int u = 0; 1021 int change = 1; 1022 int result; 1023 int num_nodes = g->num_nodes; 1024 sbitmap workset = sbitmap_alloc (num_nodes); 1025 sbitmap tmp = sbitmap_alloc (num_nodes); 1026 1027 1028 /* Data will hold the distance of the longest path found so far from 1029 src to each node. Initialize to -1 = less than minimum. */ 1030 for (i = 0; i < g->num_nodes; i++) 1031 g->nodes[i].aux.count = -1; 1032 g->nodes[src].aux.count = 0; 1033 1034 sbitmap_zero (tmp); 1035 SET_BIT (tmp, src); 1036 1037 while (change) 1038 { 1039 sbitmap_iterator sbi; 1040 1041 change = 0; 1042 sbitmap_copy (workset, tmp); 1043 sbitmap_zero (tmp); 1044 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 1045 { 1046 ddg_node_ptr u_node = &g->nodes[u]; 1047 1048 change |= update_dist_to_successors (u_node, nodes, tmp); 1049 } 1050 } 1051 result = g->nodes[dest].aux.count; 1052 sbitmap_free (workset); 1053 sbitmap_free (tmp); 1054 return result; 1055} 1056