]>
Commit | Line | Data |
---|---|---|
d397e8c6 | 1 | /* DDG - Data Dependence Graph - interface. |
b5b8b0ac | 2 | Copyright (C) 2004, 2005, 2006, 2007, 2008 |
d397e8c6 MH |
3 | Free Software Foundation, Inc. |
4 | Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify it under | |
9 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 10 | Software Foundation; either version 3, or (at your option) any later |
d397e8c6 MH |
11 | version. |
12 | ||
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
d397e8c6 MH |
21 | |
22 | #ifndef GCC_DDG_H | |
23 | #define GCC_DDG_H | |
24 | ||
59587b18 JQ |
25 | /* For sbitmap. */ |
26 | #include "sbitmap.h" | |
27 | /* For basic_block. */ | |
28 | #include "basic-block.h" | |
59587b18 | 29 | #include "df.h" |
b8698a0f | 30 | |
d397e8c6 MH |
31 | typedef struct ddg_node *ddg_node_ptr; |
32 | typedef struct ddg_edge *ddg_edge_ptr; | |
33 | typedef struct ddg *ddg_ptr; | |
34 | typedef struct ddg_scc *ddg_scc_ptr; | |
35 | typedef struct ddg_all_sccs *ddg_all_sccs_ptr; | |
36 | ||
37 | typedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type; | |
38 | typedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP} | |
39 | dep_data_type; | |
40 | ||
41 | /* The following two macros enables direct access to the successors and | |
42 | predecessors bitmaps held in each ddg_node. Do not make changes to | |
43 | these bitmaps, unless you want to change the DDG. */ | |
44 | #define NODE_SUCCESSORS(x) ((x)->successors) | |
45 | #define NODE_PREDECESSORS(x) ((x)->predecessors) | |
46 | ||
47 | /* A structure that represents a node in the DDG. */ | |
48 | struct ddg_node | |
49 | { | |
50 | /* Each node has a unique CUID index. These indices increase monotonically | |
51 | (according to the order of the corresponding INSN in the BB), starting | |
52 | from 0 with no gaps. */ | |
53 | int cuid; | |
54 | ||
55 | /* The insn represented by the node. */ | |
56 | rtx insn; | |
57 | ||
1ea7e6ad | 58 | /* A note preceding INSN (or INSN itself), such that all insns linked |
d397e8c6 MH |
59 | from FIRST_NOTE until INSN (inclusive of both) are moved together |
60 | when reordering the insns. This takes care of notes that should | |
1ea7e6ad | 61 | continue to precede INSN. */ |
d397e8c6 MH |
62 | rtx first_note; |
63 | ||
64 | /* Incoming and outgoing dependency edges. */ | |
65 | ddg_edge_ptr in; | |
66 | ddg_edge_ptr out; | |
67 | ||
68 | /* Each bit corresponds to a ddg_node according to its cuid, and is | |
69 | set iff the node is a successor/predecessor of "this" node. */ | |
70 | sbitmap successors; | |
71 | sbitmap predecessors; | |
72 | ||
73 | /* For general use by algorithms manipulating the ddg. */ | |
74 | union { | |
75 | int count; | |
76 | void *info; | |
77 | } aux; | |
78 | }; | |
79 | ||
80 | /* A structure that represents an edge in the DDG. */ | |
81 | struct ddg_edge | |
82 | { | |
83 | /* The source and destination nodes of the dependency edge. */ | |
84 | ddg_node_ptr src; | |
85 | ddg_node_ptr dest; | |
86 | ||
87 | /* TRUE, OUTPUT or ANTI dependency. */ | |
88 | dep_type type; | |
89 | ||
90 | /* REG or MEM dependency. */ | |
91 | dep_data_type data_type; | |
92 | ||
61ada8ae | 93 | /* Latency of the dependency. */ |
d397e8c6 MH |
94 | int latency; |
95 | ||
96 | /* The distance: number of loop iterations the dependency crosses. */ | |
97 | int distance; | |
98 | ||
99 | /* The following two fields are used to form a linked list of the in/out | |
100 | going edges to/from each node. */ | |
101 | ddg_edge_ptr next_in; | |
102 | ddg_edge_ptr next_out; | |
103 | ||
104 | /* For general use by algorithms manipulating the ddg. */ | |
105 | union { | |
106 | int count; | |
107 | void *info; | |
108 | } aux; | |
109 | }; | |
110 | ||
111 | /* This structure holds the Data Dependence Graph for a basic block. */ | |
112 | struct ddg | |
113 | { | |
114 | /* The basic block for which this DDG is built. */ | |
115 | basic_block bb; | |
116 | ||
117 | /* Number of instructions in the basic block. */ | |
118 | int num_nodes; | |
119 | ||
120 | /* Number of load/store instructions in the BB - statistics. */ | |
121 | int num_loads; | |
122 | int num_stores; | |
123 | ||
b5b8b0ac AO |
124 | /* Number of debug instructions in the BB. */ |
125 | int num_debug; | |
126 | ||
d397e8c6 MH |
127 | /* This array holds the nodes in the graph; it is indexed by the node |
128 | cuid, which follows the order of the instructions in the BB. */ | |
129 | ddg_node_ptr nodes; | |
130 | ||
131 | /* The branch closing the loop. */ | |
132 | ddg_node_ptr closing_branch; | |
133 | ||
134 | /* Build dependence edges for closing_branch, when set. In certain cases, | |
135 | the closing branch can be dealt with separately from the insns of the | |
136 | loop, and then no such deps are needed. */ | |
137 | int closing_branch_deps; | |
138 | ||
139 | /* Array and number of backarcs (edges with distance > 0) in the DDG. */ | |
d397e8c6 | 140 | int num_backarcs; |
b5b8b0ac | 141 | ddg_edge_ptr *backarcs; |
d397e8c6 MH |
142 | }; |
143 | ||
144 | \f | |
145 | /* Holds information on an SCC (Strongly Connected Component) of the DDG. */ | |
146 | struct ddg_scc | |
147 | { | |
148 | /* A bitmap that represents the nodes of the DDG that are in the SCC. */ | |
149 | sbitmap nodes; | |
150 | ||
151 | /* Array and number of backarcs (edges with distance > 0) in the SCC. */ | |
152 | ddg_edge_ptr *backarcs; | |
153 | int num_backarcs; | |
154 | ||
155 | /* The maximum of (total_latency/total_distance) over all cycles in SCC. */ | |
156 | int recurrence_length; | |
157 | }; | |
158 | ||
159 | /* This structure holds the SCCs of the DDG. */ | |
160 | struct ddg_all_sccs | |
161 | { | |
162 | /* Array that holds the SCCs in the DDG, and their number. */ | |
163 | ddg_scc_ptr *sccs; | |
164 | int num_sccs; | |
165 | ||
166 | ddg_ptr ddg; | |
167 | }; | |
168 | ||
169 | \f | |
6fb5fa3c | 170 | ddg_ptr create_ddg (basic_block, int closing_branch_deps); |
d397e8c6 MH |
171 | void free_ddg (ddg_ptr); |
172 | ||
173 | void print_ddg (FILE *, ddg_ptr); | |
174 | void vcg_print_ddg (FILE *, ddg_ptr); | |
175 | void print_ddg_edge (FILE *, ddg_edge_ptr); | |
8cec1624 | 176 | void print_sccs (FILE *, ddg_all_sccs_ptr, ddg_ptr); |
d397e8c6 MH |
177 | |
178 | ddg_node_ptr get_node_of_insn (ddg_ptr, rtx); | |
179 | ||
180 | void find_successors (sbitmap result, ddg_ptr, sbitmap); | |
181 | void find_predecessors (sbitmap result, ddg_ptr, sbitmap); | |
182 | ||
183 | ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr); | |
184 | void free_ddg_all_sccs (ddg_all_sccs_ptr); | |
185 | ||
186 | int find_nodes_on_paths (sbitmap result, ddg_ptr, sbitmap from, sbitmap to); | |
187 | int longest_simple_path (ddg_ptr, int from, int to, sbitmap via); | |
188 | ||
189 | #endif /* GCC_DDG_H */ |