irlivechk.c 19.9 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$
yb9976's avatar
yb9976 committed
25
 * @brief
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
#include <config.h>
41
42
43
44

#include <stdio.h>

#include "irgraph_t.h"
45
#include "irnode_t.h"
46
47
#include "irphase_t.h"
#include "iredges_t.h"
48

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

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

#include "irlivechk.h"

59
#include "statev.h"
60

61
typedef struct _bl_info_t {
62
	const ir_node *block;      /**< The block. */
63

64
65
	int be_tgt_calc : 1;
	int id : 31;               /**< a tight number for the block.
66
67
68
69
70
71
72
73
74
75
76
77
78
								 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 {
79
	ir_phase     ph;
Sebastian Hack's avatar
Sebastian Hack committed
80
	const dfs_t *dfs;
81
82
83
84
	int          n_blocks;
	bitset_t    *back_edge_src;
	bitset_t    *back_edge_tgt;
	bl_info_t  **map;
Michael Beck's avatar
Michael Beck committed
85
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
86
87
};

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

93
	bi->id            = get_Block_dom_tree_pre_num(irn);
94
95
96
	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);
97
	bi->be_tgt_calc   = 0;
Matthias Braun's avatar
Matthias Braun committed
98
	(void) old;
99
100
101
102
103
104
105
106
	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.
 */
107
static inline int is_liveness_node(const ir_node *irn)
108
{
Michael Beck's avatar
Michael Beck committed
109
	switch (get_irn_opcode(irn)) {
110
111
112
	case iro_Block:
	case iro_Bad:
	case iro_End:
113
	case iro_Anchor:
114
		return 0;
115
116
	default:
		break;
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
	}

	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
136
		const ir_node *bl   = dfs_get_post_num_node(lv->dfs, i);
137
138
139
140
		bl_info_t *bi = get_block_info(lv, bl);

		const ir_edge_t *edge;

141
		bitset_set(bi->red_reachable, bi->id);
142
143
144
145
146
147
148
149
150
151
		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) {
152
				assert(dfs_get_post_num(lv->dfs, bl) > dfs_get_post_num(lv->dfs, succ));
153
154
155
156
157
158
159
160
161
162
163
164
165
166
				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);
			}
		}

	}

}

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

172
	unsigned elm;
173

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

176
	/* put all back edge sources reachable (reduced) from here in tmp */
177
178
179
	bitset_copy(tmp, bi->red_reachable);
	bitset_set(tmp, bi->id);
	bitset_and(tmp, lv->back_edge_src);
180
181
182
183
184
185
186
	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];
187
188
		const ir_edge_t *edge;

189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
		/* 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);
	}
}

206

207
static inline void compute_back_edge_chains(lv_chk_t *lv)
208
{
209
	unsigned elm;
210
211
212
213
214
215
216
217
	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
218
219
		const ir_node *bl = dfs_get_post_num_node(lv->dfs, i);
		bl_info_t *bi     = get_block_info(lv, bl);
220
221
222
223
224
225

		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);
226
				bl_info_t *si = get_block_info(lv, succ);
227
228
229
230
231
232
				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);
				}
233
234
235
			}
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
236
237
238
239
240
241

	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);
	}
242
243
}

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

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

Sebastian Hack's avatar
Sebastian Hack committed
254
	stat_ev_tim_push();
255
	phase_init(&res->ph, irg, init_block_data);
256
257
258
259
	obst = phase_obst(&res->ph);

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

Sebastian Hack's avatar
Sebastian Hack committed
260
	res->dfs           = dfs;
261
262
263
	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);
264
	res->map           = OALLOCNZ(obst, bl_info_t*, res->n_blocks);
265

266
#if 0
267
268
269
270
271
272
273
274
275
276
277
278
279
280
	{
		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
281
282
		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);
283
284
		assert(bi->id < res->n_blocks);
		assert(res->map[bi->id] == NULL);
285
		res->map[bi->id] = bi;
286
287
288
289
290
	}

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

291
292
	/* compute back edge chains */
	compute_back_edge_chains(res);
293

Sebastian Hack's avatar
Sebastian Hack committed
294
295
296
297
298
299
300
301
302
303
#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
304
305
306
307

	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
308
	stat_ev_tim_pop("lv_chk_cons_time");
309
310
311
312
313
	return res;
}

void lv_chk_free(lv_chk_t *lv)
{
314
	phase_deinit(&lv->ph);
315
316
317
	xfree(lv);
}

318
#if 0
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
/**
 * 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.
 */
336
337
338
339
340
unsigned lv_chk_bl_in_mask(const lv_chk_t *lv, const ir_node *bl, const ir_node *var)
{
	ir_node *def_bl;
	const ir_edge_t *edge;

Michael Beck's avatar
Michael Beck committed
341
342
	stat_ev_cnt_decl(uses);

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
	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)
{
	ir_node *def_bl;
	const ir_edge_t *edge;

Michael Beck's avatar
Michael Beck committed
421
422
	stat_ev_cnt_decl(uses);

423
424
425
426
427
428
429
430
431
432
	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;
Michael Beck's avatar
Michael Beck committed
433
	} else {
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
		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;
}
488
#endif
489
490
491
492
493
494
495
496
497
498
499

/**
 * 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)
500
{
501
	int res  = 0;
502
	ir_node *def_bl;
Michael Beck's avatar
Michael Beck committed
503
504
	stat_ev_cnt_decl(uses);
	stat_ev_cnt_decl(iter);
505
506
507

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

508
509
	/* If the variable ist no liveness related var, bail out. */
	if (!is_liveness_node(var))
510
511
		return 0;

Sebastian Hack's avatar
Sebastian Hack committed
512
513
	stat_ev_ctx_push_fmt("lv_chk", "%u", get_irn_idx(var));
	stat_ev_tim_push();
514

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

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

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

			if (!is_liveness_node(use))
				continue;

538
			stat_ev_cnt_inc(uses);
539
540
541
542
543
			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);

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

550
			if (use_bl != def_bl) {
551
552
553
				res = lv_chk_state_end | lv_chk_state_out;
				goto end;
			}
554
555
		}

556
		goto end;
557
558
	}

559
560
561
562
563
	/*
	 * this is the more complicated case.
	 * We try to gather as much information as possible during looking
	 * at the uses.
	 *
Michael Beck's avatar
Michael Beck committed
564
	 * Note that we know for sure that bl != def_bl. That is sometimes
565
566
	 * silently exploited below.
	 */
567
	else {
568
569
		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
570
571
		bitset_t *uses = bitset_alloca(lv->n_blocks);
		bitset_t *Tq;
572

Sebastian Hack's avatar
Sebastian Hack committed
573
		unsigned i, min_dom, max_dom;
574
575
		const ir_edge_t *edge;

576
577
578
579
580
581
582
583
584
		/* 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
585
		(void) def;
586
587
588
589
590
591
592
		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;

593
			ir_node *use_bl;
594
			bl_info_t *bi;
595

596
			/* if the user is no liveness node, the use does not count */
597
598
599
			if (!is_liveness_node(user))
				continue;

600
			stat_ev_cnt_inc(uses);
601
602
603
604
605

			/* 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. */
606
607
			use_bl = get_nodes_block(user);
			if (is_Phi(user)) {
608
609
610
611
				int pos = get_edge_src_pos(edge);
				use_bl  = get_Block_cfgpred_block(use_bl, pos);
				mask   |= lv_chk_state_end;
			}
612

613

614
615
616
617
618
619
			/* 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;
620

621
			bi = get_block_info(lv, use_bl);
622

623
624
			if (bi)
				bitset_set(uses, bi->id);
625
626
		}

627
628
629
630
631
632
633
634
635
636
637
		/* 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
638
639
		 * we will search/find the calculated uses. */
		Tq = bli->be_tgt_reach;
640
641
642
643
644

		/* 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
645
646
		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);
647
		while (i <= max_dom) {
648
649
			bl_info_t *ti = lv->map[i];
			int use_in_current_block = bitset_is_set(uses, ti->id);
650

Sebastian Hack's avatar
Sebastian Hack committed
651
652
			stat_ev_cnt_inc(iter);

653
			/*
Michael Beck's avatar
Michael Beck committed
654
			 * This is somewhat tricky. Since this routine handles both, live in
655
656
657
			 * 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
Michael Beck's avatar
Michael Beck committed
658
			 * intersection check of uses and reachability below will always
659
660
661
662
663
664
665
666
667
668
669
670
			 * 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.
671
			 */
672
673
674
675
676
677
678
679
680
			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;
681
682
				goto end;
			}
683
684

			/*
685
686
687
			 * 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).
688
			 */
689
690
			if (use_in_current_block)
				bitset_set(uses, ti->id);
Sebastian Hack's avatar
Sebastian Hack committed
691
692

			i = bitset_next_set(Tq, get_Block_dom_max_subtree_pre_num(ti->block) + 1);
693
		}
694
695
696

	}

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

	return res;
704
}