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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
/*
* This file is part of libFirm.
* Copyright (C) 2012 University of Karlsruhe.
*/
/**
* @file
* @brief Interblock liveness analysis.
* @author Sebastian Hack
* @date 06.12.2004
*/
#ifndef FIRM_BE_BELIVE_H
#define FIRM_BE_BELIVE_H
#include "be_types.h"
#include "irnodeset.h"
#include "irnodehashmap.h"
#include "irlivechk.h"
#include "bearch.h"
typedef enum be_lv_state_t {
be_lv_state_none = 0,
be_lv_state_in = 1u << 0,
be_lv_state_end = 1u << 1,
be_lv_state_out = 1u << 2,
} be_lv_state_t;
ENUM_BITSET(be_lv_state_t)
/**
* Compute the inter block liveness for a graph.
* @param irg The graph.
*/
be_lv_t *be_liveness_new(ir_graph *irg);
/**
* Free the liveness information.
*/
void be_liveness_free(be_lv_t *lv);
/**
* (Re)compute the liveness information if necessary.
*/
void be_liveness_compute_sets(be_lv_t *lv);
void be_liveness_compute_chk(be_lv_t *lv);
/**
* Invalidate the liveness information.
* You must call this if you modify the program and do not
* update the liveness with the be_liveness_{update,remove,introduce}
* functions.
* @note If changed the control flow then you must also call
* be_liveness_invalidate_chk()
*/
void be_liveness_invalidate_sets(be_lv_t *lv);
void be_liveness_invalidate_chk(be_lv_t *lv);
/**
* Update the liveness information for a single node.
* It is irrelevant if there is liveness information present for the node.
* The liveness information for the node is firstly deleted and then recomputed.
* If the node is fresh and never recorded inf the liveness information before,
* it is more efficient to call be_liveness_introduce().
*/
void be_liveness_update(be_lv_t *lv, ir_node *irn);
/**
* Remove a node from the liveness information.
*/
void be_liveness_remove(be_lv_t *lv, const ir_node *irn);
/**
* Introduce a new node to the liveness information.
* The new irn is not deleted from any block's liveness information, so it must be fresh!
* @param lv The liveness info.
* @param irn The node.
*/
void be_liveness_introduce(be_lv_t *lv, ir_node *irn);
/**
* The liveness transfer function.
* Updates a live set over a single step from a given node to its predecessor.
* Everything defined at the node is removed from the set, the uses of the node get inserted.
* @param cls The register class to consider.
* @param irn The node at which liveness should be computed.
* @param live The set of nodes live before @p irn. This set gets modified by updating it to
* the nodes live after irn.
* @return live.
*/
void be_liveness_transfer(const arch_register_class_t *cls, ir_node *node,
ir_nodeset_t *nodeset);
/**
* Put all node live at the end of a block into a set.
* @param cls The register class to consider.
* @param bl The block.
* @param live The set to put them into.
* @return live.
*/
void be_liveness_end_of_block(const be_lv_t *lv,
const arch_register_class_t *cls,
const ir_node *bl, ir_nodeset_t *nodeset);
/**
* Check if value @p value is live after instruction @p after.
*/
bool be_value_live_after(const ir_node *value, const ir_node *after);
/**
* Check, if two values interfere.
* @param lv Liveness information
* @param a The first value.
* @param b The second value.
* @return true, if a and b interfere, false if not.
*/
bool be_values_interfere(const ir_node *a, const ir_node *b);
/**
* Similar to by_values_interfere() but with special handling for Sync nodes.
*/
bool be_memory_values_interfere(const ir_node *a, const ir_node *b);
/**
* Compute a set of nodes which are live just before the given node.
* @param cls The register class to consider.
* @param pos The node.
* @param live The set to put them into.
*/
void be_liveness_nodes_live_before(be_lv_t const *lv,
arch_register_class_t const *cls,
ir_node const *pos, ir_nodeset_t *live);
struct be_lv_t {
ir_nodehashmap_t map;
struct obstack obst;
bool sets_valid;
ir_graph *irg;
lv_chk_t *lvc;
};
typedef struct be_lv_info_node_t be_lv_info_node_t;
struct be_lv_info_node_t {
ir_node *node;
be_lv_state_t flags;
};
struct be_lv_info_t {
unsigned n_members;
unsigned n_size;
be_lv_info_node_t nodes[];
};
be_lv_info_node_t *be_lv_get(const be_lv_t *li, const ir_node *block,
const ir_node *irn);
static inline be_lv_state_t be_get_live_state(be_lv_t const *const li, ir_node const *const block, ir_node const *const irn)
{
if (li->sets_valid) {
be_lv_info_node_t *info = be_lv_get(li, block, irn);
return info ? info->flags : be_lv_state_none;
} else {
return lv_chk_bl_xxx(li->lvc, block, irn);
}
}
/**
* Check, if a node is live in at a block.
* @param block The block.
* @param irn The node to check for.
* @return true, if @p irn is live at the entrance of @p block
*/
static inline bool be_is_live_in(const be_lv_t *li, const ir_node *block,
const ir_node *node)
{
return be_get_live_state(li, block, node) & be_lv_state_in;
}
/**
* Check, if a node is live out at a block.
* @param block The block.
* @param irn The node to check for.
* @return true, if @p irn is live at the exit of @p block
*/
static inline bool be_is_live_out(const be_lv_t *li, const ir_node *block,
const ir_node *node)
{
return be_get_live_state(li, block, node) & be_lv_state_out;
}
/**
* Check, if a node is live at the end of a block.
* @param block The block.
* @param irn The node to check for.
* @return true, if @p irn is live at the end of the block
*/
static inline bool be_is_live_end(const be_lv_t *li, const ir_node *block,
const ir_node *node)
{
return be_get_live_state(li, block, node) & be_lv_state_end;
}
typedef struct lv_iterator_t
{
be_lv_info_t *info;
size_t i;
} lv_iterator_t;
static inline lv_iterator_t be_lv_iteration_begin(const be_lv_t *lv,
const ir_node *block)
{
assert(lv->sets_valid);
lv_iterator_t res;
res.info = ir_nodehashmap_get(be_lv_info_t, &lv->map, block);
res.i = res.info ? res.info->n_members : 0;
return res;
}
static inline ir_node *be_lv_iteration_next(lv_iterator_t *iterator,
be_lv_state_t flags)
{
while (iterator->i != 0) {
be_lv_info_node_t const *const node = &iterator->info->nodes[--iterator->i];
assert(get_irn_mode(node->node) != mode_T);
if (node->flags & flags)
return node->node;
}
return NULL;
}
static inline ir_node *be_lv_iteration_cls_next(lv_iterator_t *iterator,
be_lv_state_t flags,
const arch_register_class_t *cls)
{
while (iterator->i != 0) {
be_lv_info_node_t const *const lnode = &iterator->info->nodes[--iterator->i];
assert(get_irn_mode(lnode->node) != mode_T);
if (!(lnode->flags & flags))
continue;
ir_node *const node = lnode->node;
if (!arch_irn_consider_in_reg_alloc(cls, node))
continue;
return node;
}
return NULL;
}
#define be_lv_foreach(lv, block, flags, node) \
for (bool once = true; once;) \
for (lv_iterator_t iter = be_lv_iteration_begin((lv), (block)); once; once = false) \
for (ir_node *node; (node = be_lv_iteration_next(&iter, (flags))) != NULL;)
#define be_lv_foreach_cls(lv, block, flags, cls, node) \
for (bool once = true; once;) \
for (lv_iterator_t iter = be_lv_iteration_begin((lv), (block)); once; once = false) \
for (ir_node *node; (node = be_lv_iteration_cls_next(&iter, (flags), (cls))) != NULL;)
#endif
|
