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