1 /*
2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
10 *
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
14 *
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE.
18 */
19
20 /**
21 * @file
22 * @brief Everlasting outs -- private header.
23 * @author Sebastian Hack, Andreas Schoesser
24 * @date 15.01.2005
25 */
26 #ifndef FIRM_IR_EDGES_T_H
27 #define FIRM_IR_EDGES_T_H
28
29 #include "debug.h"
30
31 #include "set.h"
32 #include "list.h"
33
34 #include "irnode_t.h"
35 #include "irgraph_t.h"
36
37 #include "iredgekinds.h"
38 #include "iredges.h"
39
40 #define DBG_EDGES "firm.ir.edges"
41
42 /**
43 * An edge.
44 */
45 struct ir_edge_t {
46 ir_node *src; /**< The source node of the edge. */
47 int pos; /**< The position of the edge at @p src. */
48 unsigned invalid : 1; /**< edges that are removed are marked invalid. */
49 unsigned present : 1; /**< Used by the verifier. Don't rely on its content. */
50 unsigned kind : 4; /**< The kind of the edge. */
51 struct list_head list; /**< The list head to queue all out edges at a node. */
52 };
53
54 /** Accessor for private irn info. */
get_irn_edge_info(ir_node * node,ir_edge_kind_t kind)55 static inline irn_edge_info_t *get_irn_edge_info(ir_node *node,
56 ir_edge_kind_t kind)
57 {
58 return &node->edge_info[kind];
59 }
60
get_irn_edge_info_const(const ir_node * node,ir_edge_kind_t kind)61 static inline const irn_edge_info_t *get_irn_edge_info_const(
62 const ir_node *node, ir_edge_kind_t kind)
63 {
64 return &node->edge_info[kind];
65 }
66
67 /** Accessor for private irg info. */
get_irg_edge_info(ir_graph * irg,ir_edge_kind_t kind)68 static inline irg_edge_info_t *get_irg_edge_info(ir_graph *irg,
69 ir_edge_kind_t kind)
70 {
71 return &irg->edge_info[kind];
72 }
73
74 /** Accessor for private irg info. */
get_irg_edge_info_const(const ir_graph * irg,ir_edge_kind_t kind)75 static inline const irg_edge_info_t *get_irg_edge_info_const(
76 const ir_graph *irg, ir_edge_kind_t kind)
77 {
78 return &irg->edge_info[kind];
79 }
80
81 /**
82 * Get the first edge pointing to some node.
83 * @note There is no order on out edges. First in this context only
84 * means, that you get some starting point into the list of edges.
85 * @param irn The node.
86 * @return The first out edge that points to this node.
87 */
get_irn_out_edge_first_kind_(const ir_node * irn,ir_edge_kind_t kind)88 static inline const ir_edge_t *get_irn_out_edge_first_kind_(const ir_node *irn, ir_edge_kind_t kind)
89 {
90 const struct list_head *head;
91 assert(edges_activated_kind(get_irn_irg(irn), kind));
92 head = &get_irn_edge_info_const(irn, kind)->outs_head;
93 return list_empty(head) ? NULL : list_entry(head->next, ir_edge_t, list);
94 }
95
96 /**
97 * Get the next edge in the out list of some node.
98 * @param irn The node.
99 * @param last The last out edge you have seen.
100 * @return The next out edge in @p irn 's out list after @p last.
101 */
get_irn_out_edge_next_(const ir_node * irn,const ir_edge_t * last)102 static inline const ir_edge_t *get_irn_out_edge_next_(const ir_node *irn, const ir_edge_t *last)
103 {
104 struct list_head *next = last->list.next;
105 const struct list_head *head
106 = &get_irn_edge_info_const(irn, (ir_edge_kind_t)last->kind)->outs_head;
107 return next == head ? NULL : list_entry(next, ir_edge_t, list);
108 }
109
110 /**
111 * Get the number of edges pointing to a node.
112 * @param irn The node.
113 * @return The number of edges pointing to this node.
114 */
get_irn_n_edges_kind_(const ir_node * irn,ir_edge_kind_t kind)115 static inline int get_irn_n_edges_kind_(const ir_node *irn, ir_edge_kind_t kind)
116 {
117 return get_irn_edge_info_const(irn, kind)->out_count;
118 }
119
edges_activated_kind_(const ir_graph * irg,ir_edge_kind_t kind)120 static inline int edges_activated_kind_(const ir_graph *irg, ir_edge_kind_t kind)
121 {
122 return get_irg_edge_info_const(irg, kind)->activated;
123 }
124
125 /**
126 * Assure, that the edges information is present for a certain graph.
127 * @param irg The graph.
128 */
edges_assure_kind_(ir_graph * irg,ir_edge_kind_t kind)129 static inline void edges_assure_kind_(ir_graph *irg, ir_edge_kind_t kind)
130 {
131 if(!edges_activated_kind_(irg, kind))
132 edges_activate_kind(irg, kind);
133 }
134
135 void edges_init_graph_kind(ir_graph *irg, ir_edge_kind_t kind);
136
137 void edges_node_deleted(ir_node *irn);
138
139 /**
140 * A node might be revivaled by CSE.
141 */
142 void edges_node_revival(ir_node *node);
143
144 void edges_invalidate_kind(ir_node *irn, ir_edge_kind_t kind);
145
146 /**
147 * Register additional memory in an edge.
148 * This must be called before Firm is initialized.
149 * @param n Number of bytes you need.
150 * @return A number you have to keep and to pass
151 * edges_get_private_data()
152 * to get a pointer to your data.
153 */
154 size_t edges_register_private_data(size_t n);
155
156 /**
157 * Get a pointer to the private data you registered.
158 * @param edge The edge.
159 * @param ofs The number, you obtained with
160 * edges_register_private_data().
161 * @return A pointer to the private data.
162 */
get_edge_private_data_(const ir_edge_t * edge,int ofs)163 static inline void *get_edge_private_data_(const ir_edge_t *edge, int ofs)
164 {
165 return (void *) ((char *) edge + sizeof(edge[0]) + ofs);
166 }
167
get_edge_src_irn_(const ir_edge_t * edge)168 static inline ir_node *get_edge_src_irn_(const ir_edge_t *edge)
169 {
170 return edge->src;
171 }
172
get_edge_src_pos_(const ir_edge_t * edge)173 static inline int get_edge_src_pos_(const ir_edge_t *edge)
174 {
175 return edge->pos;
176 }
177
178 /**
179 * Returns the edge object of an outgoing edge at a node.
180 * @param irn The node at which the edge originates.
181 * @param pos The position of the edge.
182 * @param kind The kind of the edge.
183 * @return The corresponding edge object or NULL,
184 * if no such edge exists.
185 */
186 FIRM_API const ir_edge_t *get_irn_edge_kind(const ir_node *irn,
187 int pos, ir_edge_kind_t kind);
188
189 /**
190 * Initialize the out edges.
191 * This must be called before firm is initialized.
192 */
193 extern void init_edges(void);
194
195 void edges_invalidate_all(ir_node *irn);
196
197 /**
198 * Helper function to dump the edge set of a graph,
199 * unused in normal code.
200 */
201 void edges_dump_kind(ir_graph *irg, ir_edge_kind_t kind);
202
203 /**
204 * Notify normal and block edges.
205 */
206 void edges_notify_edge(ir_node *src, int pos, ir_node *tgt,
207 ir_node *old_tgt, ir_graph *irg);
208
209 #define get_irn_n_edges_kind(irn, kind) get_irn_n_edges_kind_(irn, kind)
210 #define get_edge_src_irn(edge) get_edge_src_irn_(edge)
211 #define get_edge_src_pos(edge) get_edge_src_pos_(edge)
212 #define get_edge_private_data(edge, ofs) get_edge_private_data_(edge,ofs)
213 #define get_irn_out_edge_next(irn, last) get_irn_out_edge_next_(irn, last)
214
215 #ifndef get_irn_n_edges
216 #define get_irn_n_edges(irn) get_irn_n_edges_kind_(irn, EDGE_KIND_NORMAL)
217 #endif
218
219 #ifndef get_irn_out_edge_first
220 #define get_irn_out_edge_first(irn) get_irn_out_edge_first_kind_(irn, EDGE_KIND_NORMAL)
221 #endif
222
223 #ifndef get_block_succ_first
224 #define get_block_succ_first(irn) get_irn_out_edge_first_kind_(irn, EDGE_KIND_BLOCK)
225 #endif
226
227 #ifndef get_block_succ_next
228 #define get_block_succ_next(irn, last) get_irn_out_edge_next_(irn, last)
229 #endif
230
231 #endif
232