belive.c 8.35 KB
Newer Older
1
2
3
4
5
/**
 * Interblock liveness analysis.
 * @author Sebastian Hack
 * @date 6.12.2004
 */
Michael Beck's avatar
Michael Beck committed
6
7
8
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
9

Sebastian Hack's avatar
Sebastian Hack committed
10
#include "impl.h"
Sebastian Hack's avatar
Sebastian Hack committed
11
#include "iredges_t.h"
12
#include "irgwalk.h"
Sebastian Hack's avatar
Sebastian Hack committed
13
#include "irprintf_t.h"
14
15
16

#include "beutil.h"
#include "belive_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
17
18
19
#include "besched_t.h"

#define DBG_MODULE "firm.be.liveness"
20

Sebastian Hack's avatar
Sebastian Hack committed
21
22
FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *)
FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *)
23
FIRM_IMPL2(is_live_end, int, const ir_node *, const ir_node *)
Sebastian Hack's avatar
Sebastian Hack committed
24

25
/** The offset of the liveness information in a firm node. */
Sebastian Hack's avatar
Sebastian Hack committed
26
size_t live_irg_data_offset = 0;
27
28
29

void be_liveness_init(void)
{
Sebastian Hack's avatar
Sebastian Hack committed
30
  live_irg_data_offset = register_additional_graph_data(sizeof(irn_live_t));
31
32
}

Michael Beck's avatar
Michael Beck committed
33
34
35
/**
 * Mark a node as live-in in a block.
 */
36
37
static INLINE void mark_live_in(ir_node *block, const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
38
  _get_or_set_live(block, irn, live_state_in);
39
40
}

Michael Beck's avatar
Michael Beck committed
41
42
43
/**
 * Mark a node as live-out in a block.
 */
44
45
static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
46
  _get_or_set_live(block, irn, live_state_out | live_state_end);
47
48
}

Michael Beck's avatar
Michael Beck committed
49
50
51
/**
 * Mark a node as live-end in a block.
 */
52
53
static INLINE void mark_live_end(ir_node *block, const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
54
  _get_or_set_live(block, irn, live_state_end);
55
56
}

57
58
59
60
61
62
63
/**
 * Mark a node (value) live out at a certain block. Do this also
 * transitively, i.e. if the block is not the block of the value's
 * definition, all predecessors are also marked live.
 * @param def The node (value).
 * @param block The block to mark the value live out of.
 * @param visited A set were all visited blocks are recorded.
64
65
 * @param is_true_out Is the node real out there or only live at the end
 * of the block.
66
 */
67
static void live_end_at_block(ir_node *def, ir_node *block,
Sebastian Hack's avatar
Sebastian Hack committed
68
    pset *visited, int is_true_out)
69
{
Sebastian Hack's avatar
Sebastian Hack committed
70
71
72
  mark_live_end(block, def);
  if(is_true_out)
    mark_live_out(block, def);
73

Sebastian Hack's avatar
Sebastian Hack committed
74
  if(!pset_find_ptr(visited, block)) {
75

Sebastian Hack's avatar
Sebastian Hack committed
76
    pset_insert_ptr(visited, block);
77

Sebastian Hack's avatar
Sebastian Hack committed
78
79
80
81
82
83
    /*
     * If this block is not the definition block, we have to go up
     * further.
     */
    if(get_nodes_block(def) != block) {
      int i, n;
84

Sebastian Hack's avatar
Sebastian Hack committed
85
      mark_live_in(block, def);
86

Sebastian Hack's avatar
Sebastian Hack committed
87
      for(i = 0, n = get_irn_arity(block); i < n; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
88
        live_end_at_block(def, get_Block_cfgpred_block(block, i), visited, 1);
Sebastian Hack's avatar
Sebastian Hack committed
89
    }
90

Sebastian Hack's avatar
Sebastian Hack committed
91
  }
92
93
94
95
96
97
98
99
100
101
102
}

/**
 * Liveness analysis for a value.
 * This functions is meant to be called by a firm walker, to compute the
 * set of all blocks a value is live in.
 * @param irn The node (value).
 * @param env Ignored.
 */
static void liveness_for_node(ir_node *irn, void *env)
{
Sebastian Hack's avatar
Sebastian Hack committed
103
  const ir_edge_t *edge;
Sebastian Hack's avatar
Sebastian Hack committed
104
105
106
107
108
109
110
111
112
113
114
  ir_node *def_block;
  pset *visited;

  /* Don't compute liveness information for non-data nodes. */
  if(!is_data_node(irn))
    return;

  visited = pset_new_ptr(512);
  def_block = get_nodes_block(irn);

  /* Go over all uses of the value */
Sebastian Hack's avatar
Sebastian Hack committed
115
116
  foreach_out_edge(irn, edge) {
    ir_node *use = edge->src;
Sebastian Hack's avatar
Sebastian Hack committed
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
    ir_node *use_block;

    /*
     * If the usage is no data node, skip this use, since it does not
     * affect the liveness of the node.
     */
    if(!is_data_node(use))
      continue;

    /* Get the block where the usage is in. */
    use_block = get_nodes_block(use);

    /*
     * If the use is a phi function, determine the corresponding block
     * through which the value reaches the phi function and mark the
     * value as live out of that block.
     */
    if(is_Phi(use)) {
Sebastian Hack's avatar
Sebastian Hack committed
135
136
			ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos);
			live_end_at_block(irn, pred_block, visited, 0);
Sebastian Hack's avatar
Sebastian Hack committed
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
    }

    /*
     * Else, the value is live in at this block. Mark it and call live
     * out on the predecessors.
     */
    else if(def_block != use_block) {
      int i, n;

      mark_live_in(use_block, irn);

      for(i = 0, n = get_irn_arity(use_block); i < n; ++i) {
        ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
        live_end_at_block(irn, pred_block, visited, 1);
      }
    }
  }

  del_pset(visited);
156
157
}

Michael Beck's avatar
Michael Beck committed
158
159
160
/**
 * Compare two live entries.
 */
Sebastian Hack's avatar
Sebastian Hack committed
161
static int cmp_irn_live(const void *a, const void *b, size_t size)
162
{
Sebastian Hack's avatar
Sebastian Hack committed
163
164
  const irn_live_t *p = a;
  const irn_live_t *q = b;
165

Sebastian Hack's avatar
Sebastian Hack committed
166
  return !(p->block == q->block && p->irn == q->irn);
167
}
Sebastian Hack's avatar
Sebastian Hack committed
168

169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
static int (*old_dump_block_func)(ir_node *self, FILE *F, dump_reason_t reason) = NULL;

static int dump_block_func(ir_node *self, FILE *F, dump_reason_t reason)
{
	switch(reason) {
	case dump_node_opcode_txt:
		fprintf(F, get_irn_opname(self));
		break;
	case dump_node_mode_txt:
		fprintf(F, get_irn_modename(self));
		break;
	case dump_node_nodeattr_txt:
		break;
	case dump_node_info_txt:
		if(!get_irg_live_info(get_irn_irg(self))->live)
			return 0;
Sebastian Hack's avatar
Sebastian Hack committed
185
#if 0
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
		fprintf(F, "liveness information:\n");
		{
			irn_live_t *li;
			live_foreach(self, li) {
				ir_fprintf(F, "%+F", li->irn);
				if(live_is_in(li))
					fprintf(F, " in");
				if(live_is_end(li))
					fprintf(F, " end");
				if(live_is_out(li))
					fprintf(F, " out");

				fprintf(F, "\n");
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
201
#endif
202
203
204
205
206
	}

	return 0;
}

Michael Beck's avatar
Michael Beck committed
207
/* Compute the inter block liveness for a graph. */
Sebastian Hack's avatar
Sebastian Hack committed
208
209
void be_liveness(ir_graph *irg)
{
Sebastian Hack's avatar
Sebastian Hack committed
210
  irg_live_info_t *live_info = get_irg_live_info(irg);
Sebastian Hack's avatar
Sebastian Hack committed
211
212
213
  if(live_info->live)
    del_set(live_info->live);

Sebastian Hack's avatar
Sebastian Hack committed
214
215
  live_info->live = new_set(cmp_irn_live, 8192);
  irg_walk_graph(irg, liveness_for_node, NULL, NULL);
216
217
218

  old_dump_block_func     = op_Block->ops.dump_node;
  op_Block->ops.dump_node = dump_block_func;
Sebastian Hack's avatar
Sebastian Hack committed
219
}
Sebastian Hack's avatar
Sebastian Hack committed
220

Michael Beck's avatar
Michael Beck committed
221
222
223
/**
 * Pre-walker: dump liveness data to a file
 */
Sebastian Hack's avatar
Sebastian Hack committed
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
static void dump_liveness_walker(ir_node *bl, void *data)
{
	FILE *f = data;
	const irn_live_t *li;
	char buf[64];

	ir_fprintf(f, "%+F\n", bl);
	live_foreach(bl, li) {
		strcpy(buf, "");

		if(live_is_in(li))
			strcat(buf, "in ");

		if(live_is_end(li))
			strcat(buf, "end ");

		if(live_is_out(li))
			strcat(buf, "out ");

		ir_fprintf(f, "\t%+20F %s\n", li->irn, buf);
	}
}

Michael Beck's avatar
Michael Beck committed
247
/* Dump the liveness information for a graph. */
Sebastian Hack's avatar
Sebastian Hack committed
248
249
250
251
void be_liveness_dump(ir_graph *irg, FILE *f)
{
	irg_block_walk_graph(irg, dump_liveness_walker, NULL, f);
}
Sebastian Hack's avatar
Sebastian Hack committed
252

Michael Beck's avatar
Michael Beck committed
253
/* Dump the liveness information for a graph. */
Daniel Grund's avatar
Daniel Grund committed
254
255
256
257
258
259
260
261
262
263
264
void be_liveness_dumpto(ir_graph *irg, const char *cls_name)
{
	FILE *f;
	char buf[128];
	ir_snprintf(buf, sizeof(buf), "%F_%s-live.txt", irg, cls_name);
	if((f = fopen(buf, "wt")) != NULL) {
		be_liveness_dump(irg, f);
		fclose(f);
	}
}

Michael Beck's avatar
Michael Beck committed
265
266
267
268
/**
 * Walker: checks the every predecessors of a node dominate
 * the note.
 */
Sebastian Hack's avatar
Sebastian Hack committed
269
270
static void dom_check(ir_node *irn, void *data)
{
Daniel Grund's avatar
Daniel Grund committed
271
	if(!is_Block(irn) && irn != get_irg_end(get_irn_irg(irn))) {
Sebastian Hack's avatar
Sebastian Hack committed
272
273
274
275
276
277
278
279
280
281
282
		int i, n;
		ir_node *bl = get_nodes_block(irn);

		for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
			ir_node *op     = get_irn_n(irn, i);
			ir_node *def_bl = get_nodes_block(op);
			ir_node *use_bl = bl;

			if(is_Phi(irn))
				use_bl = get_Block_cfgpred_block(bl, i);

Daniel Grund's avatar
Daniel Grund committed
283
284
285
286
			if(!block_dominates(def_bl, use_bl)) {
				ir_fprintf(stderr, "%+F in %+F must dominate %+F for user %+F\n", op, def_bl, use_bl, irn);
				assert(0);
			}
Sebastian Hack's avatar
Sebastian Hack committed
287
288
289
290
		}
	}
}

Michael Beck's avatar
Michael Beck committed
291
/* Check, if the SSA dominance property is fulfilled. */
Sebastian Hack's avatar
Sebastian Hack committed
292
293
294
295
void be_check_dominance(ir_graph *irg)
{
	irg_walk_graph(irg, dom_check, NULL, NULL);
}
Sebastian Hack's avatar
Sebastian Hack committed
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353

pset *be_liveness_transfer(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_node *irn, pset *live)
{
	firm_dbg_module_t *dbg = firm_dbg_register(DBG_MODULE);
	int i, n;
	ir_node *x;

	DBG((dbg, LEVEL_1, "%+F\n", irn));
	for(x = pset_first(live); x; x = pset_next(live))
		DBG((dbg, LEVEL_1, "\tlive: %+F\n", x));

	if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
		pset_remove_ptr(live, irn);

	for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
		ir_node *op = get_irn_n(irn, i);

		if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
			pset_insert_ptr(live, op);
	}

	return live;
}

pset *be_liveness_end_of_block(const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *bl, pset *live)
{
	irn_live_t *li;

	live_foreach(bl, li) {
		ir_node *irn = (ir_node *) li->irn;
		if(live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
			pset_insert_ptr(live, irn);
	}

	return live;
}

pset *be_liveness_nodes_live_at(const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live)
{
	firm_dbg_module_t *dbg = firm_dbg_register(DBG_MODULE);
	const ir_node *bl      = is_Block(pos) ? pos : get_nodes_block(pos);
	ir_node *irn;

	be_liveness_end_of_block(arch_env, cls, bl, live);

	sched_foreach_reverse(bl, irn) {
		/*
		 * If we encounter the node we want to insert the Perm after,
		 * exit immediately, so that this node is still live
		 */
		if(irn == pos)
			return live;

		be_liveness_transfer(arch_env, cls, irn, live);
	}

	return live;
}