1169689Skan/* DDG - Data Dependence Graph implementation. 2169689Skan Copyright (C) 2004, 2005, 2006 3169689Skan Free Software Foundation, Inc. 4169689Skan Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> 5169689Skan 6169689SkanThis file is part of GCC. 7169689Skan 8169689SkanGCC is free software; you can redistribute it and/or modify it under 9169689Skanthe terms of the GNU General Public License as published by the Free 10169689SkanSoftware Foundation; either version 2, or (at your option) any later 11169689Skanversion. 12169689Skan 13169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 14169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 15169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16169689Skanfor more details. 17169689Skan 18169689SkanYou should have received a copy of the GNU General Public License 19169689Skanalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 22169689Skan 23169689Skan 24169689Skan#include "config.h" 25169689Skan#include "system.h" 26169689Skan#include "coretypes.h" 27169689Skan#include "tm.h" 28169689Skan#include "toplev.h" 29169689Skan#include "rtl.h" 30169689Skan#include "tm_p.h" 31169689Skan#include "hard-reg-set.h" 32169689Skan#include "regs.h" 33169689Skan#include "function.h" 34169689Skan#include "flags.h" 35169689Skan#include "insn-config.h" 36169689Skan#include "insn-attr.h" 37169689Skan#include "except.h" 38169689Skan#include "recog.h" 39169689Skan#include "sched-int.h" 40169689Skan#include "target.h" 41169689Skan#include "cfglayout.h" 42169689Skan#include "cfgloop.h" 43169689Skan#include "sbitmap.h" 44169689Skan#include "expr.h" 45169689Skan#include "bitmap.h" 46169689Skan#include "df.h" 47169689Skan#include "ddg.h" 48169689Skan 49169689Skan/* A flag indicating that a ddg edge belongs to an SCC or not. */ 50169689Skanenum edge_flag {NOT_IN_SCC = 0, IN_SCC}; 51169689Skan 52169689Skan/* Forward declarations. */ 53169689Skanstatic void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr); 54169689Skanstatic void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr); 55169689Skanstatic void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr); 56169689Skanstatic void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx); 57169689Skanstatic void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, 58169689Skan dep_type, dep_data_type, int); 59169689Skanstatic ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, 60169689Skan dep_data_type, int, int); 61169689Skanstatic void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr); 62169689Skan 63169689Skan/* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ 64169689Skanstatic bool mem_ref_p; 65169689Skan 66169689Skan/* Auxiliary function for mem_read_insn_p. */ 67169689Skanstatic int 68169689Skanmark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED) 69169689Skan{ 70169689Skan if (MEM_P (*x)) 71169689Skan mem_ref_p = true; 72169689Skan return 0; 73169689Skan} 74169689Skan 75169689Skan/* Auxiliary function for mem_read_insn_p. */ 76169689Skanstatic void 77169689Skanmark_mem_use_1 (rtx *x, void *data) 78169689Skan{ 79169689Skan for_each_rtx (x, mark_mem_use, data); 80169689Skan} 81169689Skan 82169689Skan/* Returns nonzero if INSN reads from memory. */ 83169689Skanstatic bool 84169689Skanmem_read_insn_p (rtx insn) 85169689Skan{ 86169689Skan mem_ref_p = false; 87169689Skan note_uses (&PATTERN (insn), mark_mem_use_1, NULL); 88169689Skan return mem_ref_p; 89169689Skan} 90169689Skan 91169689Skanstatic void 92169689Skanmark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) 93169689Skan{ 94169689Skan if (MEM_P (loc)) 95169689Skan mem_ref_p = true; 96169689Skan} 97169689Skan 98169689Skan/* Returns nonzero if INSN writes to memory. */ 99169689Skanstatic bool 100169689Skanmem_write_insn_p (rtx insn) 101169689Skan{ 102169689Skan mem_ref_p = false; 103169689Skan note_stores (PATTERN (insn), mark_mem_store, NULL); 104169689Skan return mem_ref_p; 105169689Skan} 106169689Skan 107169689Skan/* Returns nonzero if X has access to memory. */ 108169689Skanstatic bool 109169689Skanrtx_mem_access_p (rtx x) 110169689Skan{ 111169689Skan int i, j; 112169689Skan const char *fmt; 113169689Skan enum rtx_code code; 114169689Skan 115169689Skan if (x == 0) 116169689Skan return false; 117169689Skan 118169689Skan if (MEM_P (x)) 119169689Skan return true; 120169689Skan 121169689Skan code = GET_CODE (x); 122169689Skan fmt = GET_RTX_FORMAT (code); 123169689Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 124169689Skan { 125169689Skan if (fmt[i] == 'e') 126169689Skan { 127169689Skan if (rtx_mem_access_p (XEXP (x, i))) 128169689Skan return true; 129169689Skan } 130169689Skan else if (fmt[i] == 'E') 131169689Skan for (j = 0; j < XVECLEN (x, i); j++) 132169689Skan { 133169689Skan if (rtx_mem_access_p (XVECEXP (x, i, j))) 134169689Skan return true; 135169689Skan } 136169689Skan } 137169689Skan return false; 138169689Skan} 139169689Skan 140169689Skan/* Returns nonzero if INSN reads to or writes from memory. */ 141169689Skanstatic bool 142169689Skanmem_access_insn_p (rtx insn) 143169689Skan{ 144169689Skan return rtx_mem_access_p (PATTERN (insn)); 145169689Skan} 146169689Skan 147169689Skan/* Computes the dependence parameters (latency, distance etc.), creates 148169689Skan a ddg_edge and adds it to the given DDG. */ 149169689Skanstatic void 150169689Skancreate_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node, 151169689Skan ddg_node_ptr dest_node, rtx link) 152169689Skan{ 153169689Skan ddg_edge_ptr e; 154169689Skan int latency, distance = 0; 155169689Skan int interloop = (src_node->cuid >= dest_node->cuid); 156169689Skan dep_type t = TRUE_DEP; 157169689Skan dep_data_type dt = (mem_access_insn_p (src_node->insn) 158169689Skan && mem_access_insn_p (dest_node->insn) ? MEM_DEP 159169689Skan : REG_DEP); 160169689Skan 161169689Skan /* For now we don't have an exact calculation of the distance, 162169689Skan so assume 1 conservatively. */ 163169689Skan if (interloop) 164169689Skan distance = 1; 165169689Skan 166169689Skan gcc_assert (link); 167169689Skan 168169689Skan /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ 169169689Skan if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 170169689Skan t = ANTI_DEP; 171169689Skan else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 172169689Skan t = OUTPUT_DEP; 173169689Skan latency = insn_cost (src_node->insn, link, dest_node->insn); 174169689Skan 175169689Skan e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); 176169689Skan 177169689Skan if (interloop) 178169689Skan { 179169689Skan /* Some interloop dependencies are relaxed: 180169689Skan 1. Every insn is output dependent on itself; ignore such deps. 181169689Skan 2. Every true/flow dependence is an anti dependence in the 182169689Skan opposite direction with distance 1; such register deps 183169689Skan will be removed by renaming if broken --- ignore them. */ 184169689Skan if (!(t == OUTPUT_DEP && src_node == dest_node) 185169689Skan && !(t == ANTI_DEP && dt == REG_DEP)) 186169689Skan add_backarc_to_ddg (g, e); 187169689Skan else 188169689Skan free (e); 189169689Skan } 190169689Skan else if (t == ANTI_DEP && dt == REG_DEP) 191169689Skan free (e); /* We can fix broken anti register deps using reg-moves. */ 192169689Skan else 193169689Skan add_edge_to_ddg (g, e); 194169689Skan} 195169689Skan 196169689Skan/* The same as the above function, but it doesn't require a link parameter. */ 197169689Skanstatic void 198169689Skancreate_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, 199169689Skan dep_type d_t, dep_data_type d_dt, int distance) 200169689Skan{ 201169689Skan ddg_edge_ptr e; 202169689Skan int l; 203169689Skan rtx link = alloc_INSN_LIST (to->insn, NULL_RTX); 204169689Skan 205169689Skan if (d_t == ANTI_DEP) 206169689Skan PUT_REG_NOTE_KIND (link, REG_DEP_ANTI); 207169689Skan else if (d_t == OUTPUT_DEP) 208169689Skan PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT); 209169689Skan 210169689Skan l = insn_cost (from->insn, link, to->insn); 211169689Skan free_INSN_LIST_node (link); 212169689Skan 213169689Skan e = create_ddg_edge (from, to, d_t, d_dt, l, distance); 214169689Skan if (distance > 0) 215169689Skan add_backarc_to_ddg (g, e); 216169689Skan else 217169689Skan add_edge_to_ddg (g, e); 218169689Skan} 219169689Skan 220169689Skan 221169689Skan/* Given a downwards exposed register def RD, add inter-loop true dependences 222169689Skan for all its uses in the next iteration, and an output dependence to the 223169689Skan first def of the next iteration. */ 224169689Skanstatic void 225169689Skanadd_deps_for_def (ddg_ptr g, struct df *df, struct df_ref *rd) 226169689Skan{ 227169689Skan int regno = DF_REF_REGNO (rd); 228169689Skan struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (df, g->bb); 229169689Skan struct df_link *r_use; 230169689Skan int use_before_def = false; 231169689Skan rtx def_insn = DF_REF_INSN (rd); 232169689Skan ddg_node_ptr src_node = get_node_of_insn (g, def_insn); 233169689Skan 234169689Skan /* Create and inter-loop true dependence between RD and each of its uses 235169689Skan that is upwards exposed in RD's block. */ 236169689Skan for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next) 237169689Skan { 238169689Skan if (bitmap_bit_p (bb_info->gen, r_use->ref->id)) 239169689Skan { 240169689Skan rtx use_insn = DF_REF_INSN (r_use->ref); 241169689Skan ddg_node_ptr dest_node = get_node_of_insn (g, use_insn); 242169689Skan 243169689Skan gcc_assert (src_node && dest_node); 244169689Skan 245169689Skan /* Any such upwards exposed use appears before the rd def. */ 246169689Skan use_before_def = true; 247169689Skan create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP, 248169689Skan REG_DEP, 1); 249169689Skan } 250169689Skan } 251169689Skan 252169689Skan /* Create an inter-loop output dependence between RD (which is the 253169689Skan last def in its block, being downwards exposed) and the first def 254169689Skan in its block. Avoid creating a self output dependence. Avoid creating 255169689Skan an output dependence if there is a dependence path between the two defs 256169689Skan starting with a true dependence followed by an anti dependence (i.e. if 257169689Skan there is a use between the two defs. */ 258169689Skan if (! use_before_def) 259169689Skan { 260169689Skan struct df_ref *def = df_bb_regno_first_def_find (df, g->bb, regno); 261169689Skan int i; 262169689Skan ddg_node_ptr dest_node; 263169689Skan 264169689Skan if (!def || rd->id == def->id) 265169689Skan return; 266169689Skan 267169689Skan /* Check if there are uses after RD. */ 268169689Skan for (i = src_node->cuid + 1; i < g->num_nodes; i++) 269169689Skan if (df_find_use (df, g->nodes[i].insn, rd->reg)) 270169689Skan return; 271169689Skan 272169689Skan dest_node = get_node_of_insn (g, def->insn); 273169689Skan create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1); 274169689Skan } 275169689Skan} 276169689Skan 277169689Skan/* Given a register USE, add an inter-loop anti dependence to the first 278169689Skan (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed 279169689Skan by a def in the block. */ 280169689Skanstatic void 281169689Skanadd_deps_for_use (ddg_ptr g, struct df *df, struct df_ref *use) 282169689Skan{ 283169689Skan int i; 284169689Skan int regno = DF_REF_REGNO (use); 285169689Skan struct df_ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno); 286169689Skan ddg_node_ptr use_node; 287169689Skan ddg_node_ptr def_node; 288169689Skan struct df_rd_bb_info *bb_info; 289169689Skan 290169689Skan bb_info = DF_RD_BB_INFO (df, g->bb); 291169689Skan 292169689Skan if (!first_def) 293169689Skan return; 294169689Skan 295169689Skan use_node = get_node_of_insn (g, use->insn); 296169689Skan def_node = get_node_of_insn (g, first_def->insn); 297169689Skan 298169689Skan gcc_assert (use_node && def_node); 299169689Skan 300169689Skan /* Make sure there are no defs after USE. */ 301169689Skan for (i = use_node->cuid + 1; i < g->num_nodes; i++) 302169689Skan if (df_find_def (df, g->nodes[i].insn, use->reg)) 303169689Skan return; 304169689Skan /* We must not add ANTI dep when there is an intra-loop TRUE dep in 305169689Skan the opposite direction. If the first_def reaches the USE then there is 306169689Skan such a dep. */ 307169689Skan if (! bitmap_bit_p (bb_info->gen, first_def->id)) 308169689Skan create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1); 309169689Skan} 310169689Skan 311169689Skan/* Build inter-loop dependencies, by looking at DF analysis backwards. */ 312169689Skanstatic void 313169689Skanbuild_inter_loop_deps (ddg_ptr g, struct df *df) 314169689Skan{ 315169689Skan unsigned rd_num, u_num; 316169689Skan struct df_rd_bb_info *rd_bb_info; 317169689Skan struct df_ru_bb_info *ru_bb_info; 318169689Skan bitmap_iterator bi; 319169689Skan 320169689Skan rd_bb_info = DF_RD_BB_INFO (df, g->bb); 321169689Skan 322169689Skan /* Find inter-loop output and true deps by connecting downward exposed defs 323169689Skan to the first def of the BB and to upwards exposed uses. */ 324169689Skan EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi) 325169689Skan { 326169689Skan struct df_ref *rd = DF_DEFS_GET (df, rd_num); 327169689Skan 328169689Skan add_deps_for_def (g, df, rd); 329169689Skan } 330169689Skan 331169689Skan ru_bb_info = DF_RU_BB_INFO (df, g->bb); 332169689Skan 333169689Skan /* Find inter-loop anti deps. We are interested in uses of the block that 334169689Skan appear below all defs; this implies that these uses are killed. */ 335169689Skan EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi) 336169689Skan { 337169689Skan struct df_ref *use = DF_USES_GET (df, u_num); 338169689Skan 339169689Skan /* We are interested in uses of this BB. */ 340169689Skan if (BLOCK_FOR_INSN (use->insn) == g->bb) 341169689Skan add_deps_for_use (g, df, use); 342169689Skan } 343169689Skan} 344169689Skan 345169689Skan/* Given two nodes, analyze their RTL insns and add inter-loop mem deps 346169689Skan to ddg G. */ 347169689Skanstatic void 348169689Skanadd_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) 349169689Skan{ 350169689Skan if (mem_write_insn_p (from->insn)) 351169689Skan { 352169689Skan if (mem_read_insn_p (to->insn)) 353169689Skan create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1); 354169689Skan else if (from->cuid != to->cuid) 355169689Skan create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1); 356169689Skan } 357169689Skan else 358169689Skan { 359169689Skan if (mem_read_insn_p (to->insn)) 360169689Skan return; 361169689Skan else if (from->cuid != to->cuid) 362169689Skan { 363169689Skan create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); 364169689Skan create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); 365169689Skan } 366169689Skan } 367169689Skan 368169689Skan} 369169689Skan 370169689Skan/* Perform intra-block Data Dependency analysis and connect the nodes in 371169689Skan the DDG. We assume the loop has a single basic block. */ 372169689Skanstatic void 373169689Skanbuild_intra_loop_deps (ddg_ptr g) 374169689Skan{ 375169689Skan int i; 376169689Skan /* Hold the dependency analysis state during dependency calculations. */ 377169689Skan struct deps tmp_deps; 378169689Skan rtx head, tail, link; 379169689Skan 380169689Skan /* Build the dependence information, using the sched_analyze function. */ 381169689Skan init_deps_global (); 382169689Skan init_deps (&tmp_deps); 383169689Skan 384169689Skan /* Do the intra-block data dependence analysis for the given block. */ 385169689Skan get_ebb_head_tail (g->bb, g->bb, &head, &tail); 386169689Skan sched_analyze (&tmp_deps, head, tail); 387169689Skan 388169689Skan /* Build intra-loop data dependencies using the scheduler dependency 389169689Skan analysis. */ 390169689Skan for (i = 0; i < g->num_nodes; i++) 391169689Skan { 392169689Skan ddg_node_ptr dest_node = &g->nodes[i]; 393169689Skan 394169689Skan if (! INSN_P (dest_node->insn)) 395169689Skan continue; 396169689Skan 397169689Skan for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1)) 398169689Skan { 399169689Skan ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0)); 400169689Skan 401169689Skan if (!src_node) 402169689Skan continue; 403169689Skan 404169689Skan add_forw_dep (dest_node->insn, link); 405169689Skan create_ddg_dependence (g, src_node, dest_node, 406169689Skan INSN_DEPEND (src_node->insn)); 407169689Skan } 408169689Skan 409169689Skan /* If this insn modifies memory, add an edge to all insns that access 410169689Skan memory. */ 411169689Skan if (mem_access_insn_p (dest_node->insn)) 412169689Skan { 413169689Skan int j; 414169689Skan 415169689Skan for (j = 0; j <= i; j++) 416169689Skan { 417169689Skan ddg_node_ptr j_node = &g->nodes[j]; 418169689Skan if (mem_access_insn_p (j_node->insn)) 419169689Skan /* Don't bother calculating inter-loop dep if an intra-loop dep 420169689Skan already exists. */ 421169689Skan if (! TEST_BIT (dest_node->successors, j)) 422169689Skan add_inter_loop_mem_dep (g, dest_node, j_node); 423169689Skan } 424169689Skan } 425169689Skan } 426169689Skan 427169689Skan /* Free the INSN_LISTs. */ 428169689Skan finish_deps_global (); 429169689Skan free_deps (&tmp_deps); 430169689Skan} 431169689Skan 432169689Skan 433169689Skan/* Given a basic block, create its DDG and return a pointer to a variable 434169689Skan of ddg type that represents it. 435169689Skan Initialize the ddg structure fields to the appropriate values. */ 436169689Skanddg_ptr 437169689Skancreate_ddg (basic_block bb, struct df *df, int closing_branch_deps) 438169689Skan{ 439169689Skan ddg_ptr g; 440169689Skan rtx insn, first_note; 441169689Skan int i; 442169689Skan int num_nodes = 0; 443169689Skan 444169689Skan g = (ddg_ptr) xcalloc (1, sizeof (struct ddg)); 445169689Skan 446169689Skan g->bb = bb; 447169689Skan g->closing_branch_deps = closing_branch_deps; 448169689Skan 449169689Skan /* Count the number of insns in the BB. */ 450169689Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 451169689Skan insn = NEXT_INSN (insn)) 452169689Skan { 453169689Skan if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE) 454169689Skan continue; 455169689Skan 456169689Skan if (mem_read_insn_p (insn)) 457169689Skan g->num_loads++; 458169689Skan if (mem_write_insn_p (insn)) 459169689Skan g->num_stores++; 460169689Skan num_nodes++; 461169689Skan } 462169689Skan 463169689Skan /* There is nothing to do for this BB. */ 464169689Skan if (num_nodes <= 1) 465169689Skan { 466169689Skan free (g); 467169689Skan return NULL; 468169689Skan } 469169689Skan 470169689Skan /* Allocate the nodes array, and initialize the nodes. */ 471169689Skan g->num_nodes = num_nodes; 472169689Skan g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); 473169689Skan g->closing_branch = NULL; 474169689Skan i = 0; 475169689Skan first_note = NULL_RTX; 476169689Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 477169689Skan insn = NEXT_INSN (insn)) 478169689Skan { 479169689Skan if (! INSN_P (insn)) 480169689Skan { 481169689Skan if (! first_note && NOTE_P (insn) 482169689Skan && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) 483169689Skan first_note = insn; 484169689Skan continue; 485169689Skan } 486169689Skan if (JUMP_P (insn)) 487169689Skan { 488169689Skan gcc_assert (!g->closing_branch); 489169689Skan g->closing_branch = &g->nodes[i]; 490169689Skan } 491169689Skan else if (GET_CODE (PATTERN (insn)) == USE) 492169689Skan { 493169689Skan if (! first_note) 494169689Skan first_note = insn; 495169689Skan continue; 496169689Skan } 497169689Skan 498169689Skan g->nodes[i].cuid = i; 499169689Skan g->nodes[i].successors = sbitmap_alloc (num_nodes); 500169689Skan sbitmap_zero (g->nodes[i].successors); 501169689Skan g->nodes[i].predecessors = sbitmap_alloc (num_nodes); 502169689Skan sbitmap_zero (g->nodes[i].predecessors); 503169689Skan g->nodes[i].first_note = (first_note ? first_note : insn); 504169689Skan g->nodes[i++].insn = insn; 505169689Skan first_note = NULL_RTX; 506169689Skan } 507169689Skan 508169689Skan /* We must have found a branch in DDG. */ 509169689Skan gcc_assert (g->closing_branch); 510169689Skan 511169689Skan 512169689Skan /* Build the data dependency graph. */ 513169689Skan build_intra_loop_deps (g); 514169689Skan build_inter_loop_deps (g, df); 515169689Skan return g; 516169689Skan} 517169689Skan 518169689Skan/* Free all the memory allocated for the DDG. */ 519169689Skanvoid 520169689Skanfree_ddg (ddg_ptr g) 521169689Skan{ 522169689Skan int i; 523169689Skan 524169689Skan if (!g) 525169689Skan return; 526169689Skan 527169689Skan for (i = 0; i < g->num_nodes; i++) 528169689Skan { 529169689Skan ddg_edge_ptr e = g->nodes[i].out; 530169689Skan 531169689Skan while (e) 532169689Skan { 533169689Skan ddg_edge_ptr next = e->next_out; 534169689Skan 535169689Skan free (e); 536169689Skan e = next; 537169689Skan } 538169689Skan sbitmap_free (g->nodes[i].successors); 539169689Skan sbitmap_free (g->nodes[i].predecessors); 540169689Skan } 541169689Skan if (g->num_backarcs > 0) 542169689Skan free (g->backarcs); 543169689Skan free (g->nodes); 544169689Skan free (g); 545169689Skan} 546169689Skan 547169689Skanvoid 548169689Skanprint_ddg_edge (FILE *file, ddg_edge_ptr e) 549169689Skan{ 550169689Skan char dep_c; 551169689Skan 552169689Skan switch (e->type) { 553169689Skan case OUTPUT_DEP : 554169689Skan dep_c = 'O'; 555169689Skan break; 556169689Skan case ANTI_DEP : 557169689Skan dep_c = 'A'; 558169689Skan break; 559169689Skan default: 560169689Skan dep_c = 'T'; 561169689Skan } 562169689Skan 563169689Skan fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), 564169689Skan dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); 565169689Skan} 566169689Skan 567169689Skan/* Print the DDG nodes with there in/out edges to the dump file. */ 568169689Skanvoid 569169689Skanprint_ddg (FILE *file, ddg_ptr g) 570169689Skan{ 571169689Skan int i; 572169689Skan 573169689Skan for (i = 0; i < g->num_nodes; i++) 574169689Skan { 575169689Skan ddg_edge_ptr e; 576169689Skan 577169689Skan print_rtl_single (file, g->nodes[i].insn); 578169689Skan fprintf (file, "OUT ARCS: "); 579169689Skan for (e = g->nodes[i].out; e; e = e->next_out) 580169689Skan print_ddg_edge (file, e); 581169689Skan 582169689Skan fprintf (file, "\nIN ARCS: "); 583169689Skan for (e = g->nodes[i].in; e; e = e->next_in) 584169689Skan print_ddg_edge (file, e); 585169689Skan 586169689Skan fprintf (file, "\n"); 587169689Skan } 588169689Skan} 589169689Skan 590169689Skan/* Print the given DDG in VCG format. */ 591169689Skanvoid 592169689Skanvcg_print_ddg (FILE *file, ddg_ptr g) 593169689Skan{ 594169689Skan int src_cuid; 595169689Skan 596169689Skan fprintf (file, "graph: {\n"); 597169689Skan for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) 598169689Skan { 599169689Skan ddg_edge_ptr e; 600169689Skan int src_uid = INSN_UID (g->nodes[src_cuid].insn); 601169689Skan 602169689Skan fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); 603169689Skan print_rtl_single (file, g->nodes[src_cuid].insn); 604169689Skan fprintf (file, "\"}\n"); 605169689Skan for (e = g->nodes[src_cuid].out; e; e = e->next_out) 606169689Skan { 607169689Skan int dst_uid = INSN_UID (e->dest->insn); 608169689Skan int dst_cuid = e->dest->cuid; 609169689Skan 610169689Skan /* Give the backarcs a different color. */ 611169689Skan if (e->distance > 0) 612169689Skan fprintf (file, "backedge: {color: red "); 613169689Skan else 614169689Skan fprintf (file, "edge: { "); 615169689Skan 616169689Skan fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); 617169689Skan fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); 618169689Skan fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance); 619169689Skan } 620169689Skan } 621169689Skan fprintf (file, "}\n"); 622169689Skan} 623169689Skan 624169689Skan/* Create an edge and initialize it with given values. */ 625169689Skanstatic ddg_edge_ptr 626169689Skancreate_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, 627169689Skan dep_type t, dep_data_type dt, int l, int d) 628169689Skan{ 629169689Skan ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); 630169689Skan 631169689Skan e->src = src; 632169689Skan e->dest = dest; 633169689Skan e->type = t; 634169689Skan e->data_type = dt; 635169689Skan e->latency = l; 636169689Skan e->distance = d; 637169689Skan e->next_in = e->next_out = NULL; 638169689Skan e->aux.info = 0; 639169689Skan return e; 640169689Skan} 641169689Skan 642169689Skan/* Add the given edge to the in/out linked lists of the DDG nodes. */ 643169689Skanstatic void 644169689Skanadd_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) 645169689Skan{ 646169689Skan ddg_node_ptr src = e->src; 647169689Skan ddg_node_ptr dest = e->dest; 648169689Skan 649169689Skan /* Should have allocated the sbitmaps. */ 650169689Skan gcc_assert (src->successors && dest->predecessors); 651169689Skan 652169689Skan SET_BIT (src->successors, dest->cuid); 653169689Skan SET_BIT (dest->predecessors, src->cuid); 654169689Skan e->next_in = dest->in; 655169689Skan dest->in = e; 656169689Skan e->next_out = src->out; 657169689Skan src->out = e; 658169689Skan} 659169689Skan 660169689Skan 661169689Skan 662169689Skan/* Algorithm for computing the recurrence_length of an scc. We assume at 663169689Skan for now that cycles in the data dependence graph contain a single backarc. 664169689Skan This simplifies the algorithm, and can be generalized later. */ 665169689Skanstatic void 666169689Skanset_recurrence_length (ddg_scc_ptr scc, ddg_ptr g) 667169689Skan{ 668169689Skan int j; 669169689Skan int result = -1; 670169689Skan 671169689Skan for (j = 0; j < scc->num_backarcs; j++) 672169689Skan { 673169689Skan ddg_edge_ptr backarc = scc->backarcs[j]; 674169689Skan int length; 675169689Skan int distance = backarc->distance; 676169689Skan ddg_node_ptr src = backarc->dest; 677169689Skan ddg_node_ptr dest = backarc->src; 678169689Skan 679169689Skan length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes); 680169689Skan if (length < 0 ) 681169689Skan { 682169689Skan /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */ 683169689Skan continue; 684169689Skan } 685169689Skan length += backarc->latency; 686169689Skan result = MAX (result, (length / distance)); 687169689Skan } 688169689Skan scc->recurrence_length = result; 689169689Skan} 690169689Skan 691169689Skan/* Create a new SCC given the set of its nodes. Compute its recurrence_length 692169689Skan and mark edges that belong to this scc as IN_SCC. */ 693169689Skanstatic ddg_scc_ptr 694169689Skancreate_scc (ddg_ptr g, sbitmap nodes) 695169689Skan{ 696169689Skan ddg_scc_ptr scc; 697169689Skan unsigned int u = 0; 698169689Skan sbitmap_iterator sbi; 699169689Skan 700169689Skan scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); 701169689Skan scc->backarcs = NULL; 702169689Skan scc->num_backarcs = 0; 703169689Skan scc->nodes = sbitmap_alloc (g->num_nodes); 704169689Skan sbitmap_copy (scc->nodes, nodes); 705169689Skan 706169689Skan /* Mark the backarcs that belong to this SCC. */ 707169689Skan EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi) 708169689Skan { 709169689Skan ddg_edge_ptr e; 710169689Skan ddg_node_ptr n = &g->nodes[u]; 711169689Skan 712169689Skan for (e = n->out; e; e = e->next_out) 713169689Skan if (TEST_BIT (nodes, e->dest->cuid)) 714169689Skan { 715169689Skan e->aux.count = IN_SCC; 716169689Skan if (e->distance > 0) 717169689Skan add_backarc_to_scc (scc, e); 718169689Skan } 719169689Skan } 720169689Skan 721169689Skan set_recurrence_length (scc, g); 722169689Skan return scc; 723169689Skan} 724169689Skan 725169689Skan/* Cleans the memory allocation of a given SCC. */ 726169689Skanstatic void 727169689Skanfree_scc (ddg_scc_ptr scc) 728169689Skan{ 729169689Skan if (!scc) 730169689Skan return; 731169689Skan 732169689Skan sbitmap_free (scc->nodes); 733169689Skan if (scc->num_backarcs > 0) 734169689Skan free (scc->backarcs); 735169689Skan free (scc); 736169689Skan} 737169689Skan 738169689Skan 739169689Skan/* Add a given edge known to be a backarc to the given DDG. */ 740169689Skanstatic void 741169689Skanadd_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) 742169689Skan{ 743169689Skan int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); 744169689Skan 745169689Skan add_edge_to_ddg (g, e); 746169689Skan g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); 747169689Skan g->backarcs[g->num_backarcs++] = e; 748169689Skan} 749169689Skan 750169689Skan/* Add backarc to an SCC. */ 751169689Skanstatic void 752169689Skanadd_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) 753169689Skan{ 754169689Skan int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); 755169689Skan 756169689Skan scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); 757169689Skan scc->backarcs[scc->num_backarcs++] = e; 758169689Skan} 759169689Skan 760169689Skan/* Add the given SCC to the DDG. */ 761169689Skanstatic void 762169689Skanadd_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) 763169689Skan{ 764169689Skan int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); 765169689Skan 766169689Skan g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); 767169689Skan g->sccs[g->num_sccs++] = scc; 768169689Skan} 769169689Skan 770169689Skan/* Given the instruction INSN return the node that represents it. */ 771169689Skanddg_node_ptr 772169689Skanget_node_of_insn (ddg_ptr g, rtx insn) 773169689Skan{ 774169689Skan int i; 775169689Skan 776169689Skan for (i = 0; i < g->num_nodes; i++) 777169689Skan if (insn == g->nodes[i].insn) 778169689Skan return &g->nodes[i]; 779169689Skan return NULL; 780169689Skan} 781169689Skan 782169689Skan/* Given a set OPS of nodes in the DDG, find the set of their successors 783169689Skan which are not in OPS, and set their bits in SUCC. Bits corresponding to 784169689Skan OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ 785169689Skanvoid 786169689Skanfind_successors (sbitmap succ, ddg_ptr g, sbitmap ops) 787169689Skan{ 788169689Skan unsigned int i = 0; 789169689Skan sbitmap_iterator sbi; 790169689Skan 791169689Skan EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) 792169689Skan { 793169689Skan const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); 794169689Skan sbitmap_a_or_b (succ, succ, node_succ); 795169689Skan }; 796169689Skan 797169689Skan /* We want those that are not in ops. */ 798169689Skan sbitmap_difference (succ, succ, ops); 799169689Skan} 800169689Skan 801169689Skan/* Given a set OPS of nodes in the DDG, find the set of their predecessors 802169689Skan which are not in OPS, and set their bits in PREDS. Bits corresponding to 803169689Skan OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ 804169689Skanvoid 805169689Skanfind_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) 806169689Skan{ 807169689Skan unsigned int i = 0; 808169689Skan sbitmap_iterator sbi; 809169689Skan 810169689Skan EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) 811169689Skan { 812169689Skan const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); 813169689Skan sbitmap_a_or_b (preds, preds, node_preds); 814169689Skan }; 815169689Skan 816169689Skan /* We want those that are not in ops. */ 817169689Skan sbitmap_difference (preds, preds, ops); 818169689Skan} 819169689Skan 820169689Skan 821169689Skan/* Compare function to be passed to qsort to order the backarcs in descending 822169689Skan recMII order. */ 823169689Skanstatic int 824169689Skancompare_sccs (const void *s1, const void *s2) 825169689Skan{ 826169689Skan int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length; 827169689Skan int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length; 828169689Skan return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); 829169689Skan 830169689Skan} 831169689Skan 832169689Skan/* Order the backarcs in descending recMII order using compare_sccs. */ 833169689Skanstatic void 834169689Skanorder_sccs (ddg_all_sccs_ptr g) 835169689Skan{ 836169689Skan qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), 837169689Skan (int (*) (const void *, const void *)) compare_sccs); 838169689Skan} 839169689Skan 840169689Skan/* Perform the Strongly Connected Components decomposing algorithm on the 841169689Skan DDG and return DDG_ALL_SCCS structure that contains them. */ 842169689Skanddg_all_sccs_ptr 843169689Skancreate_ddg_all_sccs (ddg_ptr g) 844169689Skan{ 845169689Skan int i; 846169689Skan int num_nodes = g->num_nodes; 847169689Skan sbitmap from = sbitmap_alloc (num_nodes); 848169689Skan sbitmap to = sbitmap_alloc (num_nodes); 849169689Skan sbitmap scc_nodes = sbitmap_alloc (num_nodes); 850169689Skan ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) 851169689Skan xmalloc (sizeof (struct ddg_all_sccs)); 852169689Skan 853169689Skan sccs->ddg = g; 854169689Skan sccs->sccs = NULL; 855169689Skan sccs->num_sccs = 0; 856169689Skan 857169689Skan for (i = 0; i < g->num_backarcs; i++) 858169689Skan { 859169689Skan ddg_scc_ptr scc; 860169689Skan ddg_edge_ptr backarc = g->backarcs[i]; 861169689Skan ddg_node_ptr src = backarc->src; 862169689Skan ddg_node_ptr dest = backarc->dest; 863169689Skan 864169689Skan /* If the backarc already belongs to an SCC, continue. */ 865169689Skan if (backarc->aux.count == IN_SCC) 866169689Skan continue; 867169689Skan 868169689Skan sbitmap_zero (from); 869169689Skan sbitmap_zero (to); 870169689Skan SET_BIT (from, dest->cuid); 871169689Skan SET_BIT (to, src->cuid); 872169689Skan 873169689Skan if (find_nodes_on_paths (scc_nodes, g, from, to)) 874169689Skan { 875169689Skan scc = create_scc (g, scc_nodes); 876169689Skan add_scc_to_ddg (sccs, scc); 877169689Skan } 878169689Skan } 879169689Skan order_sccs (sccs); 880169689Skan sbitmap_free (from); 881169689Skan sbitmap_free (to); 882169689Skan sbitmap_free (scc_nodes); 883169689Skan return sccs; 884169689Skan} 885169689Skan 886169689Skan/* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ 887169689Skanvoid 888169689Skanfree_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) 889169689Skan{ 890169689Skan int i; 891169689Skan 892169689Skan if (!all_sccs) 893169689Skan return; 894169689Skan 895169689Skan for (i = 0; i < all_sccs->num_sccs; i++) 896169689Skan free_scc (all_sccs->sccs[i]); 897169689Skan 898169689Skan free (all_sccs); 899169689Skan} 900169689Skan 901169689Skan 902169689Skan/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination 903169689Skan nodes - find all nodes that lie on paths from FROM to TO (not excluding 904169689Skan nodes from FROM and TO). Return nonzero if nodes exist. */ 905169689Skanint 906169689Skanfind_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) 907169689Skan{ 908169689Skan int answer; 909169689Skan int change; 910169689Skan unsigned int u = 0; 911169689Skan int num_nodes = g->num_nodes; 912169689Skan sbitmap_iterator sbi; 913169689Skan 914169689Skan sbitmap workset = sbitmap_alloc (num_nodes); 915169689Skan sbitmap reachable_from = sbitmap_alloc (num_nodes); 916169689Skan sbitmap reach_to = sbitmap_alloc (num_nodes); 917169689Skan sbitmap tmp = sbitmap_alloc (num_nodes); 918169689Skan 919169689Skan sbitmap_copy (reachable_from, from); 920169689Skan sbitmap_copy (tmp, from); 921169689Skan 922169689Skan change = 1; 923169689Skan while (change) 924169689Skan { 925169689Skan change = 0; 926169689Skan sbitmap_copy (workset, tmp); 927169689Skan sbitmap_zero (tmp); 928169689Skan EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 929169689Skan { 930169689Skan ddg_edge_ptr e; 931169689Skan ddg_node_ptr u_node = &g->nodes[u]; 932169689Skan 933169689Skan for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) 934169689Skan { 935169689Skan ddg_node_ptr v_node = e->dest; 936169689Skan int v = v_node->cuid; 937169689Skan 938169689Skan if (!TEST_BIT (reachable_from, v)) 939169689Skan { 940169689Skan SET_BIT (reachable_from, v); 941169689Skan SET_BIT (tmp, v); 942169689Skan change = 1; 943169689Skan } 944169689Skan } 945169689Skan } 946169689Skan } 947169689Skan 948169689Skan sbitmap_copy (reach_to, to); 949169689Skan sbitmap_copy (tmp, to); 950169689Skan 951169689Skan change = 1; 952169689Skan while (change) 953169689Skan { 954169689Skan change = 0; 955169689Skan sbitmap_copy (workset, tmp); 956169689Skan sbitmap_zero (tmp); 957169689Skan EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 958169689Skan { 959169689Skan ddg_edge_ptr e; 960169689Skan ddg_node_ptr u_node = &g->nodes[u]; 961169689Skan 962169689Skan for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) 963169689Skan { 964169689Skan ddg_node_ptr v_node = e->src; 965169689Skan int v = v_node->cuid; 966169689Skan 967169689Skan if (!TEST_BIT (reach_to, v)) 968169689Skan { 969169689Skan SET_BIT (reach_to, v); 970169689Skan SET_BIT (tmp, v); 971169689Skan change = 1; 972169689Skan } 973169689Skan } 974169689Skan } 975169689Skan } 976169689Skan 977169689Skan answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to); 978169689Skan sbitmap_free (workset); 979169689Skan sbitmap_free (reachable_from); 980169689Skan sbitmap_free (reach_to); 981169689Skan sbitmap_free (tmp); 982169689Skan return answer; 983169689Skan} 984169689Skan 985169689Skan 986169689Skan/* Updates the counts of U_NODE's successors (that belong to NODES) to be 987169689Skan at-least as large as the count of U_NODE plus the latency between them. 988169689Skan Sets a bit in TMP for each successor whose count was changed (increased). 989169689Skan Returns nonzero if any count was changed. */ 990169689Skanstatic int 991169689Skanupdate_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp) 992169689Skan{ 993169689Skan ddg_edge_ptr e; 994169689Skan int result = 0; 995169689Skan 996169689Skan for (e = u_node->out; e; e = e->next_out) 997169689Skan { 998169689Skan ddg_node_ptr v_node = e->dest; 999169689Skan int v = v_node->cuid; 1000169689Skan 1001169689Skan if (TEST_BIT (nodes, v) 1002169689Skan && (e->distance == 0) 1003169689Skan && (v_node->aux.count < u_node->aux.count + e->latency)) 1004169689Skan { 1005169689Skan v_node->aux.count = u_node->aux.count + e->latency; 1006169689Skan SET_BIT (tmp, v); 1007169689Skan result = 1; 1008169689Skan } 1009169689Skan } 1010169689Skan return result; 1011169689Skan} 1012169689Skan 1013169689Skan 1014169689Skan/* Find the length of a longest path from SRC to DEST in G, 1015169689Skan going only through NODES, and disregarding backarcs. */ 1016169689Skanint 1017169689Skanlongest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes) 1018169689Skan{ 1019169689Skan int i; 1020169689Skan unsigned int u = 0; 1021169689Skan int change = 1; 1022169689Skan int result; 1023169689Skan int num_nodes = g->num_nodes; 1024169689Skan sbitmap workset = sbitmap_alloc (num_nodes); 1025169689Skan sbitmap tmp = sbitmap_alloc (num_nodes); 1026169689Skan 1027169689Skan 1028169689Skan /* Data will hold the distance of the longest path found so far from 1029169689Skan src to each node. Initialize to -1 = less than minimum. */ 1030169689Skan for (i = 0; i < g->num_nodes; i++) 1031169689Skan g->nodes[i].aux.count = -1; 1032169689Skan g->nodes[src].aux.count = 0; 1033169689Skan 1034169689Skan sbitmap_zero (tmp); 1035169689Skan SET_BIT (tmp, src); 1036169689Skan 1037169689Skan while (change) 1038169689Skan { 1039169689Skan sbitmap_iterator sbi; 1040169689Skan 1041169689Skan change = 0; 1042169689Skan sbitmap_copy (workset, tmp); 1043169689Skan sbitmap_zero (tmp); 1044169689Skan EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) 1045169689Skan { 1046169689Skan ddg_node_ptr u_node = &g->nodes[u]; 1047169689Skan 1048169689Skan change |= update_dist_to_successors (u_node, nodes, tmp); 1049169689Skan } 1050169689Skan } 1051169689Skan result = g->nodes[dest].aux.count; 1052169689Skan sbitmap_free (workset); 1053169689Skan sbitmap_free (tmp); 1054169689Skan return result; 1055169689Skan} 1056