irlivechk.c 20 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
/*
2
 * Copyright (C) 1995-2007 Inria Rhone-Alpes.  All right reserved.
Michael Beck's avatar
Michael Beck committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Michael Beck's avatar
Michael Beck committed
21
22
23
 * @file    livechk.c
 * @date    21.04.2007
 * @author  Sebastian Hack
Michael Beck's avatar
Michael Beck committed
24
 * @version $Id$
Michael Beck's avatar
Michael Beck committed
25
 * @summary
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 *
 * Liveness checks as developed by Benoit Boissinot, Fabrice Rastello and myself.
 *
 * The speciality here is, that nothing has to be recomputed if new nodes are created
 * or old ones deleted.
 *
 * This algo has one core routine check_live_end_internal() which performs the liveness check.
 * It only relies on the precomputation done in the constructor, which in turn needs:
 * - out edges
 * - the dominance tree
 * - data obtained from a depth-first-search
 *
 * The precomputation remains valid as long as the CFG is not altered.
 */
Matthias Braun's avatar
Matthias Braun committed
40
41
42
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
43
44
45
46

#include <stdio.h>

#include "irgraph_t.h"
47
#include "irnode_t.h"
48
49
#include "irphase_t.h"
#include "iredges_t.h"
50

51
#include "irprintf.h"
52
#include "irdom.h"
53
54
55
56
57
58
59
60
#include "irdump.h"

#include "dfs_t.h"
#include "bitset.h"
#include "util.h"

#include "irlivechk.h"

61
#include "statev.h"
62

63
typedef struct _bl_info_t {
64
	const ir_node *block;      /**< The block. */
65

66
67
	int be_tgt_calc : 1;
	int id : 31;               /**< a tight number for the block.
68
69
70
71
72
73
74
75
76
77
78
79
80
81
								 we're just reusing the pre num from
								 the DFS. */
	bitset_t *red_reachable;   /**< Holds all id's if blocks reachable
								 in the CFG modulo back edges. */

	bitset_t *be_tgt_reach;	   /**< target blocks of back edges whose
								 sources are reachable from this block
								 in the reduced graph. */
} bl_info_t;

#define get_block_info(lv, bl) ((bl_info_t *) phase_get_irn_data(&(lv)->ph, bl))

struct _lv_chk_t {
	ir_phase ph;
Sebastian Hack's avatar
Sebastian Hack committed
82
	const dfs_t *dfs;
83
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
84
85
86
87
88
89
	int n_blocks;
	bitset_t *back_edge_src;
	bitset_t *back_edge_tgt;
	bl_info_t **map;
};

90
static void *init_block_data(ir_phase *ph, const ir_node *irn, void *old)
91
92
93
94
{
	lv_chk_t *lv      = container_of(ph, lv_chk_t, ph);
	bl_info_t *bi     = phase_alloc(ph, sizeof(bi[0]));

95
	bi->id            = get_Block_dom_tree_pre_num(irn);
96
97
98
	bi->block         = irn;
	bi->red_reachable = bitset_obstack_alloc(phase_obst(ph), lv->n_blocks);
	bi->be_tgt_reach  = bitset_obstack_alloc(phase_obst(ph), lv->n_blocks);
99
	bi->be_tgt_calc   = 0;
Matthias Braun's avatar
Matthias Braun committed
100
	(void) old;
101
102
103
104
105
106
107
108
109
110
111
112
113
114
	return bi;
}

/**
 * Filter function to select all nodes for which liveness is computed.
 * @param irn A node.
 * @return    1 if the node shall be considered in liveness, 0 if not.
 */
static INLINE int is_liveness_node(const ir_node *irn)
{
	switch(get_irn_opcode(irn)) {
	case iro_Block:
	case iro_Bad:
	case iro_End:
115
	case iro_Anchor:
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
		return 0;
	default:;
	}

	return 1;
}

/**
 * Compute the transitive closure on the reduced graph.
 * The reduced graph is the original graph without back edges.
 * Since that is a DAG, a reverse post order of the graph gives a toposort
 * which is ideally suited to compute the transitive closure.
 * Note also, that the DFS tree of the reduced graph is the same than the one
 * of the original graph. This saves us computing a new reverse post order.
 * We also can re-use the DFS tree of the original graph.
 */
static void red_trans_closure(lv_chk_t *lv)
{
	int i, n;

	for (i = 0, n = dfs_get_n_nodes(lv->dfs); i < n; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
137
		const ir_node *bl   = dfs_get_post_num_node(lv->dfs, i);
138
139
140
141
		bl_info_t *bi = get_block_info(lv, bl);

		const ir_edge_t *edge;

142
		bitset_set(bi->red_reachable, bi->id);
143
144
145
146
147
148
149
150
151
152
		foreach_block_succ (bl, edge) {
			ir_node *succ = get_edge_src_irn(edge);
			bl_info_t *si = get_block_info(lv, succ);
			dfs_edge_kind_t kind = dfs_get_edge_kind(lv->dfs, bl, succ);

			/*
			 * if the successor is no back edge, include all reachable
			 * blocks from there into the reachable set of the current node
			 */
			if (kind != DFS_EDGE_BACK) {
153
				assert(dfs_get_post_num(lv->dfs, bl) > dfs_get_post_num(lv->dfs, succ));
154
155
156
157
158
159
160
161
162
163
164
165
166
167
				bitset_or(bi->red_reachable, si->red_reachable);
			}

			/* mark the block as a back edge src and succ as back edge tgt. */
			else {
				bitset_set(lv->back_edge_src, bi->id);
				bitset_set(lv->back_edge_tgt, si->id);
			}
		}

	}

}

168
static void compute_back_edge_chain(lv_chk_t *lv, const ir_node *bl)
169
170
{
	bitset_t *tmp = bitset_alloca(lv->n_blocks);
171
	bl_info_t *bi = get_block_info(lv, bl);
172
173
174

	bitset_pos_t elm;

175
	DBG((lv->dbg, LEVEL_2, "computing T_%d\n", bi->id));
176

177
	/* put all back edge sources reachable (reduced) from here in tmp */
178
179
180
	bitset_copy(tmp, bi->red_reachable);
	bitset_set(tmp, bi->id);
	bitset_and(tmp, lv->back_edge_src);
181
182
183
184
185
186
187
	bi->be_tgt_calc = 1;

	DBG((lv->dbg, LEVEL_2, "\treachable be src: %B\n", tmp));

	/* iterate over them ... */
	bitset_foreach(tmp, elm) {
		bl_info_t *si = lv->map[elm];
188
189
		const ir_edge_t *edge;

190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
		/* and find back edge targets which are not reduced reachable from bl */
		foreach_block_succ (si->block, edge) {
			ir_node *tgt         = get_edge_src_irn(edge);
			bl_info_t *ti        = get_block_info(lv, tgt);
			dfs_edge_kind_t kind = dfs_get_edge_kind(lv->dfs, si->block, tgt);

			if (kind == DFS_EDGE_BACK && !bitset_is_set(bi->red_reachable, ti->id)) {
				if (!ti->be_tgt_calc)
					compute_back_edge_chain(lv, tgt);
				bitset_set(bi->be_tgt_reach, ti->id);
				bitset_or(bi->be_tgt_reach, ti->be_tgt_reach);
			}
		}
		bitset_clear(bi->be_tgt_reach, bi->id);
	}
}

207

208
209
210
211
212
213
214
215
216
217
218
static INLINE void compute_back_edge_chains(lv_chk_t *lv)
{
	bitset_pos_t elm;
	int i, n;

	DBG((lv->dbg, LEVEL_2, "back edge sources: %B\n", lv->back_edge_src));
	bitset_foreach(lv->back_edge_src, elm) {
		compute_back_edge_chain(lv, lv->map[elm]->block);
	}

	for (i = 0, n = dfs_get_n_nodes(lv->dfs); i < n; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
219
220
		const ir_node *bl = dfs_get_post_num_node(lv->dfs, i);
		bl_info_t *bi     = get_block_info(lv, bl);
221
222
223
224
225
226

		const ir_edge_t *edge;

		if (!bitset_is_set(lv->back_edge_tgt, bi->id)) {
			foreach_block_succ (bl, edge) {
				ir_node *succ = get_edge_src_irn(edge);
227
				bl_info_t *si = get_block_info(lv, succ);
228
229
230
231
232
233
				dfs_edge_kind_t kind = dfs_get_edge_kind(lv->dfs, bl, succ);

				if (kind != DFS_EDGE_BACK) {
					assert(dfs_get_post_num(lv->dfs, bl) > dfs_get_post_num(lv->dfs, succ));
					bitset_or(bi->be_tgt_reach, si->be_tgt_reach);
				}
234
235
236
			}
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
237
238
239
240
241
242

	for (i = 0, n = dfs_get_n_nodes(lv->dfs); i < n; ++i) {
		const ir_node *bl = dfs_get_post_num_node(lv->dfs, i);
		bl_info_t *bi     = get_block_info(lv, bl);
		bitset_set(bi->be_tgt_reach, bi->id);
	}
243
244
}

Sebastian Hack's avatar
Sebastian Hack committed
245
lv_chk_t *lv_chk_new(ir_graph *irg, const dfs_t *dfs)
246
{
247
	lv_chk_t *res = XMALLOC(lv_chk_t);
248
249
250
	struct obstack *obst;
	int i;

251
252
253
254
	edges_deactivate(irg);
	edges_activate(irg);
	compute_doms(irg);

Sebastian Hack's avatar
Sebastian Hack committed
255
	stat_ev_tim_push();
256
257
258
259
260
	phase_init(&res->ph, "liveness check", irg, PHASE_DEFAULT_GROWTH, init_block_data, NULL);
	obst = phase_obst(&res->ph);

	FIRM_DBG_REGISTER(res->dbg, "ir.ana.lvchk");

Sebastian Hack's avatar
Sebastian Hack committed
261
	res->dfs           = dfs;
262
263
264
265
	res->n_blocks      = dfs_get_n_nodes(res->dfs);
	res->back_edge_src = bitset_obstack_alloc(obst, res->n_blocks);
	res->back_edge_tgt = bitset_obstack_alloc(obst, res->n_blocks);
	res->map           = obstack_alloc(obst, res->n_blocks * sizeof(res->map[0]));
266
	memset(res->map, 0, res->n_blocks * sizeof(res->map[0]));
267

268
#if 0
269
270
271
272
273
274
275
276
277
278
279
280
281
282
	{
		char name[256];
		FILE *f;
		ir_snprintf(name, sizeof(name), "dfs_%F.dot", irg);
		if ((f = fopen(name, "wt")) != NULL) {
			dfs_dump(res->dfs, f);
			fclose(f);
		}
		dump_ir_block_graph(irg, "-lvchk");
	}
#endif

	/* fill the map which maps pre_num to block infos */
	for (i = res->n_blocks - 1; i >= 0; --i) {
Sebastian Hack's avatar
Sebastian Hack committed
283
284
		ir_node *irn  = (ir_node *) dfs_get_pre_num_node(res->dfs, i);
		bl_info_t *bi = phase_get_or_set_irn_data(&res->ph, irn);
285
286
		assert(bi->id < res->n_blocks);
		assert(res->map[bi->id] == NULL);
287
		res->map[bi->id] = bi;
288
289
290
291
292
	}

	/* first of all, compute the transitive closure of the CFG *without* back edges */
	red_trans_closure(res);

293
294
	/* compute back edge chains */
	compute_back_edge_chains(res);
295

Sebastian Hack's avatar
Sebastian Hack committed
296
297
298
299
300
301
302
303
304
305
#ifndef NDEBUG
	DBG((res->dbg, LEVEL_1, "liveness chk in %+F\n", irg));
	for (i = res->n_blocks - 1; i >= 0; --i) {
		const ir_node *irn = dfs_get_pre_num_node(res->dfs, i);
		bl_info_t *bi      = get_block_info(res, irn);
		DBG((res->dbg, LEVEL_1, "lv_chk for %d -> %+F\n", i, irn));
		DBG((res->dbg, LEVEL_1, "\tred reach: %B\n", bi->red_reachable));
		DBG((res->dbg, LEVEL_1, "\ttgt reach: %B\n", bi->be_tgt_reach));
	}
#endif
306
307
308
309

	DBG((res->dbg, LEVEL_1, "back edge src: %B\n", res->back_edge_src));
	DBG((res->dbg, LEVEL_1, "back edge tgt: %B\n", res->back_edge_tgt));

Sebastian Hack's avatar
Sebastian Hack committed
310
	stat_ev_tim_pop("lv_chk_cons_time");
311
312
313
314
315
	return res;
}

void lv_chk_free(lv_chk_t *lv)
{
yb9976's avatar
yb9976 committed
316
	phase_free(&lv->ph);
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
	xfree(lv);
}

/**
 * Check if a node is live at the end of a block.
 * This function is for internal use as its code is shared between
 * the in/end routines below. It is almost the "live_end" routine
 * but passing in the bitset for recording the blocks where the variable
 * is used saves some effort in the "live_in" routine. See below for
 * details.
 *
 * @param lv    The liveness check environment.
 * @param what  The node to check for.
 * @param bl    The block under investigation.
 * @param uses  A bitset where this routine records all ids of blocks
 *              where this variable is used. Note that the bitset
 *              is only guaranteed to be filled if the node was not
 *              live at the end of the block.
 * @return      1, if @p what is live at the end at @p bl.
 */
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
unsigned lv_chk_bl_in_mask(const lv_chk_t *lv, const ir_node *bl, const ir_node *var)
{
	stat_ev_cnt_decl(uses);

	ir_node *def_bl;
	const ir_edge_t *edge;

	int res = 0;

	assert(is_Block(bl) && "can only check for liveness in a block");

	if (!is_liveness_node(var))
		return 0;

	def_bl = get_nodes_block(var);
	if (def_bl == bl || !block_dominates(def_bl, bl)) {
		goto end;
	}

	else {
		bitset_t *uses = bitset_alloca(lv->n_blocks);
		bitset_t *tmp  = bitset_alloca(lv->n_blocks);
		int min_dom    = get_Block_dom_tree_pre_num(def_bl) + 1;
		int max_dom    = get_Block_dom_max_subtree_pre_num(def_bl);
		bl_info_t *bli = get_block_info(lv, bl);
		int i;

		DBG((lv->dbg, LEVEL_2, "lv check of %+F, def=%+F,%d != q=%+F,%d\n",
					var, def_bl, min_dom - 1, bl, bli->id));

		foreach_out_edge (var, edge) {
			ir_node *user = get_edge_src_irn(edge);
			ir_node *use_bl;
			bl_info_t *bi;

			if (!is_liveness_node(user))
				continue;

			stat_ev_cnt_inc(uses);
			use_bl = get_nodes_block(user);
			if (is_Phi(user)) {
				int pos = get_edge_src_pos(edge);
				use_bl  = get_Block_cfgpred_block(use_bl, pos);
			}

			if (use_bl == bl) {
				res = lv_chk_state_in;
				DBG((lv->dbg, LEVEL_2, "\tuse directly in block %+F by %+F\n", use_bl, user));
				goto end;
			}

			bi = get_block_info(lv, use_bl);
			bitset_set(uses, bi->id);
		}

		DBG((lv->dbg, LEVEL_2, "\tuses: %B\n", uses));

		{

			bitset_copy(tmp, bli->be_tgt_reach);
			bitset_set(tmp, bli->id);

			DBG((lv->dbg, LEVEL_2, "\tbe tgt reach: %B, dom span: [%d, %d]\n", tmp, min_dom, max_dom));
			for (i = bitset_next_set(tmp, min_dom); i >= 0 && i <= max_dom; i = bitset_next_set(tmp, i + 1)) {
				bl_info_t *ti = lv->map[i];
				DBG((lv->dbg, LEVEL_2, "\tlooking from %d: seeing %B\n", ti->id, ti->red_reachable));
				if (bitset_intersect(ti->red_reachable, uses)) {
					res = lv_chk_state_in;
					goto end;
				}

				bitset_andnot(tmp, ti->red_reachable);
			}
		}
	}

end:
	return res;
}

unsigned lv_chk_bl_end_mask(const lv_chk_t *lv, const ir_node *bl, const ir_node *var)
{
	stat_ev_cnt_decl(uses);

	ir_node *def_bl;
	const ir_edge_t *edge;

	int res = 0;

	assert(is_Block(bl) && "can only check for liveness in a block");

	if (!is_liveness_node(var))
		return 0;

	def_bl = get_nodes_block(var);
	if (!block_dominates(def_bl, bl)) {
		goto end;
	}

	else {
		bitset_t *uses = bitset_alloca(lv->n_blocks);
		bitset_t *tmp  = bitset_alloca(lv->n_blocks);
		int min_dom    = get_Block_dom_tree_pre_num(def_bl) + 1;
		int max_dom    = get_Block_dom_max_subtree_pre_num(def_bl);
		bl_info_t *bli = get_block_info(lv, bl);
		int i;

		DBG((lv->dbg, LEVEL_2, "lv end check of %+F, def=%+F,%d != q=%+F,%d\n",
					var, def_bl, min_dom - 1, bl, bli->id));

		foreach_out_edge (var, edge) {
			ir_node *user = get_edge_src_irn(edge);
			ir_node *use_bl;
			bl_info_t *bi;

			if (!is_liveness_node(user))
				continue;

			stat_ev_cnt_inc(uses);
			use_bl = get_nodes_block(user);
			if (is_Phi(user)) {
				int pos = get_edge_src_pos(edge);
				use_bl  = get_Block_cfgpred_block(use_bl, pos);

				if (bl == use_bl)
					res |= lv_chk_state_end;
			}

			bi = get_block_info(lv, use_bl);
			if (use_bl != bl || bitset_is_set(lv->back_edge_tgt, bi->id))
				bitset_set(uses, bi->id);
		}

		DBG((lv->dbg, LEVEL_2, "\tuses: %B\n", uses));

		bitset_copy(tmp, bli->be_tgt_reach);
		bitset_set(tmp, bli->id);

		DBG((lv->dbg, LEVEL_2, "\tbe tgt reach + current: %B, dom span: [%d, %d]\n", tmp, min_dom, max_dom));
		for (i = bitset_next_set(tmp, min_dom); i >= 0 && i <= max_dom; i = bitset_next_set(tmp, i + 1)) {
			bl_info_t *ti = lv->map[i];
			DBG((lv->dbg, LEVEL_2, "\tlooking from %d: seeing %B\n", ti->id, ti->red_reachable));
			if (bitset_intersect(ti->red_reachable, uses)) {
				res = lv_chk_state_out | lv_chk_state_end;
				goto end;
			}

			bitset_andnot(tmp, ti->red_reachable);
		}
	}

end:
	return res;
}

/**
 * Check a nodes liveness situation of a block.
 * This routine considers both cases, the live in and end/out case.
 *
 * @param lv   The liveness check environment.
 * @param bl   The block under investigation.
 * @param var  The node to check for.
 * @return     A bitmask of lv_chk_state_XXX fields.
 */
unsigned lv_chk_bl_xxx(const lv_chk_t *lv, const ir_node *bl, const ir_node *var)
502
{
503
504
505
506
	stat_ev_cnt_decl(uses);
	stat_ev_cnt_decl(iter);

	int res  = 0;
507
	ir_node *def_bl;
508
509
510

	assert(is_Block(bl) && "can only check for liveness in a block");

511
512
	/* If the variable ist no liveness related var, bail out. */
	if (!is_liveness_node(var))
513
514
		return 0;

Sebastian Hack's avatar
Sebastian Hack committed
515
516
	stat_ev_ctx_push_fmt("lv_chk", "%u", get_irn_idx(var));
	stat_ev_tim_push();
517

518
519
520
	/* If there is no dominance relation, go out, too */
	def_bl = get_nodes_block(var);
	if (!block_dominates(def_bl, bl)) {
521
522
		stat_ev("lv_chk_no_dom");
		goto end;
523
	}
524
525
526

	/*
	 * If the block in question is the same as the definition block,
527
	 * the algorithm is simple. Just check for uses not inside this block.
528
	 */
529
	if (def_bl == bl) {
530
531
		const ir_edge_t *edge;

532
		stat_ev("lv_chk_def_block");
533
534
		DBG((lv->dbg, LEVEL_2, "lv check same block %+F in %+F\n", var, bl));
		foreach_out_edge (var, edge) {
535
536
537
538
539
540
			ir_node *use    = get_edge_src_irn(edge);
			ir_node *use_bl;

			if (!is_liveness_node(use))
				continue;

541
			stat_ev_cnt_inc(uses);
542
543
544
545
546
			use_bl = get_nodes_block(use);
			if (is_Phi(use)) {
				int pos = get_edge_src_pos(edge);
				use_bl  = get_Block_cfgpred_block(use_bl, pos);

547
				if (use_bl == bl) {
548
					DBG((lv->dbg, LEVEL_2, "\tphi %+F in succ %+F,%d -> live end\n", use, use_bl, pos));
549
					res |= lv_chk_state_end;
550
551
552
				}
			}

553
			if (use_bl != def_bl) {
554
555
556
				res = lv_chk_state_end | lv_chk_state_out;
				goto end;
			}
557
558
		}

559
		goto end;
560
561
	}

562
563
564
565
566
567
568
569
	/*
	 * this is the more complicated case.
	 * We try to gather as much information as possible during looking
	 * at the uses.
	 *
	 * Note that we know for shure that bl != def_bl. That is sometimes
	 * silently exploited below.
	 */
570
	else {
571
572
		bl_info_t *def = get_block_info(lv, def_bl);
		bl_info_t *bli = get_block_info(lv, bl);
Sebastian Hack's avatar
Sebastian Hack committed
573
574
		bitset_t *uses = bitset_alloca(lv->n_blocks);
		bitset_t *Tq;
575

Sebastian Hack's avatar
Sebastian Hack committed
576
		unsigned i, min_dom, max_dom;
577
578
		const ir_edge_t *edge;

579
580
581
582
583
584
585
586
587
		/* if the block has no DFS info, it cannot be reached.
		 * This can happen in functions with endless loops.
		 * we then go out, since nothing is live there.
		 *
		 * TODO: Is that right?
		 */
		if (!bli)
			goto end;

Sebastian Hack's avatar
Sebastian Hack committed
588
		(void) def;
589
590
591
592
593
594
595
		DBG((lv->dbg, LEVEL_2, "lv check %+F (def in %+F #%d) in different block %+F #%d\n",
					var, def_bl, def->id, bl, bli->id));

		foreach_out_edge (var, edge) {
			ir_node *user = get_edge_src_irn(edge);
			int mask      = lv_chk_state_in;

596
			ir_node *use_bl;
597
			bl_info_t *bi;
598

599
			/* if the user is no liveness node, the use does not count */
600
601
602
			if (!is_liveness_node(user))
				continue;

603
			stat_ev_cnt_inc(uses);
604
605
606
607
608

			/* if the user is a phi, the use is in the predecessor
			 * furthermore, prepare a mask so that in the case where
			 * bl (the block in question) coincides with a use, it
			 * can be marked live_end there. */
609
610
			use_bl = get_nodes_block(user);
			if (is_Phi(user)) {
611
612
613
614
				int pos = get_edge_src_pos(edge);
				use_bl  = get_Block_cfgpred_block(use_bl, pos);
				mask   |= lv_chk_state_end;
			}
615

616

617
618
619
620
621
622
			/* if the use block coincides with the query block, we
			 * already gather a little liveness information.
			 * The variable is surely live there, since bl != def_bl
			 * (that case is treated above). */
			if (use_bl == bl)
				res |= mask;
623

624
			bi = get_block_info(lv, use_bl);
625

626
627
			if (bi)
				bitset_set(uses, bi->id);
628
629
		}

630
631
632
633
634
635
636
637
638
639
640
		/* get the dominance range which really matters. all uses outside
		 * the definition's dominance range are not to consider. note,
		 * that the definition itself is also not considered. The case
		 * where bl == def_bl is considered above. */
		min_dom = get_Block_dom_tree_pre_num(def_bl) + 1;
		max_dom = get_Block_dom_max_subtree_pre_num(def_bl);

		DBG((lv->dbg, LEVEL_2, "\tuses: %B\n", uses));

		/* prepare a set with all reachable back edge targets.
		 * this will determine our "looking points" from where
Sebastian Hack's avatar
Sebastian Hack committed
641
642
		 * we will search/find the calculated uses. */
		Tq = bli->be_tgt_reach;
643
644
645
646
647

		/* now, visit all viewing points in the temporary bitset lying
		 * in the dominance range of the variable. Note that for reducible
		 * flow-graphs the first iteration is sufficient and the loop
		 * will be left. */
Sebastian Hack's avatar
Sebastian Hack committed
648
649
650
		DBG((lv->dbg, LEVEL_2, "\tbe tgt reach: %B, dom span: [%d, %d]\n", Tq, min_dom, max_dom));
		i = bitset_next_set(Tq, min_dom);
		while(i <= max_dom) {
651
652
			bl_info_t *ti = lv->map[i];
			int use_in_current_block = bitset_is_set(uses, ti->id);
653

Sebastian Hack's avatar
Sebastian Hack committed
654
655
			stat_ev_cnt_inc(iter);

656
			/*
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
			 * This is somehat tricky. Since this routine handles both, live in
			 * and end/out we have to handle all the border cases correctly.
			 * Each node is in its own red_reachable set (see calculation
			 * function above). That means, that in the case where bl == t, the
			 * intersection check of uses and rechability below will always
			 * find an intersection, namely t.
			 *
			 * However, if a block contains a use and the variable is dead
			 * afterwards, it is not live end/out at that block. Besides
			 * back-edge target. If a var is live-in at a back-edge target it
			 * is also live out/end there since the variable is live in the
			 * underlying loop. So in the case where t == bl and that is not
			 * a back-edge target, we have to remove that use from consideration
			 * to determine if the var is live out/end there.
			 *
			 * Note that the live in information has been calculated by the
			 * uses iteration above.
674
			 */
675
676
677
678
679
680
681
682
683
			if (ti == bli && !bitset_is_set(lv->back_edge_tgt, ti->id)) {
				DBG((lv->dbg, LEVEL_2, "\tlooking not from a back edge target and q == t. removing use: %d\n", ti->id));
				bitset_clear(uses, ti->id);
			}

			/* If we can reach a use, the variable is live there and we say goodbye */
			DBG((lv->dbg, LEVEL_2, "\tlooking from %d: seeing %B\n", ti->id, ti->red_reachable));
			if (bitset_intersect(ti->red_reachable, uses)) {
				res |= lv_chk_state_in | lv_chk_state_out | lv_chk_state_end;
684
685
				goto end;
			}
686
687

			/*
688
689
690
			 * if we deleted a use do to the commentary above, we have to
			 * re-add it since it might be visible from further view points
			 * (we only need that in the non-reducible case).
691
			 */
692
693
			if (use_in_current_block)
				bitset_set(uses, ti->id);
Sebastian Hack's avatar
Sebastian Hack committed
694
695

			i = bitset_next_set(Tq, get_Block_dom_max_subtree_pre_num(ti->block) + 1);
696
		}
697
698
699

	}

700
end:
Sebastian Hack's avatar
Sebastian Hack committed
701
	stat_ev_tim_pop("lv_chk_query_time");
702
703
	stat_ev_cnt_done(uses, "lv_chk_uses");
	stat_ev_cnt_done(iter, "lv_chk_iter");
Sebastian Hack's avatar
Sebastian Hack committed
704
	stat_ev_ctx_pop("lv_chk");
705
706

	return res;
707
}