1169689Skan/* DDG - Data Dependence Graph - interface. 2169689Skan Copyright (C) 2004 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#ifndef GCC_DDG_H 24169689Skan#define GCC_DDG_H 25169689Skan 26169689Skan/* For sbitmap. */ 27169689Skan#include "sbitmap.h" 28169689Skan/* For basic_block. */ 29169689Skan#include "basic-block.h" 30169689Skan/* For struct df. */ 31169689Skan#include "df.h" 32169689Skan 33169689Skantypedef struct ddg_node *ddg_node_ptr; 34169689Skantypedef struct ddg_edge *ddg_edge_ptr; 35169689Skantypedef struct ddg *ddg_ptr; 36169689Skantypedef struct ddg_scc *ddg_scc_ptr; 37169689Skantypedef struct ddg_all_sccs *ddg_all_sccs_ptr; 38169689Skan 39169689Skantypedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type; 40169689Skantypedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP} 41169689Skan dep_data_type; 42169689Skan 43169689Skan/* The following two macros enables direct access to the successors and 44169689Skan predecessors bitmaps held in each ddg_node. Do not make changes to 45169689Skan these bitmaps, unless you want to change the DDG. */ 46169689Skan#define NODE_SUCCESSORS(x) ((x)->successors) 47169689Skan#define NODE_PREDECESSORS(x) ((x)->predecessors) 48169689Skan 49169689Skan/* A structure that represents a node in the DDG. */ 50169689Skanstruct ddg_node 51169689Skan{ 52169689Skan /* Each node has a unique CUID index. These indices increase monotonically 53169689Skan (according to the order of the corresponding INSN in the BB), starting 54169689Skan from 0 with no gaps. */ 55169689Skan int cuid; 56169689Skan 57169689Skan /* The insn represented by the node. */ 58169689Skan rtx insn; 59169689Skan 60169689Skan /* A note preceding INSN (or INSN itself), such that all insns linked 61169689Skan from FIRST_NOTE until INSN (inclusive of both) are moved together 62169689Skan when reordering the insns. This takes care of notes that should 63169689Skan continue to precede INSN. */ 64169689Skan rtx first_note; 65169689Skan 66169689Skan /* Incoming and outgoing dependency edges. */ 67169689Skan ddg_edge_ptr in; 68169689Skan ddg_edge_ptr out; 69169689Skan 70169689Skan /* Each bit corresponds to a ddg_node according to its cuid, and is 71169689Skan set iff the node is a successor/predecessor of "this" node. */ 72169689Skan sbitmap successors; 73169689Skan sbitmap predecessors; 74169689Skan 75169689Skan /* For general use by algorithms manipulating the ddg. */ 76169689Skan union { 77169689Skan int count; 78169689Skan void *info; 79169689Skan } aux; 80169689Skan}; 81169689Skan 82169689Skan/* A structure that represents an edge in the DDG. */ 83169689Skanstruct ddg_edge 84169689Skan{ 85169689Skan /* The source and destination nodes of the dependency edge. */ 86169689Skan ddg_node_ptr src; 87169689Skan ddg_node_ptr dest; 88169689Skan 89169689Skan /* TRUE, OUTPUT or ANTI dependency. */ 90169689Skan dep_type type; 91169689Skan 92169689Skan /* REG or MEM dependency. */ 93169689Skan dep_data_type data_type; 94169689Skan 95169689Skan /* Latency of the dependency. */ 96169689Skan int latency; 97169689Skan 98169689Skan /* The distance: number of loop iterations the dependency crosses. */ 99169689Skan int distance; 100169689Skan 101169689Skan /* The following two fields are used to form a linked list of the in/out 102169689Skan going edges to/from each node. */ 103169689Skan ddg_edge_ptr next_in; 104169689Skan ddg_edge_ptr next_out; 105169689Skan 106169689Skan /* For general use by algorithms manipulating the ddg. */ 107169689Skan union { 108169689Skan int count; 109169689Skan void *info; 110169689Skan } aux; 111169689Skan}; 112169689Skan 113169689Skan/* This structure holds the Data Dependence Graph for a basic block. */ 114169689Skanstruct ddg 115169689Skan{ 116169689Skan /* The basic block for which this DDG is built. */ 117169689Skan basic_block bb; 118169689Skan 119169689Skan /* Number of instructions in the basic block. */ 120169689Skan int num_nodes; 121169689Skan 122169689Skan /* Number of load/store instructions in the BB - statistics. */ 123169689Skan int num_loads; 124169689Skan int num_stores; 125169689Skan 126169689Skan /* This array holds the nodes in the graph; it is indexed by the node 127169689Skan cuid, which follows the order of the instructions in the BB. */ 128169689Skan ddg_node_ptr nodes; 129169689Skan 130169689Skan /* The branch closing the loop. */ 131169689Skan ddg_node_ptr closing_branch; 132169689Skan 133169689Skan /* Build dependence edges for closing_branch, when set. In certain cases, 134169689Skan the closing branch can be dealt with separately from the insns of the 135169689Skan loop, and then no such deps are needed. */ 136169689Skan int closing_branch_deps; 137169689Skan 138169689Skan /* Array and number of backarcs (edges with distance > 0) in the DDG. */ 139169689Skan ddg_edge_ptr *backarcs; 140169689Skan int num_backarcs; 141169689Skan}; 142169689Skan 143169689Skan 144169689Skan/* Holds information on an SCC (Strongly Connected Component) of the DDG. */ 145169689Skanstruct ddg_scc 146169689Skan{ 147169689Skan /* A bitmap that represents the nodes of the DDG that are in the SCC. */ 148169689Skan sbitmap nodes; 149169689Skan 150169689Skan /* Array and number of backarcs (edges with distance > 0) in the SCC. */ 151169689Skan ddg_edge_ptr *backarcs; 152169689Skan int num_backarcs; 153169689Skan 154169689Skan /* The maximum of (total_latency/total_distance) over all cycles in SCC. */ 155169689Skan int recurrence_length; 156169689Skan}; 157169689Skan 158169689Skan/* This structure holds the SCCs of the DDG. */ 159169689Skanstruct ddg_all_sccs 160169689Skan{ 161169689Skan /* Array that holds the SCCs in the DDG, and their number. */ 162169689Skan ddg_scc_ptr *sccs; 163169689Skan int num_sccs; 164169689Skan 165169689Skan ddg_ptr ddg; 166169689Skan}; 167169689Skan 168169689Skan 169169689Skanddg_ptr create_ddg (basic_block, struct df *, int closing_branch_deps); 170169689Skanvoid free_ddg (ddg_ptr); 171169689Skan 172169689Skanvoid print_ddg (FILE *, ddg_ptr); 173169689Skanvoid vcg_print_ddg (FILE *, ddg_ptr); 174169689Skanvoid print_ddg_edge (FILE *, ddg_edge_ptr); 175169689Skan 176169689Skanddg_node_ptr get_node_of_insn (ddg_ptr, rtx); 177169689Skan 178169689Skanvoid find_successors (sbitmap result, ddg_ptr, sbitmap); 179169689Skanvoid find_predecessors (sbitmap result, ddg_ptr, sbitmap); 180169689Skan 181169689Skanddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr); 182169689Skanvoid free_ddg_all_sccs (ddg_all_sccs_ptr); 183169689Skan 184169689Skanint find_nodes_on_paths (sbitmap result, ddg_ptr, sbitmap from, sbitmap to); 185169689Skanint longest_simple_path (ddg_ptr, int from, int to, sbitmap via); 186169689Skan 187169689Skan#endif /* GCC_DDG_H */ 188