1/* DDG - Data Dependence Graph implementation. 2 Copyright (C) 2004-2015 Free Software Foundation, Inc. 3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> 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 3, 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 COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "diagnostic-core.h" 27#include "rtl.h" 28#include "tm_p.h" 29#include "hard-reg-set.h" 30#include "regs.h" 31#include "hashtab.h" 32#include "hash-set.h" 33#include "vec.h" 34#include "machmode.h" 35#include "input.h" 36#include "function.h" 37#include "flags.h" 38#include "insn-config.h" 39#include "insn-attr.h" 40#include "except.h" 41#include "recog.h" 42#include "predict.h" 43#include "basic-block.h" 44#include "sched-int.h" 45#include "target.h" 46#include "cfgloop.h" 47#include "sbitmap.h" 48#include "symtab.h" 49#include "statistics.h" 50#include "double-int.h" 51#include "real.h" 52#include "fixed-value.h" 53#include "alias.h" 54#include "wide-int.h" 55#include "inchash.h" 56#include "tree.h" 57#include "expmed.h" 58#include "dojump.h" 59#include "explow.h" 60#include "calls.h" 61#include "emit-rtl.h" 62#include "varasm.h" 63#include "stmt.h" 64#include "expr.h" 65#include "bitmap.h" 66#include "df.h" 67#include "ddg.h" 68#include "rtl-iter.h" 69 70#ifdef INSN_SCHEDULING 71 72/* A flag indicating that a ddg edge belongs to an SCC or not. */ 73enum edge_flag {NOT_IN_SCC = 0, IN_SCC}; 74 75/* Forward declarations. */ 76static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr); 77static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr); 78static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr); 79static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr, 80 ddg_node_ptr, dep_t); 81static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, 82 dep_type, dep_data_type, int); 83static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, 84 dep_data_type, int, int); 85static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr); 86 87/* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ 88static bool mem_ref_p; 89 90/* Auxiliary function for mem_read_insn_p. */ 91static void 92mark_mem_use (rtx *x, void *) 93{ 94 subrtx_iterator::array_type array; 95 FOR_EACH_SUBRTX (iter, array, *x, NONCONST) 96 if (MEM_P (*iter)) 97 { 98 mem_ref_p = true; 99 break; 100 } 101} 102 103/* Returns nonzero if INSN reads from memory. */ 104static bool 105mem_read_insn_p (rtx_insn *insn) 106{ 107 mem_ref_p = false; 108 note_uses (&PATTERN (insn), mark_mem_use, NULL); 109 return mem_ref_p; 110} 111 112static void 113mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) 114{ 115 if (MEM_P (loc)) 116 mem_ref_p = true; 117} 118 119/* Returns nonzero if INSN writes to memory. */ 120static bool 121mem_write_insn_p (rtx_insn *insn) 122{ 123 mem_ref_p = false; 124 note_stores (PATTERN (insn), mark_mem_store, NULL); 125 return mem_ref_p; 126} 127 128/* Returns nonzero if X has access to memory. */ 129static bool 130rtx_mem_access_p (rtx x) 131{ 132 int i, j; 133 const char *fmt; 134 enum rtx_code code; 135 136 if (x == 0) 137 return false; 138 139 if (MEM_P (x)) 140 return true; 141 142 code = GET_CODE (x); 143 fmt = GET_RTX_FORMAT (code); 144 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 145 { 146 if (fmt[i] == 'e') 147 { 148 if (rtx_mem_access_p (XEXP (x, i))) 149 return true; 150 } 151 else if (fmt[i] == 'E') 152 for (j = 0; j < XVECLEN (x, i); j++) 153 { 154 if (rtx_mem_access_p (XVECEXP (x, i, j))) 155 return true; 156 } 157 } 158 return false; 159} 160 161/* Returns nonzero if INSN reads to or writes from memory. */ 162static bool 163mem_access_insn_p (rtx_insn *insn) 164{ 165 return rtx_mem_access_p (PATTERN (insn)); 166} 167 168/* Return true if DEF_INSN contains address being auto-inc or auto-dec 169 which is used in USE_INSN. Otherwise return false. The result is 170 being used to decide whether to remove the edge between def_insn and 171 use_insn when -fmodulo-sched-allow-regmoves is set. This function 172 doesn't need to consider the specific address register; no reg_moves 173 will be allowed for any life range defined by def_insn and used 174 by use_insn, if use_insn uses an address register auto-inc'ed by 175 def_insn. */ 176bool 177autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn) 178{ 179 rtx note; 180 181 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1)) 182 if (REG_NOTE_KIND (note) == REG_INC 183 && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn))) 184 return true; 185 186 return false; 187} 188 189/* Return true if one of the definitions in INSN has MODE_CC. Otherwise 190 return false. */ 191static bool 192def_has_ccmode_p (rtx_insn *insn) 193{ 194 df_ref def; 195 196 FOR_EACH_INSN_DEF (def, insn) 197 { 198 machine_mode mode = GET_MODE (DF_REF_REG (def)); 199 200 if (GET_MODE_CLASS (mode) == MODE_CC) 201 return true; 202 } 203 204 return false; 205} 206 207/* Computes the dependence parameters (latency, distance etc.), creates 208 a ddg_edge and adds it to the given DDG. */ 209static void 210create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node, 211 ddg_node_ptr dest_node, dep_t link) 212{ 213 ddg_edge_ptr e; 214 int latency, distance = 0; 215 dep_type t = TRUE_DEP; 216 dep_data_type dt = (mem_access_insn_p (src_node->insn) 217 && mem_access_insn_p (dest_node->insn) ? MEM_DEP 218 : REG_DEP); 219 gcc_assert (src_node->cuid < dest_node->cuid); 220 gcc_assert (link); 221 222 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ 223 if (DEP_TYPE (link) == REG_DEP_ANTI) 224 t = ANTI_DEP; 225 else if (DEP_TYPE (link) == REG_DEP_OUTPUT) 226 t = OUTPUT_DEP; 227 228 gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP); 229 gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP); 230 231 /* We currently choose not to create certain anti-deps edges and 232 compensate for that by generating reg-moves based on the life-range 233 analysis. The anti-deps that will be deleted are the ones which 234 have true-deps edges in the opposite direction (in other words 235 the kernel has only one def of the relevant register). 236 If the address that is being auto-inc or auto-dec in DEST_NODE 237 is used in SRC_NODE then do not remove the edge to make sure 238 reg-moves will not be created for this address. 239 TODO: support the removal of all anti-deps edges, i.e. including those 240 whose register has multiple defs in the loop. */ 241 if (flag_modulo_sched_allow_regmoves 242 && (t == ANTI_DEP && dt == REG_DEP) 243 && !def_has_ccmode_p (dest_node->insn) 244 && !autoinc_var_is_used_p (dest_node->insn, src_node->insn)) 245 { 246 rtx set; 247 248 set = single_set (dest_node->insn); 249 /* TODO: Handle registers that REG_P is not true for them, i.e. 250 subregs and special registers. */ 251 if (set && REG_P (SET_DEST (set))) 252 { 253 int regno = REGNO (SET_DEST (set)); 254 df_ref first_def; 255 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); 256 257 first_def = df_bb_regno_first_def_find (g->bb, regno); 258 gcc_assert (first_def); 259 260 if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))) 261 return; 262 } 263 } 264 265 latency = dep_cost (link); 266 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); 267 add_edge_to_ddg (g, e); 268} 269 270/* The same as the above function, but it doesn't require a link parameter. */ 271static void 272create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, 273 dep_type d_t, dep_data_type d_dt, int distance) 274{ 275 ddg_edge_ptr e; 276 int l; 277 enum reg_note dep_kind; 278 struct _dep _dep, *dep = &_dep; 279 280 gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP); 281 gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP); 282 283 if (d_t == ANTI_DEP) 284 dep_kind = REG_DEP_ANTI; 285 else if (d_t == OUTPUT_DEP) 286 dep_kind = REG_DEP_OUTPUT; 287 else 288 { 289 gcc_assert (d_t == TRUE_DEP); 290 291 dep_kind = REG_DEP_TRUE; 292 } 293 294 init_dep (dep, from->insn, to->insn, dep_kind); 295 296 l = dep_cost (dep); 297 298 e = create_ddg_edge (from, to, d_t, d_dt, l, distance); 299 if (distance > 0) 300 add_backarc_to_ddg (g, e); 301 else 302 add_edge_to_ddg (g, e); 303} 304 305 306/* Given a downwards exposed register def LAST_DEF (which is the last 307 definition of that register in the bb), add inter-loop true dependences 308 to all its uses in the next iteration, an output dependence to the 309 first def of the same register (possibly itself) in the next iteration 310 and anti-dependences from its uses in the current iteration to the 311 first definition in the next iteration. */ 312static void 313add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def) 314{ 315 int regno = DF_REF_REGNO (last_def); 316 struct df_link *r_use; 317 int has_use_in_bb_p = false; 318 rtx_insn *def_insn = DF_REF_INSN (last_def); 319 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn); 320 ddg_node_ptr use_node; 321#ifdef ENABLE_CHECKING 322 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); 323#endif 324 df_ref first_def = df_bb_regno_first_def_find (g->bb, regno); 325 326 gcc_assert (last_def_node); 327 gcc_assert (first_def); 328 329#ifdef ENABLE_CHECKING 330 if (DF_REF_ID (last_def) != DF_REF_ID (first_def)) 331 gcc_assert (!bitmap_bit_p (&bb_info->gen, 332 DF_REF_ID (first_def))); 333#endif 334 335 /* Create inter-loop true dependences and anti dependences. */ 336 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next) 337 { 338 rtx_insn *use_insn = DF_REF_INSN (r_use->ref); 339 340 if (BLOCK_FOR_INSN (use_insn) != g->bb) 341 continue; 342 343 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */ 344 use_node = get_node_of_insn (g, use_insn); 345 gcc_assert (use_node); 346 has_use_in_bb_p = true; 347 if (use_node->cuid <= last_def_node->cuid) 348 { 349 /* Add true deps from last_def to it's uses in the next 350 iteration. Any such upwards exposed use appears before 351 the last_def def. */ 352 create_ddg_dep_no_link (g, last_def_node, use_node, 353 DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP, 354 REG_DEP, 1); 355 } 356 else if (!DEBUG_INSN_P (use_insn)) 357 { 358 /* Add anti deps from last_def's uses in the current iteration 359 to the first def in the next iteration. We do not add ANTI 360 dep when there is an intra-loop TRUE dep in the opposite 361 direction, but use regmoves to fix such disregarded ANTI 362 deps when broken. If the first_def reaches the USE then 363 there is such a dep. */ 364 ddg_node_ptr first_def_node = get_node_of_insn (g, 365 DF_REF_INSN (first_def)); 366 367 gcc_assert (first_def_node); 368 369 /* Always create the edge if the use node is a branch in 370 order to prevent the creation of reg-moves. 371 If the address that is being auto-inc or auto-dec in LAST_DEF 372 is used in USE_INSN then do not remove the edge to make sure 373 reg-moves will not be created for that address. */ 374 if (DF_REF_ID (last_def) != DF_REF_ID (first_def) 375 || !flag_modulo_sched_allow_regmoves 376 || JUMP_P (use_node->insn) 377 || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn) 378 || def_has_ccmode_p (DF_REF_INSN (last_def))) 379 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP, 380 REG_DEP, 1); 381 382 } 383 } 384 /* Create an inter-loop output dependence between LAST_DEF (which is the 385 last def in its block, being downwards exposed) and the first def in 386 its block. Avoid creating a self output dependence. Avoid creating 387 an output dependence if there is a dependence path between the two 388 defs starting with a true dependence to a use which can be in the 389 next iteration; followed by an anti dependence of that use to the 390 first def (i.e. if there is a use between the two defs.) */ 391 if (!has_use_in_bb_p) 392 { 393 ddg_node_ptr dest_node; 394 395 if (DF_REF_ID (last_def) == DF_REF_ID (first_def)) 396 return; 397 398 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def)); 399 gcc_assert (dest_node); 400 create_ddg_dep_no_link (g, last_def_node, dest_node, 401 OUTPUT_DEP, REG_DEP, 1); 402 } 403} 404/* Build inter-loop dependencies, by looking at DF analysis backwards. */ 405static void 406build_inter_loop_deps (ddg_ptr g) 407{ 408 unsigned rd_num; 409 struct df_rd_bb_info *rd_bb_info; 410 bitmap_iterator bi; 411 412 rd_bb_info = DF_RD_BB_INFO (g->bb); 413 414 /* Find inter-loop register output, true and anti deps. */ 415 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi) 416 { 417 df_ref rd = DF_DEFS_GET (rd_num); 418 419 add_cross_iteration_register_deps (g, rd); 420 } 421} 422 423 424/* Return true if two specified instructions have mem expr with conflict 425 alias sets. */ 426static bool 427insns_may_alias_p (rtx_insn *insn1, rtx_insn *insn2) 428{ 429 subrtx_iterator::array_type array1; 430 subrtx_iterator::array_type array2; 431 FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST) 432 { 433 const_rtx x1 = *iter1; 434 if (MEM_P (x1)) 435 FOR_EACH_SUBRTX (iter2, array2, PATTERN (insn2), NONCONST) 436 { 437 const_rtx x2 = *iter2; 438 if (MEM_P (x2) && may_alias_p (x2, x1)) 439 return true; 440 } 441 } 442 return false; 443} 444 445/* Given two nodes, analyze their RTL insns and add intra-loop mem deps 446 to ddg G. */ 447static void 448add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) 449{ 450 451 if ((from->cuid == to->cuid) 452 || !insns_may_alias_p (from->insn, to->insn)) 453 /* Do not create edge if memory references have disjoint alias sets 454 or 'to' and 'from' are the same instruction. */ 455 return; 456 457 if (mem_write_insn_p (from->insn)) 458 { 459 if (mem_read_insn_p (to->insn)) 460 create_ddg_dep_no_link (g, from, to, 461 DEBUG_INSN_P (to->insn) 462 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 0); 463 else 464 create_ddg_dep_no_link (g, from, to, 465 DEBUG_INSN_P (to->insn) 466 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 0); 467 } 468 else if (!mem_read_insn_p (to->insn)) 469 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0); 470} 471 472/* Given two nodes, analyze their RTL insns and add inter-loop mem deps 473 to ddg G. */ 474static void 475add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) 476{ 477 if (!insns_may_alias_p (from->insn, to->insn)) 478 /* Do not create edge if memory references have disjoint alias sets. */ 479 return; 480 481 if (mem_write_insn_p (from->insn)) 482 { 483 if (mem_read_insn_p (to->insn)) 484 create_ddg_dep_no_link (g, from, to, 485 DEBUG_INSN_P (to->insn) 486 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1); 487 else if (from->cuid != to->cuid) 488 create_ddg_dep_no_link (g, from, to, 489 DEBUG_INSN_P (to->insn) 490 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1); 491 } 492 else 493 { 494 if (mem_read_insn_p (to->insn)) 495 return; 496 else if (from->cuid != to->cuid) 497 { 498 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); 499 if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn)) 500 create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1); 501 else 502 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); 503 } 504 } 505 506} 507 508/* Perform intra-block Data Dependency analysis and connect the nodes in 509 the DDG. We assume the loop has a single basic block. */ 510static void 511build_intra_loop_deps (ddg_ptr g) 512{ 513 int i; 514 /* Hold the dependency analysis state during dependency calculations. */ 515 struct deps_desc tmp_deps; 516 rtx_insn *head, *tail; 517 518 /* Build the dependence information, using the sched_analyze function. */ 519 init_deps_global (); 520 init_deps (&tmp_deps, false); 521 522 /* Do the intra-block data dependence analysis for the given block. */ 523 get_ebb_head_tail (g->bb, g->bb, &head, &tail); 524 sched_analyze (&tmp_deps, head, tail); 525 526 /* Build intra-loop data dependencies using the scheduler dependency 527 analysis. */ 528 for (i = 0; i < g->num_nodes; i++) 529 { 530 ddg_node_ptr dest_node = &g->nodes[i]; 531 sd_iterator_def sd_it; 532 dep_t dep; 533 534 if (! INSN_P (dest_node->insn)) 535 continue; 536 537 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep) 538 { 539 rtx_insn *src_insn = DEP_PRO (dep); 540 ddg_node_ptr src_node; 541 542 /* Don't add dependencies on debug insns to non-debug insns 543 to avoid codegen differences between -g and -g0. */ 544 if (DEBUG_INSN_P (src_insn) && !DEBUG_INSN_P (dest_node->insn)) 545 continue; 546 547 src_node = get_node_of_insn (g, src_insn); 548 549 if (!src_node) 550 continue; 551 552 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep); 553 } 554 555 /* If this insn modifies memory, add an edge to all insns that access 556 memory. */ 557 if (mem_access_insn_p (dest_node->insn)) 558 { 559 int j; 560 561 for (j = 0; j <= i; j++) 562 { 563 ddg_node_ptr j_node = &g->nodes[j]; 564 if (DEBUG_INSN_P (j_node->insn)) 565 continue; 566 if (mem_access_insn_p (j_node->insn)) 567 { 568 /* Don't bother calculating inter-loop dep if an intra-loop dep 569 already exists. */ 570 if (! bitmap_bit_p (dest_node->successors, j)) 571 add_inter_loop_mem_dep (g, dest_node, j_node); 572 /* If -fmodulo-sched-allow-regmoves 573 is set certain anti-dep edges are not created. 574 It might be that these anti-dep edges are on the 575 path from one memory instruction to another such that 576 removing these edges could cause a violation of the 577 memory dependencies. Thus we add intra edges between 578 every two memory instructions in this case. */ 579 if (flag_modulo_sched_allow_regmoves 580 && !bitmap_bit_p (dest_node->predecessors, j)) 581 add_intra_loop_mem_dep (g, j_node, dest_node); 582 } 583 } 584 } 585 } 586 587 /* Free the INSN_LISTs. */ 588 finish_deps_global (); 589 free_deps (&tmp_deps); 590 591 /* Free dependencies. */ 592 sched_free_deps (head, tail, false); 593} 594 595 596/* Given a basic block, create its DDG and return a pointer to a variable 597 of ddg type that represents it. 598 Initialize the ddg structure fields to the appropriate values. */ 599ddg_ptr 600create_ddg (basic_block bb, int closing_branch_deps) 601{ 602 ddg_ptr g; 603 rtx_insn *insn, *first_note; 604 int i; 605 int num_nodes = 0; 606 607 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg)); 608 609 g->bb = bb; 610 g->closing_branch_deps = closing_branch_deps; 611 612 /* Count the number of insns in the BB. */ 613 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 614 insn = NEXT_INSN (insn)) 615 { 616 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE) 617 continue; 618 619 if (DEBUG_INSN_P (insn)) 620 g->num_debug++; 621 else 622 { 623 if (mem_read_insn_p (insn)) 624 g->num_loads++; 625 if (mem_write_insn_p (insn)) 626 g->num_stores++; 627 } 628 num_nodes++; 629 } 630 631 /* There is nothing to do for this BB. */ 632 if ((num_nodes - g->num_debug) <= 1) 633 { 634 free (g); 635 return NULL; 636 } 637 638 /* Allocate the nodes array, and initialize the nodes. */ 639 g->num_nodes = num_nodes; 640 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); 641 g->closing_branch = NULL; 642 i = 0; 643 first_note = NULL; 644 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 645 insn = NEXT_INSN (insn)) 646 { 647 if (! INSN_P (insn)) 648 { 649 if (! first_note && NOTE_P (insn) 650 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK) 651 first_note = insn; 652 continue; 653 } 654 if (JUMP_P (insn)) 655 { 656 gcc_assert (!g->closing_branch); 657 g->closing_branch = &g->nodes[i]; 658 } 659 else if (GET_CODE (PATTERN (insn)) == USE) 660 { 661 if (! first_note) 662 first_note = insn; 663 continue; 664 } 665 666 g->nodes[i].cuid = i; 667 g->nodes[i].successors = sbitmap_alloc (num_nodes); 668 bitmap_clear (g->nodes[i].successors); 669 g->nodes[i].predecessors = sbitmap_alloc (num_nodes); 670 bitmap_clear (g->nodes[i].predecessors); 671 g->nodes[i].first_note = (first_note ? first_note : insn); 672 g->nodes[i++].insn = insn; 673 first_note = NULL; 674 } 675 676 /* We must have found a branch in DDG. */ 677 gcc_assert (g->closing_branch); 678 679 680 /* Build the data dependency graph. */ 681 build_intra_loop_deps (g); 682 build_inter_loop_deps (g); 683 return g; 684} 685 686/* Free all the memory allocated for the DDG. */ 687void 688free_ddg (ddg_ptr g) 689{ 690 int i; 691 692 if (!g) 693 return; 694 695 for (i = 0; i < g->num_nodes; i++) 696 { 697 ddg_edge_ptr e = g->nodes[i].out; 698 699 while (e) 700 { 701 ddg_edge_ptr next = e->next_out; 702 703 free (e); 704 e = next; 705 } 706 sbitmap_free (g->nodes[i].successors); 707 sbitmap_free (g->nodes[i].predecessors); 708 } 709 if (g->num_backarcs > 0) 710 free (g->backarcs); 711 free (g->nodes); 712 free (g); 713} 714 715void 716print_ddg_edge (FILE *file, ddg_edge_ptr e) 717{ 718 char dep_c; 719 720 switch (e->type) 721 { 722 case OUTPUT_DEP : 723 dep_c = 'O'; 724 break; 725 case ANTI_DEP : 726 dep_c = 'A'; 727 break; 728 default: 729 dep_c = 'T'; 730 } 731 732 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), 733 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); 734} 735 736/* Print the DDG nodes with there in/out edges to the dump file. */ 737void 738print_ddg (FILE *file, ddg_ptr g) 739{ 740 int i; 741 742 for (i = 0; i < g->num_nodes; i++) 743 { 744 ddg_edge_ptr e; 745 746 fprintf (file, "Node num: %d\n", g->nodes[i].cuid); 747 print_rtl_single (file, g->nodes[i].insn); 748 fprintf (file, "OUT ARCS: "); 749 for (e = g->nodes[i].out; e; e = e->next_out) 750 print_ddg_edge (file, e); 751 752 fprintf (file, "\nIN ARCS: "); 753 for (e = g->nodes[i].in; e; e = e->next_in) 754 print_ddg_edge (file, e); 755 756 fprintf (file, "\n"); 757 } 758} 759 760/* Print the given DDG in VCG format. */ 761DEBUG_FUNCTION void 762vcg_print_ddg (FILE *file, ddg_ptr g) 763{ 764 int src_cuid; 765 766 fprintf (file, "graph: {\n"); 767 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) 768 { 769 ddg_edge_ptr e; 770 int src_uid = INSN_UID (g->nodes[src_cuid].insn); 771 772 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); 773 print_rtl_single (file, g->nodes[src_cuid].insn); 774 fprintf (file, "\"}\n"); 775 for (e = g->nodes[src_cuid].out; e; e = e->next_out) 776 { 777 int dst_uid = INSN_UID (e->dest->insn); 778 int dst_cuid = e->dest->cuid; 779 780 /* Give the backarcs a different color. */ 781 if (e->distance > 0) 782 fprintf (file, "backedge: {color: red "); 783 else 784 fprintf (file, "edge: { "); 785 786 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); 787 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); 788 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance); 789 } 790 } 791 fprintf (file, "}\n"); 792} 793 794/* Dump the sccs in SCCS. */ 795void 796print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g) 797{ 798 unsigned int u = 0; 799 sbitmap_iterator sbi; 800 int i; 801 802 if (!file) 803 return; 804 805 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs); 806 for (i = 0; i < sccs->num_sccs; i++) 807 { 808 fprintf (file, "SCC number: %d\n", i); 809 EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi) 810 { 811 fprintf (file, "insn num %d\n", u); 812 print_rtl_single (file, g->nodes[u].insn); 813 } 814 } 815 fprintf (file, "\n"); 816} 817 818/* Create an edge and initialize it with given values. */ 819static ddg_edge_ptr 820create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, 821 dep_type t, dep_data_type dt, int l, int d) 822{ 823 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); 824 825 e->src = src; 826 e->dest = dest; 827 e->type = t; 828 e->data_type = dt; 829 e->latency = l; 830 e->distance = d; 831 e->next_in = e->next_out = NULL; 832 e->aux.info = 0; 833 return e; 834} 835 836/* Add the given edge to the in/out linked lists of the DDG nodes. */ 837static void 838add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) 839{ 840 ddg_node_ptr src = e->src; 841 ddg_node_ptr dest = e->dest; 842 843 /* Should have allocated the sbitmaps. */ 844 gcc_assert (src->successors && dest->predecessors); 845 846 bitmap_set_bit (src->successors, dest->cuid); 847 bitmap_set_bit (dest->predecessors, src->cuid); 848 e->next_in = dest->in; 849 dest->in = e; 850 e->next_out = src->out; 851 src->out = e; 852} 853 854 855 856/* Algorithm for computing the recurrence_length of an scc. We assume at 857 for now that cycles in the data dependence graph contain a single backarc. 858 This simplifies the algorithm, and can be generalized later. */ 859static void 860set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g) 861{ 862 int j; 863 int result = -1; 864 865 for (j = 0; j < scc->num_backarcs; j++) 866 { 867 ddg_edge_ptr backarc = scc->backarcs[j]; 868 int length; 869 int distance = backarc->distance; 870 ddg_node_ptr src = backarc->dest; 871 ddg_node_ptr dest = backarc->src; 872 873 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes); 874 if (length < 0 ) 875 { 876 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */ 877 continue; 878 } 879 length += backarc->latency; 880 result = MAX (result, (length / distance)); 881 } 882 scc->recurrence_length = result; 883} 884 885/* Create a new SCC given the set of its nodes. Compute its recurrence_length 886 and mark edges that belong to this scc as IN_SCC. */ 887static ddg_scc_ptr 888create_scc (ddg_ptr g, sbitmap nodes) 889{ 890 ddg_scc_ptr scc; 891 unsigned int u = 0; 892 sbitmap_iterator sbi; 893 894 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); 895 scc->backarcs = NULL; 896 scc->num_backarcs = 0; 897 scc->nodes = sbitmap_alloc (g->num_nodes); 898 bitmap_copy (scc->nodes, nodes); 899 900 /* Mark the backarcs that belong to this SCC. */ 901 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) 902 { 903 ddg_edge_ptr e; 904 ddg_node_ptr n = &g->nodes[u]; 905 906 for (e = n->out; e; e = e->next_out) 907 if (bitmap_bit_p (nodes, e->dest->cuid)) 908 { 909 e->aux.count = IN_SCC; 910 if (e->distance > 0) 911 add_backarc_to_scc (scc, e); 912 } 913 } 914 915 set_recurrence_length (scc, g); 916 return scc; 917} 918 919/* Cleans the memory allocation of a given SCC. */ 920static void 921free_scc (ddg_scc_ptr scc) 922{ 923 if (!scc) 924 return; 925 926 sbitmap_free (scc->nodes); 927 if (scc->num_backarcs > 0) 928 free (scc->backarcs); 929 free (scc); 930} 931 932 933/* Add a given edge known to be a backarc to the given DDG. */ 934static void 935add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) 936{ 937 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); 938 939 add_edge_to_ddg (g, e); 940 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); 941 g->backarcs[g->num_backarcs++] = e; 942} 943 944/* Add backarc to an SCC. */ 945static void 946add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) 947{ 948 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); 949 950 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); 951 scc->backarcs[scc->num_backarcs++] = e; 952} 953 954/* Add the given SCC to the DDG. */ 955static void 956add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) 957{ 958 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); 959 960 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); 961 g->sccs[g->num_sccs++] = scc; 962} 963 964/* Given the instruction INSN return the node that represents it. */ 965ddg_node_ptr 966get_node_of_insn (ddg_ptr g, rtx_insn *insn) 967{ 968 int i; 969 970 for (i = 0; i < g->num_nodes; i++) 971 if (insn == g->nodes[i].insn) 972 return &g->nodes[i]; 973 return NULL; 974} 975 976/* Given a set OPS of nodes in the DDG, find the set of their successors 977 which are not in OPS, and set their bits in SUCC. Bits corresponding to 978 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ 979void 980find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) 981{ 982 unsigned int i = 0; 983 sbitmap_iterator sbi; 984 985 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) 986 { 987 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); 988 bitmap_ior (succ, succ, node_succ); 989 }; 990 991 /* We want those that are not in ops. */ 992 bitmap_and_compl (succ, succ, ops); 993} 994 995/* Given a set OPS of nodes in the DDG, find the set of their predecessors 996 which are not in OPS, and set their bits in PREDS. Bits corresponding to 997 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ 998void 999find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) 1000{ 1001 unsigned int i = 0; 1002 sbitmap_iterator sbi; 1003 1004 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) 1005 { 1006 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); 1007 bitmap_ior (preds, preds, node_preds); 1008 }; 1009 1010 /* We want those that are not in ops. */ 1011 bitmap_and_compl (preds, preds, ops); 1012} 1013 1014 1015/* Compare function to be passed to qsort to order the backarcs in descending 1016 recMII order. */ 1017static int 1018compare_sccs (const void *s1, const void *s2) 1019{ 1020 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length; 1021 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length; 1022 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); 1023 1024} 1025 1026/* Order the backarcs in descending recMII order using compare_sccs. */ 1027static void 1028order_sccs (ddg_all_sccs_ptr g) 1029{ 1030 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), 1031 (int (*) (const void *, const void *)) compare_sccs); 1032} 1033 1034#ifdef ENABLE_CHECKING 1035/* Check that every node in SCCS belongs to exactly one strongly connected 1036 component and that no element of SCCS is empty. */ 1037static void 1038check_sccs (ddg_all_sccs_ptr sccs, int num_nodes) 1039{ 1040 int i = 0; 1041 sbitmap tmp = sbitmap_alloc (num_nodes); 1042 1043 bitmap_clear (tmp); 1044 for (i = 0; i < sccs->num_sccs; i++) 1045 { 1046 gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes)); 1047 /* Verify that every node in sccs is in exactly one strongly 1048 connected component. */ 1049 gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes)); 1050 bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes); 1051 } 1052 sbitmap_free (tmp); 1053} 1054#endif 1055 1056/* Perform the Strongly Connected Components decomposing algorithm on the 1057 DDG and return DDG_ALL_SCCS structure that contains them. */ 1058ddg_all_sccs_ptr 1059create_ddg_all_sccs (ddg_ptr g) 1060{ 1061 int i; 1062 int num_nodes = g->num_nodes; 1063 sbitmap from = sbitmap_alloc (num_nodes); 1064 sbitmap to = sbitmap_alloc (num_nodes); 1065 sbitmap scc_nodes = sbitmap_alloc (num_nodes); 1066 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) 1067 xmalloc (sizeof (struct ddg_all_sccs)); 1068 1069 sccs->ddg = g; 1070 sccs->sccs = NULL; 1071 sccs->num_sccs = 0; 1072 1073 for (i = 0; i < g->num_backarcs; i++) 1074 { 1075 ddg_scc_ptr scc; 1076 ddg_edge_ptr backarc = g->backarcs[i]; 1077 ddg_node_ptr src = backarc->src; 1078 ddg_node_ptr dest = backarc->dest; 1079 1080 /* If the backarc already belongs to an SCC, continue. */ 1081 if (backarc->aux.count == IN_SCC) 1082 continue; 1083 1084 bitmap_clear (scc_nodes); 1085 bitmap_clear (from); 1086 bitmap_clear (to); 1087 bitmap_set_bit (from, dest->cuid); 1088 bitmap_set_bit (to, src->cuid); 1089 1090 if (find_nodes_on_paths (scc_nodes, g, from, to)) 1091 { 1092 scc = create_scc (g, scc_nodes); 1093 add_scc_to_ddg (sccs, scc); 1094 } 1095 } 1096 order_sccs (sccs); 1097 sbitmap_free (from); 1098 sbitmap_free (to); 1099 sbitmap_free (scc_nodes); 1100#ifdef ENABLE_CHECKING 1101 check_sccs (sccs, num_nodes); 1102#endif 1103 return sccs; 1104} 1105 1106/* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ 1107void 1108free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) 1109{ 1110 int i; 1111 1112 if (!all_sccs) 1113 return; 1114 1115 for (i = 0; i < all_sccs->num_sccs; i++) 1116 free_scc (all_sccs->sccs[i]); 1117 1118 free (all_sccs->sccs); 1119 free (all_sccs); 1120} 1121 1122 1123/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination 1124 nodes - find all nodes that lie on paths from FROM to TO (not excluding 1125 nodes from FROM and TO). Return nonzero if nodes exist. */ 1126int 1127find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) 1128{ 1129 int answer; 1130 int change; 1131 unsigned int u = 0; 1132 int num_nodes = g->num_nodes; 1133 sbitmap_iterator sbi; 1134 1135 sbitmap workset = sbitmap_alloc (num_nodes); 1136 sbitmap reachable_from = sbitmap_alloc (num_nodes); 1137 sbitmap reach_to = sbitmap_alloc (num_nodes); 1138 sbitmap tmp = sbitmap_alloc (num_nodes); 1139 1140 bitmap_copy (reachable_from, from); 1141 bitmap_copy (tmp, from); 1142 1143 change = 1; 1144 while (change) 1145 { 1146 change = 0; 1147 bitmap_copy (workset, tmp); 1148 bitmap_clear (tmp); 1149 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) 1150 { 1151 ddg_edge_ptr e; 1152 ddg_node_ptr u_node = &g->nodes[u]; 1153 1154 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) 1155 { 1156 ddg_node_ptr v_node = e->dest; 1157 int v = v_node->cuid; 1158 1159 if (!bitmap_bit_p (reachable_from, v)) 1160 { 1161 bitmap_set_bit (reachable_from, v); 1162 bitmap_set_bit (tmp, v); 1163 change = 1; 1164 } 1165 } 1166 } 1167 } 1168 1169 bitmap_copy (reach_to, to); 1170 bitmap_copy (tmp, to); 1171 1172 change = 1; 1173 while (change) 1174 { 1175 change = 0; 1176 bitmap_copy (workset, tmp); 1177 bitmap_clear (tmp); 1178 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) 1179 { 1180 ddg_edge_ptr e; 1181 ddg_node_ptr u_node = &g->nodes[u]; 1182 1183 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) 1184 { 1185 ddg_node_ptr v_node = e->src; 1186 int v = v_node->cuid; 1187 1188 if (!bitmap_bit_p (reach_to, v)) 1189 { 1190 bitmap_set_bit (reach_to, v); 1191 bitmap_set_bit (tmp, v); 1192 change = 1; 1193 } 1194 } 1195 } 1196 } 1197 1198 answer = bitmap_and (result, reachable_from, reach_to); 1199 sbitmap_free (workset); 1200 sbitmap_free (reachable_from); 1201 sbitmap_free (reach_to); 1202 sbitmap_free (tmp); 1203 return answer; 1204} 1205 1206 1207/* Updates the counts of U_NODE's successors (that belong to NODES) to be 1208 at-least as large as the count of U_NODE plus the latency between them. 1209 Sets a bit in TMP for each successor whose count was changed (increased). 1210 Returns nonzero if any count was changed. */ 1211static int 1212update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp) 1213{ 1214 ddg_edge_ptr e; 1215 int result = 0; 1216 1217 for (e = u_node->out; e; e = e->next_out) 1218 { 1219 ddg_node_ptr v_node = e->dest; 1220 int v = v_node->cuid; 1221 1222 if (bitmap_bit_p (nodes, v) 1223 && (e->distance == 0) 1224 && (v_node->aux.count < u_node->aux.count + e->latency)) 1225 { 1226 v_node->aux.count = u_node->aux.count + e->latency; 1227 bitmap_set_bit (tmp, v); 1228 result = 1; 1229 } 1230 } 1231 return result; 1232} 1233 1234 1235/* Find the length of a longest path from SRC to DEST in G, 1236 going only through NODES, and disregarding backarcs. */ 1237int 1238longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes) 1239{ 1240 int i; 1241 unsigned int u = 0; 1242 int change = 1; 1243 int result; 1244 int num_nodes = g->num_nodes; 1245 sbitmap workset = sbitmap_alloc (num_nodes); 1246 sbitmap tmp = sbitmap_alloc (num_nodes); 1247 1248 1249 /* Data will hold the distance of the longest path found so far from 1250 src to each node. Initialize to -1 = less than minimum. */ 1251 for (i = 0; i < g->num_nodes; i++) 1252 g->nodes[i].aux.count = -1; 1253 g->nodes[src].aux.count = 0; 1254 1255 bitmap_clear (tmp); 1256 bitmap_set_bit (tmp, src); 1257 1258 while (change) 1259 { 1260 sbitmap_iterator sbi; 1261 1262 change = 0; 1263 bitmap_copy (workset, tmp); 1264 bitmap_clear (tmp); 1265 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) 1266 { 1267 ddg_node_ptr u_node = &g->nodes[u]; 1268 1269 change |= update_dist_to_successors (u_node, nodes, tmp); 1270 } 1271 } 1272 result = g->nodes[dest].aux.count; 1273 sbitmap_free (workset); 1274 sbitmap_free (tmp); 1275 return result; 1276} 1277 1278#endif /* INSN_SCHEDULING */ 1279