belive.c 17.8 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"
Sebastian Hack's avatar
Sebastian Hack committed
14
#include "irbitset.h"
15
#include "irdump_t.h"
16
17
18

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

Sebastian Hack's avatar
Sebastian Hack committed
21
#define DBG_MODULE              "firm.be.liveness"
22

Sebastian Hack's avatar
Sebastian Hack committed
23
24
25
#define LV_STD_SIZE             128
#define LV_USE_BINARY_SEARCH
#undef  LV_INTESIVE_CHECKS
Sebastian Hack's avatar
Sebastian Hack committed
26

27
28
static INLINE int is_liveness_node(const ir_node *irn)
{
29
30
31
32
33
34
35
36
37
	switch(get_irn_opcode(irn)) {
	case iro_Block:
	case iro_Bad:
	case iro_End:
		return 0;
	default:;
	}

	return 1;
38
39
}

Sebastian Hack's avatar
Sebastian Hack committed
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
int (be_lv_next_irn)(const struct _be_lv_t *lv, const ir_node *bl, unsigned flags, int i)
{
	return _be_lv_next_irn(lv, bl, flags, i);
}

const ir_node * (be_lv_get_irn)(const struct _be_lv_t *lv, const ir_node *bl, int i)
{
	return _be_lv_get_irn(lv, bl, i);
}

int (be_is_live_in)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
{
	return _be_is_live_xxx(lv, block, irn, be_lv_state_in);
}

int (be_is_live_out)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
{
	return _be_is_live_xxx(lv, block, irn, be_lv_state_out);
}

int (be_is_live_end)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
{
	return _be_is_live_xxx(lv, block, irn, be_lv_state_end);
}


#ifdef LV_USE_BINARY_SEARCH
static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned idx)
{
	struct _be_lv_info_t *payload = arr + 1;

	unsigned n   = arr[0].u.head.n_members;
	unsigned res = 0;
	int lo       = 0;
	int hi       = n;

	if(n == 0)
		return 0;

#if 0
	if(idx < payload[0].u.node.idx)
		return 0;

	if(idx > payload[n - 1].u.node.idx)
		return n - 1;
#endif

	/* start a binary search for the requested node. */
	while(lo < hi) {
		int md          = lo + ((hi - lo) >> 1);
		unsigned md_idx = payload[md].u.node.idx;

		if(idx > md_idx)
			lo = md + 1;
		else if(idx < md_idx)
			hi = md;
		else {
			res = md;
			assert(payload[res].u.node.idx == idx);
			break;
		}

		res = lo;
	}

#ifdef LV_INTESIVE_CHECKS
	{
		unsigned i;
		for(i = res; i < n; ++i)
			assert(payload[i].u.node.idx >= idx);

		for(i = 0; i < res; ++i)
			assert(payload[i].u.node.idx < idx);
	}
#endif

	return res;
}

#else

/**
 * This function searches linearily for the node in the array.
 */
static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned idx) {
	unsigned n  = arr[0].u.head.n_members;
	unsigned i;
127

Sebastian Hack's avatar
Sebastian Hack committed
128
129
130
131
132
133
134
135
136
137
	for(i = 0; i < n; ++i) {
		if(arr[i + 1].u.node.idx == idx)
			return i;
	}

	return i;
}
#endif

struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *bl, const ir_node *irn)
138
{
Sebastian Hack's avatar
Sebastian Hack committed
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
258
259
	struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);

	if(irn_live) {
		unsigned idx = get_irn_idx(irn);

		/* Get the position of the index in the array. */
		int pos = _be_liveness_bsearch(irn_live, idx);

		/* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
		struct _be_lv_info_node_t *res = &irn_live[pos + 1].u.node;

		/* Check, if the irn is in deed in the array. */
		if(res->idx == idx)
			return res;
	}

	return NULL;
}

static struct _be_lv_info_node_t *be_lv_get_or_set(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
{
	struct _be_lv_info_t *irn_live = phase_get_or_set_irn_data(&li->ph, bl);

	unsigned idx = get_irn_idx(irn);

	/* Get the position of the index in the array. */
	unsigned pos = _be_liveness_bsearch(irn_live, idx);

	/* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
	struct _be_lv_info_node_t *res = &irn_live[pos + 1].u.node;

	/* Check, if the irn is in deed in the array. */
	if(res->idx != idx) {
		struct _be_lv_info_t *payload;
		unsigned n_members = irn_live[0].u.head.n_members;
		unsigned n_size    = irn_live[0].u.head.n_size;
		unsigned i;

		if(n_members == n_size - 1) {
			unsigned new_size = 2 * n_size * sizeof(irn_live[0]);
			struct _be_lv_info_t *nw = phase_alloc(&li->ph, new_size);
			memcpy(nw, irn_live, new_size);
			nw[0].u.head.n_size = new_size;
			irn_live = nw;
			phase_set_irn_data(&li->ph, irn, nw);
		}

		payload = &irn_live[1];
		for(i = n_members; i > pos; --i) {
			payload[i] = payload[i - 1];
		}

		++irn_live[0].u.head.n_members;

		res = &payload[pos].u.node;
		res->idx    = idx;
		res->flags  = 0;
	}

#ifdef LV_INTESIVE_CHECKS
	{
		unsigned i;
		unsigned n = irn_live[0].u.head.n_members;
		unsigned last = 0;
		struct _be_lv_info_t *payload = &irn_live[1];

		for(i = 0; i < n; ++i) {
			assert(payload[i].u.node.idx >= last);
			last = payload[i].u.node.idx;
		}
	}
#endif

	return res;
}

/**
 * Removes a node from the list of live variables of a block.
 * @return 1 if the node was live at that block, 0 if not.
 */
static int be_lv_remove(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
{
	struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);

	if(irn_live) {
		unsigned n   = irn_live[0].u.head.n_members;
		unsigned idx = get_irn_idx(irn);
		unsigned pos = _be_liveness_bsearch(irn_live, idx);
		struct _be_lv_info_t *payload  = irn_live + 1;
		struct _be_lv_info_node_t *res = &payload[pos].u.node;

		/* The node is in deed in the block's array. Let's remove it. */
		if(res->idx == idx) {
			unsigned i;

			for(i = pos + 1; i < n; ++i)
				payload[i - 1] = payload[i];

			payload[n - 1].u.node.idx   = 0;
			payload[n - 1].u.node.flags = 0;

			--irn_live[0].u.head.n_members;
			DBG((li->dbg, LEVEL_3, "\tdeleting %+F from %+F at pos %d\n", irn, bl, pos));
			return 1;
		}
	}

	return 0;
}

static void register_node(be_lv_t *lv, const ir_node *irn)
{
	unsigned idx = get_irn_idx(irn);
	if(idx >= bitset_size(lv->nodes)) {
		bitset_t *nw = bitset_malloc(2 * idx);
		bitset_copy(nw, lv->nodes);
		bitset_free(lv->nodes);
		lv->nodes = nw;
	}

	bitset_set(lv->nodes, idx);
260
261
}

Michael Beck's avatar
Michael Beck committed
262
263
264
/**
 * Mark a node as live-in in a block.
 */
Sebastian Hack's avatar
Sebastian Hack committed
265
static INLINE void mark_live_in(be_lv_t *lv, ir_node *block, ir_node *irn)
266
{
Sebastian Hack's avatar
Sebastian Hack committed
267
268
269
270
	struct _be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
	DBG((lv->dbg, LEVEL_2, "marking %+F live in at %+F\n", irn, block));
	n->flags |= be_lv_state_in;
	register_node(lv, irn);
271
272
}

Michael Beck's avatar
Michael Beck committed
273
274
275
/**
 * Mark a node as live-out in a block.
 */
Sebastian Hack's avatar
Sebastian Hack committed
276
static INLINE void mark_live_out(be_lv_t *lv, ir_node *block, ir_node *irn)
277
{
Sebastian Hack's avatar
Sebastian Hack committed
278
279
280
281
	struct _be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
	DBG((lv->dbg, LEVEL_2, "marking %+F live out at %+F\n", irn, block));
	n->flags |= be_lv_state_out | be_lv_state_end;
	register_node(lv, irn);
282
283
}

Michael Beck's avatar
Michael Beck committed
284
285
286
/**
 * Mark a node as live-end in a block.
 */
Sebastian Hack's avatar
Sebastian Hack committed
287
static INLINE void mark_live_end(be_lv_t *lv, ir_node *block, ir_node *irn)
288
{
Sebastian Hack's avatar
Sebastian Hack committed
289
290
291
292
	struct _be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
	DBG((lv->dbg, LEVEL_2, "marking %+F live end at %+F\n", irn, block));
	n->flags |= be_lv_state_end;
	register_node(lv, irn);
293
294
}

295
296
297
298
299
300
301
/**
 * 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.
302
303
 * @param is_true_out Is the node real out there or only live at the end
 * of the block.
304
 */
Sebastian Hack's avatar
Sebastian Hack committed
305
static void live_end_at_block(be_lv_t *lv, ir_node *def, ir_node *block, bitset_t *visited, int is_true_out)
306
{
Sebastian Hack's avatar
Sebastian Hack committed
307
	mark_live_end(lv, block, def);
Sebastian Hack's avatar
Sebastian Hack committed
308
	if(is_true_out)
Sebastian Hack's avatar
Sebastian Hack committed
309
		mark_live_out(lv, block, def);
310

Sebastian Hack's avatar
Sebastian Hack committed
311
312
	if(!bitset_contains_irn(visited, block)) {
		bitset_add_irn(visited, block);
313

Sebastian Hack's avatar
Sebastian Hack committed
314
315
316
317
318
319
		/*
		* If this block is not the definition block, we have to go up
		* further.
		*/
		if(get_nodes_block(def) != block) {
			int i, n;
320

Sebastian Hack's avatar
Sebastian Hack committed
321
			mark_live_in(lv, block, def);
322

Sebastian Hack's avatar
Sebastian Hack committed
323
			for(i = 0, n = get_Block_n_cfgpreds(block); i < n; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
324
				live_end_at_block(lv, def, get_Block_cfgpred_block(block, i), visited, 1);
Sebastian Hack's avatar
Sebastian Hack committed
325
		}
326

Sebastian Hack's avatar
Sebastian Hack committed
327
	}
328
329
}

Sebastian Hack's avatar
Sebastian Hack committed
330
331
332
333
334
struct _lv_walker_t {
	be_lv_t *lv;
	void *data;
};

335
336
337
338
339
340
341
/**
 * 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.
 */
Sebastian Hack's avatar
Sebastian Hack committed
342
static void liveness_for_node(ir_node *irn, void *data)
343
{
Sebastian Hack's avatar
Sebastian Hack committed
344
345
346
	struct _lv_walker_t *walker = data;
	be_lv_t *lv       = walker->lv;
	bitset_t *visited = walker->data;
Sebastian Hack's avatar
Sebastian Hack committed
347
348
349
350
	const ir_edge_t *edge;
	ir_node *def_block;

	/* Don't compute liveness information for non-data nodes. */
351
	if(!is_liveness_node(irn))
Sebastian Hack's avatar
Sebastian Hack committed
352
353
354
355
356
357
358
359
360
361
362
		return;

	bitset_clear_all(visited);
	def_block = get_nodes_block(irn);

	/* Go over all uses of the value */
	foreach_out_edge(irn, edge) {
		ir_node *use = edge->src;
		ir_node *use_block;

		/*
363
364
365
		 * If the usage is no data node, skip this use, since it does not
		 * affect the liveness of the node.
		 */
366
		if(!is_liveness_node(use))
Sebastian Hack's avatar
Sebastian Hack committed
367
368
369
370
371
372
			continue;

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

		/*
373
374
375
376
		 * 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.
		 */
Sebastian Hack's avatar
Sebastian Hack committed
377
		if(is_Phi(use)) {
Sebastian Hack's avatar
Sebastian Hack committed
378
			ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos);
Sebastian Hack's avatar
Sebastian Hack committed
379
			live_end_at_block(lv, irn, pred_block, visited, 0);
Sebastian Hack's avatar
Sebastian Hack committed
380
		}
Sebastian Hack's avatar
Sebastian Hack committed
381

Sebastian Hack's avatar
Sebastian Hack committed
382
		/*
383
384
385
		 * Else, the value is live in at this block. Mark it and call live
		 * out on the predecessors.
		 */
Sebastian Hack's avatar
Sebastian Hack committed
386
387
		else if(def_block != use_block) {
			int i, n;
Sebastian Hack's avatar
Sebastian Hack committed
388

Sebastian Hack's avatar
Sebastian Hack committed
389
			mark_live_in(lv, use_block, irn);
Sebastian Hack's avatar
Sebastian Hack committed
390

Sebastian Hack's avatar
Sebastian Hack committed
391
392
			for(i = 0, n = get_Block_n_cfgpreds(use_block); i < n; ++i) {
				ir_node *pred_block = get_Block_cfgpred_block(use_block, i);
Sebastian Hack's avatar
Sebastian Hack committed
393
				live_end_at_block(lv, irn, pred_block, visited, 1);
Sebastian Hack's avatar
Sebastian Hack committed
394
395
396
			}
		}
	}
397
398
}

Sebastian Hack's avatar
Sebastian Hack committed
399
static void lv_remove_irn_walker(ir_node *bl, void *data)
400
{
Sebastian Hack's avatar
Sebastian Hack committed
401
402
403
404
	struct _lv_walker_t *w = data;
	be_lv_t *lv  = w->lv;
	ir_node *irn = w->data;
	be_lv_remove(lv, bl, irn);
405
}
Sebastian Hack's avatar
Sebastian Hack committed
406

Sebastian Hack's avatar
Sebastian Hack committed
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
static const char *lv_flags_to_str(unsigned flags)
{
	static const char *states[] = {
		"---",
		"i--",
		"-e-",
		"ie-",
		"--o",
		"i-o",
		"-eo",
		"ieo"
	};

	return states[flags & 7];
}
422

Sebastian Hack's avatar
Sebastian Hack committed
423
static void lv_dump_block(void *context, FILE *f, const ir_node *bl)
424
{
Sebastian Hack's avatar
Sebastian Hack committed
425
426
427
428
429
430
431
432
433
434
435
436
	if(is_Block(bl)) {
		be_lv_t *lv = context;
		struct _be_lv_info_t *info = phase_get_irn_data(&lv->ph, bl);

		fprintf(f, "liveness:\n");
		if(info) {
			unsigned n = info[0].u.head.n_members;
			unsigned i;

			for(i = 0; i < n; ++i) {
				struct _be_lv_info_node_t *n = &info[i+1].u.node;
				ir_fprintf(f, "%s %+F\n", lv_flags_to_str(n->flags), get_idx_irn(lv->irg, n->idx));
437
438
439
			}
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
440
}
441

Sebastian Hack's avatar
Sebastian Hack committed
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
static void *lv_phase_data_init(phase_t *phase, ir_node *irn, void *old)
{
	struct _be_lv_info_t *info = phase_alloc(phase, LV_STD_SIZE * sizeof(info[0]));
	memset(info, 0, LV_STD_SIZE * sizeof(info[0]));
	info[0].u.head.n_size = LV_STD_SIZE - 1;
	return info;
}

static void compute_liveness(be_lv_t *lv)
{
	struct _lv_walker_t w;
	w.lv   = lv;
	w.data = bitset_malloc(get_irg_last_idx(lv->irg));
	irg_walk_graph(lv->irg, liveness_for_node, NULL, &w);
	bitset_free(w.data);
457
458
}

Michael Beck's avatar
Michael Beck committed
459
/* Compute the inter block liveness for a graph. */
Sebastian Hack's avatar
Sebastian Hack committed
460
be_lv_t *be_liveness(ir_graph *irg)
Sebastian Hack's avatar
Sebastian Hack committed
461
{
Sebastian Hack's avatar
Sebastian Hack committed
462
463
464
465
466
467
468
469
470
471
472
473
474
475
	be_lv_t *lv = xmalloc(sizeof(lv[0]));

	memset(lv, 0, sizeof(lv[0]));
	FIRM_DBG_REGISTER(lv->dbg, DBG_MODULE);
	lv->irg = irg;
	lv->nodes = bitset_malloc(2 * get_irg_last_idx(irg));
	lv->hook_info.context = lv;
	lv->hook_info.hook._hook_node_info = lv_dump_block;
	register_hook(hook_node_info, &lv->hook_info);
	phase_init(&lv->ph, "liveness", irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init);
	compute_liveness(lv);

	return lv;
}
Sebastian Hack's avatar
Sebastian Hack committed
476

Sebastian Hack's avatar
Sebastian Hack committed
477
478
479
480
481
482
483
void be_liveness_recompute(be_lv_t *lv)
{
	unsigned last_idx = get_irg_last_idx(lv->irg);
	if(last_idx >= bitset_size(lv->nodes)) {
		bitset_free(lv->nodes);
		lv->nodes = bitset_malloc(last_idx * 2);
	}
Sebastian Hack's avatar
Sebastian Hack committed
484

Sebastian Hack's avatar
Sebastian Hack committed
485
486
487
488
489
490
491
	else
		bitset_clear_all(lv->nodes);

	phase_free(&lv->ph);
	phase_init(&lv->ph, "liveness", lv->irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init);
	compute_liveness(lv);
}
Sebastian Hack's avatar
Sebastian Hack committed
492

493

Sebastian Hack's avatar
Sebastian Hack committed
494
495
496
497
498
499
void be_liveness_free(be_lv_t *lv)
{
	unregister_hook(hook_node_info, &lv->hook_info);
	phase_free(&lv->ph);
	bitset_free(lv->nodes);
	free(lv);
Sebastian Hack's avatar
Sebastian Hack committed
500
}
Sebastian Hack's avatar
Sebastian Hack committed
501

Sebastian Hack's avatar
Sebastian Hack committed
502
void be_liveness_remove(be_lv_t *lv, ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
503
{
Sebastian Hack's avatar
Sebastian Hack committed
504
505
506
507
508
509
510
511
512
513
514
515
516
517
	unsigned idx = get_irn_idx(irn);
	struct _lv_walker_t w;

	/*
	 * Removes a single irn from the liveness information.
	 * Since an irn can only be live at blocks dominated by the block of its
	 * definition, we only have to process that dominance subtree.
	 */
	w.lv   = lv;
	w.data = irn;
	dom_tree_walk(get_nodes_block(irn), lv_remove_irn_walker, NULL, &w);
	if(idx <= bitset_size(lv->nodes))
		bitset_clear(lv->nodes, idx);
}
Sebastian Hack's avatar
Sebastian Hack committed
518

Sebastian Hack's avatar
Sebastian Hack committed
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
void be_liveness_introduce(be_lv_t *lv, ir_node *irn)
{
	struct _lv_walker_t w;
	w.lv   = lv;
	w.data = bitset_malloc(get_irg_last_idx(lv->irg));
	liveness_for_node(irn, &w);
	bitset_free(w.data);
}

void be_liveness_update(be_lv_t *lv, ir_node *irn)
{
	be_liveness_remove(lv, irn);
	be_liveness_introduce(lv, irn);
}

static void lv_add_missing_walker(ir_node *irn, void *data)
{
	struct _lv_walker_t *w = data;
	if(!is_Block(irn) && !bitset_contains_irn(w->lv->nodes, irn)) {
		liveness_for_node(irn, w);
	}
}

void be_liveness_add_missing(be_lv_t *lv)
{
	struct _lv_walker_t w;
	w.lv   = lv;
	w.data = bitset_malloc(get_irg_last_idx(lv->irg));
	irg_walk_graph(lv->irg, lv_add_missing_walker, NULL, &w);
	bitset_free(w.data);
}

static void lv_check_walker(ir_node *bl, void *data)
{
	struct _lv_walker_t *w = data;
	be_lv_t *lv    = w->lv;
	be_lv_t *fresh = w->data;

	struct _be_lv_info_t *curr = phase_get_irn_data(&lv->ph, bl);
	struct _be_lv_info_t *fr   = phase_get_irn_data(&fresh->ph, bl);

	if(!fr && curr && curr[0].u.head.n_members > 0) {
		unsigned i;

		ir_fprintf(stderr, "%+F liveness should be empty but current liveness contains:\n", bl);
		for(i = 0; i < curr[0].u.head.n_members; ++i) {
			ir_fprintf(stderr, "\t%+F\n", get_idx_irn(lv->irg, curr[1 + i].u.node.idx));
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
568

Sebastian Hack's avatar
Sebastian Hack committed
569
570
571
	else if(curr) {
		unsigned n_curr  = curr[0].u.head.n_members;
		unsigned n_fresh = fr[0].u.head.n_members;
Sebastian Hack's avatar
Sebastian Hack committed
572

Sebastian Hack's avatar
Sebastian Hack committed
573
		unsigned i;
Sebastian Hack's avatar
Sebastian Hack committed
574

Sebastian Hack's avatar
Sebastian Hack committed
575
576
		if(n_curr != n_fresh) {
			ir_fprintf(stderr, "%+F: liveness set sizes differ. curr %d, correct %d\n", bl, n_curr, n_fresh);
Sebastian Hack's avatar
Sebastian Hack committed
577

Sebastian Hack's avatar
Sebastian Hack committed
578
579
580
581
582
583
584
585
586
587
588
589
			ir_fprintf(stderr, "current:\n");
			for(i = 0; i < n_curr; ++i) {
				struct _be_lv_info_node_t *n = &curr[1 + i].u.node;
				ir_fprintf(stderr, "%+F %u %+F %s\n", bl, i, get_idx_irn(lv->irg, n->idx), lv_flags_to_str(n->flags));
			}

			ir_fprintf(stderr, "correct:\n");
			for(i = 0; i < n_fresh; ++i) {
				struct _be_lv_info_node_t *n = &fr[1 + i].u.node;
				ir_fprintf(stderr, "%+F %u %+F %s\n", bl, i, get_idx_irn(lv->irg, n->idx), lv_flags_to_str(n->flags));
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
590
591
592
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
void be_liveness_check(be_lv_t *lv)
{
	struct _lv_walker_t w;
	be_lv_t *fresh = be_liveness(lv->irg);

	w.lv   = lv;
	w.data = fresh;
	irg_block_walk_graph(lv->irg, lv_check_walker, NULL, &w);
	be_liveness_free(fresh);
}


static void lv_dump_block_walker(ir_node *irn, void *data)
{
	struct _lv_walker_t *w = data;
	if(is_Block(irn))
		lv_dump_block(w->lv, w->data, irn);
}


Michael Beck's avatar
Michael Beck committed
613
/* Dump the liveness information for a graph. */
Sebastian Hack's avatar
Sebastian Hack committed
614
void be_liveness_dump(const be_lv_t *lv, FILE *f)
Sebastian Hack's avatar
Sebastian Hack committed
615
{
Sebastian Hack's avatar
Sebastian Hack committed
616
617
618
619
620
	struct _lv_walker_t w;

	w.lv   = (be_lv_t *) lv;
	w.data = f;
	irg_block_walk_graph(lv->irg, lv_dump_block_walker, NULL, &w);
Sebastian Hack's avatar
Sebastian Hack committed
621
}
Sebastian Hack's avatar
Sebastian Hack committed
622

Michael Beck's avatar
Michael Beck committed
623
/* Dump the liveness information for a graph. */
Sebastian Hack's avatar
Sebastian Hack committed
624
void be_liveness_dumpto(const be_lv_t *lv, const char *cls_name)
Daniel Grund's avatar
Daniel Grund committed
625
626
627
{
	FILE *f;
	char buf[128];
Sebastian Hack's avatar
Sebastian Hack committed
628
	ir_snprintf(buf, sizeof(buf), "%F_%s-live.txt", lv->irg, cls_name);
Daniel Grund's avatar
Daniel Grund committed
629
	if((f = fopen(buf, "wt")) != NULL) {
Sebastian Hack's avatar
Sebastian Hack committed
630
		be_liveness_dump(lv, f);
Daniel Grund's avatar
Daniel Grund committed
631
632
633
634
		fclose(f);
	}
}

Michael Beck's avatar
Michael Beck committed
635
636
637
638
/**
 * Walker: checks the every predecessors of a node dominate
 * the note.
 */
Sebastian Hack's avatar
Sebastian Hack committed
639
640
static void dom_check(ir_node *irn, void *data)
{
641
642
	int *problem_found = data;

Daniel Grund's avatar
Daniel Grund committed
643
	if(!is_Block(irn) && irn != get_irg_end(get_irn_irg(irn))) {
Sebastian Hack's avatar
Sebastian Hack committed
644
645
646
647
648
649
650
651
652
653
654
		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);

655
656
657
658
659
			if(get_irn_opcode(use_bl) != iro_Bad
			     && get_irn_opcode(def_bl) != iro_Bad
			     && !block_dominates(def_bl, use_bl)) {
				ir_fprintf(stderr, "Verify warning: %+F in %+F must dominate %+F for user %+F (%s)\n", op, def_bl, use_bl, irn, get_irg_dump_name(get_irn_irg(op)));
				*problem_found = 1;
Daniel Grund's avatar
Daniel Grund committed
660
			}
Sebastian Hack's avatar
Sebastian Hack committed
661
662
663
664
		}
	}
}

Michael Beck's avatar
Michael Beck committed
665
/* Check, if the SSA dominance property is fulfilled. */
666
int be_check_dominance(ir_graph *irg)
Sebastian Hack's avatar
Sebastian Hack committed
667
{
668
669
670
671
672
	int problem_found = 0;

	irg_walk_graph(irg, dom_check, NULL, &problem_found);

	return !problem_found;
Sebastian Hack's avatar
Sebastian Hack committed
673
}
Sebastian Hack's avatar
Sebastian Hack committed
674
675
676
677

pset *be_liveness_transfer(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_node *irn, pset *live)
{
	int i, n;
678
	FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
Sebastian Hack's avatar
Sebastian Hack committed
679

680
	DEBUG_ONLY(
Matthias Braun's avatar
Matthias Braun committed
681
		const ir_node *x;
682
683
684
685
686
		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));
	)

687
688
689
	/* You should better break out of your loop when hitting the first phi function. */
	assert(!is_Phi(irn) && "liveness_transfer produces invalid results for phi nodes");

690
691
692
693
	if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
		ir_node *del = pset_remove_ptr(live, irn);
		assert(irn == del);
	}
Sebastian Hack's avatar
Sebastian Hack committed
694
695
696
697
698
699
700
701
702
703
704

	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;
}

Sebastian Hack's avatar
Sebastian Hack committed
705
pset *be_liveness_end_of_block(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *bl, pset *live)
Sebastian Hack's avatar
Sebastian Hack committed
706
{
Sebastian Hack's avatar
Sebastian Hack committed
707
708
709
710
	int i;
	be_lv_foreach(lv, bl, be_lv_state_end, i) {
		ir_node *irn = be_lv_get_irn(lv, bl, i);
		if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
Sebastian Hack's avatar
Sebastian Hack committed
711
712
713
714
715
716
			pset_insert_ptr(live, irn);
	}

	return live;
}

Sebastian Hack's avatar
Sebastian Hack committed
717
pset *be_liveness_nodes_live_at(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live)
Sebastian Hack's avatar
Sebastian Hack committed
718
{
719
	const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
Sebastian Hack's avatar
Sebastian Hack committed
720
721
	ir_node *irn;

Sebastian Hack's avatar
Sebastian Hack committed
722
	be_liveness_end_of_block(lv, arch_env, cls, bl, live);
Sebastian Hack's avatar
Sebastian Hack committed
723
724
725
726
727
728
729
730
731
732
733
734
735
	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;
}