belive.c 16.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       Interblock liveness analysis.
 * @author      Sebastian Hack
 * @date        06.12.2004
11
 */
12
13
14
/* statev is expensive here, only enable when needed */
#define DISABLE_STATEV

Sebastian Hack's avatar
Sebastian Hack committed
15
#include "iredges_t.h"
16
#include "irgwalk.h"
17
#include "irprintf.h"
18
#include "irdump_t.h"
19
#include "irnodeset.h"
20

Sebastian Hack's avatar
Sebastian Hack committed
21
#include "absgraph.h"
Matthias Braun's avatar
Matthias Braun committed
22
#include "statev_t.h"
23
#include "be_t.h"
24
#include "bearch.h"
25
26
#include "beutil.h"
#include "belive_t.h"
27
#include "besched.h"
Matthias Braun's avatar
Matthias Braun committed
28
#include "bemodule.h"
29
#include "beirg.h"
Sebastian Hack's avatar
Sebastian Hack committed
30

Matthias Braun's avatar
Matthias Braun committed
31
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
32

33
#define LV_STD_SIZE             64
34

Sebastian Hack's avatar
Sebastian Hack committed
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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);
}

50
static inline unsigned _be_liveness_bsearch(be_lv_info_t *arr, const ir_node *node)
Sebastian Hack's avatar
Sebastian Hack committed
51
{
52
	be_lv_info_t *payload = arr + 1;
Sebastian Hack's avatar
Sebastian Hack committed
53

54
	unsigned n   = arr[0].head.n_members;
Sebastian Hack's avatar
Sebastian Hack committed
55
56
57
58
	unsigned res = 0;
	int lo       = 0;
	int hi       = n;

Michael Beck's avatar
Michael Beck committed
59
	if (n == 0)
Sebastian Hack's avatar
Sebastian Hack committed
60
61
		return 0;

Michael Beck's avatar
Michael Beck committed
62
	do {
63
64
		int md           = lo + ((hi - lo) >> 1);
		ir_node *md_node = payload[md].node.node;
Sebastian Hack's avatar
Sebastian Hack committed
65

66
		if (node > md_node) {
Sebastian Hack's avatar
Sebastian Hack committed
67
			lo = md + 1;
68
		} else if (node < md_node) {
Sebastian Hack's avatar
Sebastian Hack committed
69
			hi = md;
70
		} else {
Sebastian Hack's avatar
Sebastian Hack committed
71
72
73
74
75
			res = md;
			break;
		}

		res = lo;
Michael Beck's avatar
Michael Beck committed
76
	} while (lo < hi);
Sebastian Hack's avatar
Sebastian Hack committed
77
78
79
80

	return res;
}

81
82
be_lv_info_node_t *be_lv_get(const be_lv_t *li, const ir_node *bl,
                             const ir_node *irn)
83
{
84
85
	be_lv_info_t *irn_live;
	be_lv_info_node_t *res = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
86

Sebastian Hack's avatar
Sebastian Hack committed
87
	stat_ev_tim_push();
88
	irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
89
	if (irn_live != NULL) {
Sebastian Hack's avatar
Sebastian Hack committed
90
		/* Get the position of the index in the array. */
91
		int pos = _be_liveness_bsearch(irn_live, irn);
Sebastian Hack's avatar
Sebastian Hack committed
92
93

		/* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
94
		be_lv_info_node_t *rec = &irn_live[pos + 1].node;
Sebastian Hack's avatar
Sebastian Hack committed
95
96

		/* Check, if the irn is in deed in the array. */
97
		if (rec->node == irn)
Sebastian Hack's avatar
Sebastian Hack committed
98
			res = rec;
Sebastian Hack's avatar
Sebastian Hack committed
99
	}
Sebastian Hack's avatar
Sebastian Hack committed
100
	stat_ev_tim_pop("be_lv_get");
Sebastian Hack's avatar
Sebastian Hack committed
101

Sebastian Hack's avatar
Sebastian Hack committed
102
	return res;
Sebastian Hack's avatar
Sebastian Hack committed
103
104
}

105
106
static be_lv_info_node_t *be_lv_get_or_set(be_lv_t *li, ir_node *bl,
                                           ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
107
{
108
	be_lv_info_t *irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
109
110
111
112
113
	if (irn_live == NULL) {
		irn_live = OALLOCNZ(&li->obst, be_lv_info_t, LV_STD_SIZE);
		irn_live[0].head.n_size = LV_STD_SIZE-1;
		ir_nodehashmap_insert(&li->map, bl, irn_live);
	}
Sebastian Hack's avatar
Sebastian Hack committed
114
115

	/* Get the position of the index in the array. */
116
	unsigned pos = _be_liveness_bsearch(irn_live, irn);
Sebastian Hack's avatar
Sebastian Hack committed
117
118

	/* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
119
	be_lv_info_node_t *res = &irn_live[pos + 1].node;
Sebastian Hack's avatar
Sebastian Hack committed
120
121

	/* Check, if the irn is in deed in the array. */
122
	if (res->node != irn) {
123
		be_lv_info_t *payload;
124
125
		unsigned n_members = irn_live[0].head.n_members;
		unsigned n_size    = irn_live[0].head.n_size;
Sebastian Hack's avatar
Sebastian Hack committed
126
127
		unsigned i;

128
		if (n_members + 1 >= n_size) {
129
130
131
132
133
			/* double the array size. Remember that the first entry is
			 * metadata about the array and not a real array element */
			unsigned old_size_bytes  = (n_size + 1) * sizeof(irn_live[0]);
			unsigned new_size        = (2 * n_size) + 1;
			size_t   new_size_bytes  = new_size * sizeof(irn_live[0]);
134
			be_lv_info_t *nw = OALLOCN(&li->obst, be_lv_info_t, new_size);
135
136
137
			memcpy(nw, irn_live, old_size_bytes);
			memset(((char*) nw) + old_size_bytes, 0,
			       new_size_bytes - old_size_bytes);
138
			nw[0].head.n_size = new_size - 1;
Sebastian Hack's avatar
Sebastian Hack committed
139
			irn_live = nw;
140
			ir_nodehashmap_insert(&li->map, bl, nw);
Sebastian Hack's avatar
Sebastian Hack committed
141
142
143
		}

		payload = &irn_live[1];
144
		for (i = n_members; i > pos; --i) {
Sebastian Hack's avatar
Sebastian Hack committed
145
146
147
			payload[i] = payload[i - 1];
		}

148
		++irn_live[0].head.n_members;
Sebastian Hack's avatar
Sebastian Hack committed
149

150
151
152
		res        = &payload[pos].node;
		res->node  = irn;
		res->flags = 0;
Sebastian Hack's avatar
Sebastian Hack committed
153
154
155
156
157
	}

	return res;
}

158
159
160
161
162
typedef struct lv_remove_walker_t {
	be_lv_t       *lv;
	ir_node const *irn;
} lv_remove_walker_t;

Sebastian Hack's avatar
Sebastian Hack committed
163
164
165
/**
 * Removes a node from the list of live variables of a block.
 */
166
static void lv_remove_irn_walker(ir_node *const bl, void *const data)
Sebastian Hack's avatar
Sebastian Hack committed
167
{
168
169
170
	lv_remove_walker_t *const w        = (lv_remove_walker_t*)data;
	ir_node      const *const irn      = w->irn;
	be_lv_info_t       *const irn_live = ir_nodehashmap_get(be_lv_info_t, &w->lv->map, bl);
171
172
	if (irn_live != NULL) {
		unsigned n   = irn_live[0].head.n_members;
173
		unsigned pos = _be_liveness_bsearch(irn_live, irn);
174
		be_lv_info_t *payload  = irn_live + 1;
175
		be_lv_info_node_t *res = &payload[pos].node;
Sebastian Hack's avatar
Sebastian Hack committed
176
177

		/* The node is in deed in the block's array. Let's remove it. */
178
		if (res->node == irn) {
Sebastian Hack's avatar
Sebastian Hack committed
179
180
			unsigned i;

181
			for (i = pos + 1; i < n; ++i)
Sebastian Hack's avatar
Sebastian Hack committed
182
183
				payload[i - 1] = payload[i];

184
			payload[n - 1].node.node  = NULL;
185
			payload[n - 1].node.flags = 0;
Sebastian Hack's avatar
Sebastian Hack committed
186

187
			--irn_live[0].head.n_members;
Matthias Braun's avatar
Matthias Braun committed
188
			DBG((dbg, LEVEL_3, "\tdeleting %+F from %+F at pos %d\n", irn, bl, pos));
Sebastian Hack's avatar
Sebastian Hack committed
189
190
191
192
		}
	}
}

193
194
static struct {
	be_lv_t  *lv;         /**< The liveness object. */
195
	ir_node  *def;        /**< The node (value). */
196
197
198
	ir_node  *def_block;  /**< The block of def. */
} re;

199
200
201
202
203
/**
 * 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 block The block to mark the value live out of.
204
 * @param state The liveness bits to set, either end or end+out.
205
 */
206
static void live_end_at_block(ir_node *const block, be_lv_state_t const state)
207
{
208
209
	be_lv_info_node_t *const n      = be_lv_get_or_set(re.lv, block, re.def);
	be_lv_state_t      const before = n->flags;
210

211
212
213
	assert(state == be_lv_state_end || state == (be_lv_state_end | be_lv_state_out));
	DBG((dbg, LEVEL_2, "marking %+F live %s at %+F\n", re.def, state & be_lv_state_out ? "end+out" : "end", block));
	n->flags |= state;
214

215
216
217
218
	/* There is no need to recurse further, if we where here before (i.e., any
	 * live state bits were set before). */
	if (before != be_lv_state_none)
		return;
219

220
221
222
	/* Stop going up further, if this is the block of the definition. */
	if (re.def_block == block)
		return;
223

224
225
	DBG((dbg, LEVEL_2, "marking %+F live in at %+F\n", re.def, block));
	n->flags |= be_lv_state_in;
226

227
228
229
	for (int i = get_Block_n_cfgpreds(block); i-- != 0;) {
		ir_node *const pred_block = get_Block_cfgpred_block(block, i);
		live_end_at_block(pred_block, be_lv_state_end | be_lv_state_out);
Sebastian Hack's avatar
Sebastian Hack committed
230
	}
231
232
233
234
}

/**
 * Liveness analysis for a value.
235
236
 * Compute the set of all blocks a value is live in.
 * @param irn     The node (value).
237
 */
238
static void liveness_for_node(ir_node *irn)
239
{
240
	ir_node *const def_block = get_nodes_block(irn);
Sebastian Hack's avatar
Sebastian Hack committed
241

242
243
244
	re.def       = irn;
	re.def_block = def_block;

Sebastian Hack's avatar
Sebastian Hack committed
245
246
247
248
249
	/* Go over all uses of the value */
	foreach_out_edge(irn, edge) {
		ir_node *use = edge->src;
		ir_node *use_block;

Sebastian Hack's avatar
Sebastian Hack committed
250
251
252
		DBG((dbg, LEVEL_4, "%+F: use at %+F, pos %d in %+F\n", irn, use, edge->pos, get_block(use)));
		assert(get_irn_n(use, edge->pos) == irn);

Sebastian Hack's avatar
Sebastian Hack committed
253
		/*
254
255
256
		 * If the usage is no data node, skip this use, since it does not
		 * affect the liveness of the node.
		 */
257
		if (!is_liveness_node(use))
Sebastian Hack's avatar
Sebastian Hack committed
258
259
260
261
262
263
			continue;

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

		/*
264
265
266
267
		 * 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.
		 */
268
		if (is_Phi(use)) {
Sebastian Hack's avatar
Sebastian Hack committed
269
			ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos);
270
			live_end_at_block(pred_block, be_lv_state_end);
271
272
273
274
275
		} else if (def_block != use_block) {
			/*
			 * Else, the value is live in at this block. Mark it and call live
			 * out on the predecessors.
			 */
276
			int i;
Sebastian Hack's avatar
Sebastian Hack committed
277

278
279
280
			be_lv_info_node_t *const n = be_lv_get_or_set(re.lv, use_block, irn);
			DBG((dbg, LEVEL_2, "marking %+F live in at %+F\n", irn, use_block));
			n->flags |= be_lv_state_in;
Sebastian Hack's avatar
Sebastian Hack committed
281

282
			for (i = get_Block_n_cfgpreds(use_block) - 1; i >= 0; --i) {
Sebastian Hack's avatar
Sebastian Hack committed
283
				ir_node *pred_block = get_Block_cfgpred_block(use_block, i);
284
				live_end_at_block(pred_block, be_lv_state_end | be_lv_state_out);
Sebastian Hack's avatar
Sebastian Hack committed
285
286
287
			}
		}
	}
288
289
}

290
291
292
293
/**
 * Walker, collect all nodes for which we want calculate liveness info
 * on an obstack.
 */
Michael Beck's avatar
Michael Beck committed
294
static void collect_liveness_nodes(ir_node *irn, void *data)
295
{
296
	ir_node **nodes = (ir_node**)data;
297
	if (is_liveness_node(irn))
298
		nodes[get_irn_idx(irn)] = irn;
299
300
}

301
void be_liveness_compute_sets(be_lv_t *lv)
Sebastian Hack's avatar
Sebastian Hack committed
302
{
303
304
305
306
307
308
309
310
311
	int       i;
	int       n;

	if (lv->sets_valid)
		return;

	be_timer_push(T_LIVE);
	ir_nodehashmap_init(&lv->map);
	obstack_init(&lv->obst);
312

313
	n = get_irg_last_idx(lv->irg);
314
	ir_node **const nodes = NEW_ARR_FZ(ir_node*, n);
315

316
	/* inserting the variables sorted by their ID is probably
317
	 * more efficient since the binary sorted set insertion
318
	 * will not need to move around the data. */
319
	irg_walk_graph(lv->irg, NULL, collect_liveness_nodes, nodes);
320

321
	re.lv = lv;
322

323
324
325
326
	for (i = 0; i < n; ++i) {
		if (nodes[i] != NULL)
			liveness_for_node(nodes[i]);
	}
327

328
	DEL_ARR_F(nodes);
329

330
	be_timer_pop(T_LIVE);
Matthias Braun's avatar
Matthias Braun committed
331

332
333
	lv->sets_valid = true;
}
Matthias Braun's avatar
Matthias Braun committed
334

335
336
337
338
339
void be_liveness_compute_chk(be_lv_t *lv)
{
	if (lv->lvc != NULL)
		return;
	lv->lvc = lv_chk_new(lv->irg);
Sebastian Hack's avatar
Sebastian Hack committed
340
341
}

342
void be_liveness_invalidate_sets(be_lv_t *lv)
Sebastian Hack's avatar
Sebastian Hack committed
343
{
344
345
346
347
348
	if (!lv->sets_valid)
		return;
	obstack_free(&lv->obst, NULL);
	ir_nodehashmap_destroy(&lv->map);
	lv->sets_valid = false;
Sebastian Hack's avatar
Sebastian Hack committed
349
350
}

351
void be_liveness_invalidate_chk(be_lv_t *lv)
Sebastian Hack's avatar
Sebastian Hack committed
352
{
353
354
355
356
357
358
	be_liveness_invalidate_sets(lv);

	if (lv->lvc == NULL)
		return;
	lv_chk_free(lv->lvc);
	lv->lvc = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
359
360
}

361
be_lv_t *be_liveness_new(ir_graph *irg)
Sebastian Hack's avatar
Sebastian Hack committed
362
{
363
	be_lv_t *lv = XMALLOCZ(be_lv_t);
Sebastian Hack's avatar
Sebastian Hack committed
364

365
	lv->irg = irg;
Sebastian Hack's avatar
Sebastian Hack committed
366
367
368

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

Sebastian Hack's avatar
Sebastian Hack committed
370
371
void be_liveness_free(be_lv_t *lv)
{
372
373
374
	be_liveness_invalidate_sets(lv);
	be_liveness_invalidate_chk(lv);

375
	free(lv);
Sebastian Hack's avatar
Sebastian Hack committed
376
}
Sebastian Hack's avatar
Sebastian Hack committed
377

378
void be_liveness_remove(be_lv_t *lv, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
379
{
380
	if (lv->sets_valid) {
381
		lv_remove_walker_t w;
Sebastian Hack's avatar
Sebastian Hack committed
382

Sebastian Hack's avatar
Sebastian Hack committed
383
384
385
386
387
		/*
		 * 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.
		 */
388
389
		w.lv  = lv;
		w.irn = irn;
Sebastian Hack's avatar
Sebastian Hack committed
390
391
		dom_tree_walk(get_nodes_block(irn), lv_remove_irn_walker, NULL, &w);
	}
Sebastian Hack's avatar
Sebastian Hack committed
392
}
Sebastian Hack's avatar
Sebastian Hack committed
393

Sebastian Hack's avatar
Sebastian Hack committed
394
395
void be_liveness_introduce(be_lv_t *lv, ir_node *irn)
{
396
	/* Don't compute liveness information for non-data nodes. */
397
	if (lv->sets_valid && is_liveness_node(irn)) {
398
		re.lv = lv;
399
		liveness_for_node(irn);
Sebastian Hack's avatar
Sebastian Hack committed
400
	}
Sebastian Hack's avatar
Sebastian Hack committed
401
402
403
404
405
406
407
408
}

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

409
void be_liveness_transfer(const arch_register_class_t *cls,
410
                          ir_node *node, ir_nodeset_t *nodeset)
411
412
413
414
415
{
	/* You should better break out of your loop when hitting the first phi
	 * function. */
	assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");

416
	be_foreach_definition(node, cls, value, req,
417
418
		ir_nodeset_remove(nodeset, value);
	);
419

420
	be_foreach_use(node, cls, in_req, op, op_req,
421
		ir_nodeset_insert(nodeset, op);
422
	);
423
424
425
426
}



427
void be_liveness_end_of_block(const be_lv_t *lv,
428
429
                              const arch_register_class_t *cls,
                              const ir_node *block, ir_nodeset_t *live)
430
{
Matthias Braun's avatar
Matthias Braun committed
431
	assert(lv->sets_valid && "live sets must be computed");
432
	be_lv_foreach_cls(lv, block, be_lv_state_end, cls, node) {
433
434
435
436
		ir_nodeset_insert(live, node);
	}
}

437
void be_liveness_nodes_live_before(be_lv_t const *const lv, arch_register_class_t const *const cls, ir_node const *const pos, ir_nodeset_t *const live)
Sebastian Hack's avatar
Sebastian Hack committed
438
{
439
	ir_node *const bl = get_nodes_block(pos);
440
	be_liveness_end_of_block(lv, cls, bl, live);
Sebastian Hack's avatar
Sebastian Hack committed
441
	sched_foreach_reverse(bl, irn) {
442
		be_liveness_transfer(cls, irn, live);
443
		if (irn == pos)
444
			return;
Sebastian Hack's avatar
Sebastian Hack committed
445
446
	}
}
447

448
449
450
451
452
453
/**
 * Check if value @p value is live at definition of @p after.
 * @note assumes value dominates after
 */
static bool value_live_after(const ir_node *const value,
                             const ir_node *const after)
Matthias Braun's avatar
Matthias Braun committed
454
{
455
456
457
	/* If value is live end in after's block it is
	 * live at after's definition (value dominates after) */
	const ir_node  *const bb  = get_nodes_block(after);
458
459
	const ir_graph *const irg = get_Block_irg(bb);
	const be_lv_t  *const lv  = be_get_irg_liveness(irg);
460
	if (be_is_live_end(lv, bb, value))
Matthias Braun's avatar
Matthias Braun committed
461
462
		return true;

463
464
465
466
467
468
469
470
	/* Look at all usages of value.
	 * If there's one usage of value in the block of after, then we check, if
	 * this use is dominated by after, if that's true value and after interfere.
	 * Note that after must strictly dominate the user, since if after is the
	 * last user of in the block, after and value do not interfere.
	 * Uses of value not in after's block can be disobeyed, because the check
	 * for value being live at the end of after's block is already performed. */
	foreach_out_edge(value, edge) {
Matthias Braun's avatar
Matthias Braun committed
471
472
		const ir_node *const user = get_edge_src_irn(edge);
		if (get_nodes_block(user) == bb && !is_Phi(user)
473
		    && sched_comes_before(after, user))
Matthias Braun's avatar
Matthias Braun committed
474
475
476
477
478
479
			return true;
	}

	return false;
}

480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
bool be_value_live_after(const ir_node *value, const ir_node *after)
{
	assert(value != after);
	if (!value_strictly_dominates(value, after))
		return false;
	return value_live_after(value, after);
}

bool be_values_interfere(const ir_node *a, const ir_node *b)
{
	assert(a != b);
	if (value_strictly_dominates(b, a)) {
		return value_live_after(b, a);
	} else if (value_strictly_dominates(a, b)) {
		return value_live_after(a, b);
	}
	return false;
}

499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
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
static bool live_at_user(const ir_node *const users_of,
                         const ir_node *const node, const ir_node *const bb)
{
	foreach_out_edge(users_of, edge) {
		const ir_node *const user = get_edge_src_irn(edge);
		if (is_Sync(user))
			return live_at_user(user, node, bb);
		if (get_nodes_block(user) == bb && !is_Phi(user)
		    && sched_comes_before(node, user))
			return true;
	}
	return false;
}

static const ir_node *get_highest_sync_op(const ir_node *const sync)
{
	const ir_node *best = get_irn_n(sync, 0);
	for (int i = 1, arity = get_irn_arity(sync); i < arity; ++i) {
		const ir_node *other = get_irn_n(sync, i);
		if (is_Sync(other))
			other = get_highest_sync_op(other);
		if (value_strictly_dominates(other, best))
			best = other;
	}
	return best;
}

bool be_memory_values_interfere(const ir_node *a, const ir_node *b)
{
	if (is_Sync(a))
		a = get_highest_sync_op(a);
	if (is_Sync(b))
		b = get_highest_sync_op(b);

	if (value_strictly_dominates(b, a)) {
		/* Adjust a and b so, that a dominates b if
		 * a dominates b or vice versa. */
		ir_node const *const t = a;
		a = b;
		b = t;
	} else if (!value_strictly_dominates(a, b)) {
		/* If there is no dominance relation, they do not interfere. */
		return false;
	}

	/* If a is live end in b's block it is
	 * live at b's definition (a dominates b) */
	const ir_node  *const bb  = get_nodes_block(b);
	const ir_graph *const irg = get_Block_irg(bb);
	const be_lv_t  *const lv  = be_get_irg_liveness(irg);
	if (be_is_live_end(lv, bb, a))
		return true;

	/* Look at all usages of a.
	 * If there's one usage of a in the block of b, then
	 * we check, if this use is dominated by b, if that's true
	 * a and b interfere. Note that b must strictly dominate the user,
	 * since if b is the last user of in the block, b and a do not
	 * interfere.
	 * Uses of a not in b's block can be disobeyed, because the
	 * check for a being live at the end of b's block is already
	 * performed. */
	return live_at_user(a, b, bb);
}

564
565
static void collect_node(ir_node *irn, void *data)
{
566
	struct obstack *obst = (struct obstack*)data;
567
568
569
	obstack_ptr_grow(obst, irn);
}

570
static void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
571
{
Sebastian Hack's avatar
Sebastian Hack committed
572
	ir_graph *irg    = lv->irg;
573
574
575
576
577
578
579
580
581
582

	struct obstack obst;
	ir_node **nodes;
	ir_node **blocks;
	int i, j;

	obstack_init(&obst);

	irg_block_walk_graph(irg, collect_node, NULL, &obst);
	obstack_ptr_grow(&obst, NULL);
583
	blocks = (ir_node**)obstack_finish(&obst);
584
585
586

	irg_walk_graph(irg, collect_node, NULL, &obst);
	obstack_ptr_grow(&obst, NULL);
587
	nodes = (ir_node**)obstack_finish(&obst);
588

Sebastian Hack's avatar
Sebastian Hack committed
589
590
591
	stat_ev_ctx_push("be_lv_chk_compare");
	for (j = 0; nodes[j]; ++j) {
		ir_node *irn = nodes[j];
592
593
594
		if (is_Block(irn))
			continue;

Sebastian Hack's avatar
Sebastian Hack committed
595
596
		for (i = 0; blocks[i]; ++i) {
			ir_node *bl = blocks[i];
597
598
599
			int lvr_in  = be_is_live_in (lv, bl, irn);
			int lvr_out = be_is_live_out(lv, bl, irn);
			int lvr_end = be_is_live_end(lv, bl, irn);
600

601
602
603
			int lvc_in  = lv_chk_bl_in (lvc, bl, irn);
			int lvc_out = lv_chk_bl_out(lvc, bl, irn);
			int lvc_end = lv_chk_bl_end(lvc, bl, irn);
604

605
606
			if (lvr_in - lvc_in != 0)
				ir_fprintf(stderr, "live in  info for %+F at %+F differs: nml: %d, chk: %d\n", irn, bl, lvr_in, lvc_in);
607

608
609
			if (lvr_end - lvc_end != 0)
				ir_fprintf(stderr, "live end info for %+F at %+F differs: nml: %d, chk: %d\n", irn, bl, lvr_end, lvc_end);
610

611
612
			if (lvr_out - lvc_out != 0)
				ir_fprintf(stderr, "live out info for %+F at %+F differs: nml: %d, chk: %d\n", irn, bl, lvr_out, lvc_out);
613
614
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
615
	stat_ev_ctx_pop("be_lv_chk_compare");
616
617
618
619

	obstack_free(&obst, NULL);
}

Matthias Braun's avatar
Matthias Braun committed
620
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_live)
Matthias Braun's avatar
Matthias Braun committed
621
622
void be_init_live(void)
{
623
	(void)be_live_chk_compare;
Matthias Braun's avatar
Matthias Braun committed
624
625
	FIRM_DBG_REGISTER(dbg, "firm.be.liveness");
}