beverify.c 26.6 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig 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.
 */

Christian Würdig's avatar
Christian Würdig committed
20
21
22
23
24
25
/**
 * @file
 * @brief       Various verify routines that check a scheduled graph for correctness.
 * @author      Matthias Braun
 * @date        05.05.2006
 * @version     $Id$
26
 */
27
#include "config.h"
28

29
30
#include <limits.h>

31
32
33
#include "bitset.h"
#include "set.h"
#include "array.h"
34
35
36
37
38
39

#include "irnode.h"
#include "irgraph.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "irdump_t.h"
40
#include "iredges.h"
41
42
43

#include "beverify.h"
#include "belive.h"
44
#include "besched.h"
45
#include "benode.h"
46
#include "beirg.h"
47
#include "beintlive_t.h"
48

49
50
static int my_values_interfere(const ir_node *a, const ir_node *b);

51
typedef struct be_verify_register_pressure_env_t_ {
Christian Würdig's avatar
Christian Würdig committed
52
	ir_graph                    *irg;                 /**< the irg to verify */
Sebastian Hack's avatar
Sebastian Hack committed
53
	 be_lv_t                    *lv;                  /**< Liveness information. */
Christian Würdig's avatar
Christian Würdig committed
54
55
56
	const arch_register_class_t *cls;                 /**< the register class to check for */
	int                         registers_available;  /**< number of available registers */
	int                         problem_found;        /**< flag indicating if a problem was found */
57
58
} be_verify_register_pressure_env_t;

Christian Würdig's avatar
Christian Würdig committed
59
60
61
/**
 * Print all nodes of a pset into a file.
 */
62
63
static void print_living_values(FILE *F, const ir_nodeset_t *live_nodes)
{
64
	ir_nodeset_iterator_t iter;
65
66
	ir_node *node;

Christian Würdig's avatar
Christian Würdig committed
67
	ir_fprintf(F, "\t");
68
	foreach_ir_nodeset(live_nodes, node, iter) {
Christian Würdig's avatar
Christian Würdig committed
69
		ir_fprintf(F, "%+F ", node);
70
	}
Christian Würdig's avatar
Christian Würdig committed
71
	ir_fprintf(F, "\n");
72
73
}

Christian Würdig's avatar
Christian Würdig committed
74
75
76
/**
 * Check if number of live nodes never exceeds the number of available registers.
 */
77
78
static void verify_liveness_walker(ir_node *block, void *data)
{
Christian Würdig's avatar
Christian Würdig committed
79
	be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data;
80
	ir_nodeset_t live_nodes;
81
	ir_node *irn;
82
	int pressure;
83

Christian Würdig's avatar
Christian Würdig committed
84
	/* collect register pressure info, start with end of a block */
Sebastian Hack's avatar
Sebastian Hack committed
85
	// ir_fprintf(stderr, "liveness check %+F\n", block);
86
	ir_nodeset_init(&live_nodes);
87
	be_liveness_end_of_block(env->lv, env->cls, block,
88
	                         &live_nodes);
Christian Würdig's avatar
Christian Würdig committed
89

Sebastian Hack's avatar
Sebastian Hack committed
90
	// print_living_values(stderr, &live_nodes);
91
	pressure = ir_nodeset_size(&live_nodes);
92
93
94
	if(pressure > env->registers_available) {
		ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n",
			block, get_irg_dump_name(env->irg), pressure, env->registers_available);
95
		print_living_values(stderr, &live_nodes);
96
97
		env->problem_found = 1;
	}
98

99
	sched_foreach_reverse(block, irn) {
Christian Würdig's avatar
Christian Würdig committed
100
		if (is_Phi(irn))
101
102
			break;

Sebastian Hack's avatar
Sebastian Hack committed
103
		// print_living_values(stderr, &live_nodes);
104
		be_liveness_transfer(env->cls, irn, &live_nodes);
105

106
		pressure = ir_nodeset_size(&live_nodes);
107

108
		if(pressure > env->registers_available) {
109
110
			ir_fprintf(stderr, "Verify Warning: Register pressure too high before node %+F in %+F(%s) (%d/%d):\n",
				irn, block, get_irg_dump_name(env->irg), pressure, env->registers_available);
111
			print_living_values(stderr, &live_nodes);
112
			env->problem_found = 1;
Sebastian Hack's avatar
Sebastian Hack committed
113
			assert(0);
114
115
		}
	}
116
	ir_nodeset_destroy(&live_nodes);
117
118
}

Christian Würdig's avatar
Christian Würdig committed
119
120
121
/**
 * Start a walk over the irg and check the register pressure.
 */
122
123
124
int be_verify_register_pressure(const be_irg_t *birg,
                                const arch_register_class_t *cls,
                                ir_graph *irg) {
125
126
	be_verify_register_pressure_env_t env;

127
	env.lv                  = be_liveness(irg);
Christian Würdig's avatar
Christian Würdig committed
128
129
	env.irg                 = irg;
	env.cls                 = cls;
Sebastian Hack's avatar
Sebastian Hack committed
130
	env.registers_available = env.cls->n_regs - be_put_ignore_regs(birg, env.cls, NULL);
Christian Würdig's avatar
Christian Würdig committed
131
	env.problem_found       = 0;
132

Sebastian Hack's avatar
Sebastian Hack committed
133
	be_liveness_assure_sets(env.lv);
Christian Würdig's avatar
Christian Würdig committed
134
	irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env);
Sebastian Hack's avatar
Sebastian Hack committed
135
	be_liveness_free(env.lv);
Christian Würdig's avatar
Christian Würdig committed
136
137

	return ! env.problem_found;
138
139
}

140
141


142
/*--------------------------------------------------------------------------- */
143
144
145



146
typedef struct be_verify_schedule_env_t_ {
147
148
149
	int      problem_found;     /**< flags indicating if there was a problem */
	bitset_t *scheduled;        /**< bitset of scheduled nodes */
	ir_graph *irg;              /**< the irg to check */
150
151
} be_verify_schedule_env_t;

Christian Würdig's avatar
Christian Würdig committed
152
153
154
/**
 * Simple schedule checker.
 */
155
156
static void verify_schedule_walker(ir_node *block, void *data)
{
157
	be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data;
158
	ir_node *node;
Matthias Braun's avatar
Matthias Braun committed
159
	ir_node *non_phi_found = NULL;
160
	int cfchange_found = 0;
161
	/* TODO ask arch about delay branches */
162
	int delay_branches = 0;
163
	int last_timestep = INT_MIN;
164
165

	/*
166
167
168
169
	 * Tests for the following things:
	 *   1. Make sure that all phi nodes are scheduled at the beginning of the block
	 *   2. There is 1 or no control flow changing node scheduled and exactly delay_branches operations after it.
	 *   3. No value is defined after it has been used
170
171
	 *   4. mode_T nodes have all projs scheduled behind them followed by Keeps
	 *       (except mode_X projs)
172
	 */
173
174
	sched_foreach(block, node) {
		int i, arity;
175
176
		int timestep;

177
		/* this node is scheduled */
178
179
180
181
182
183
		if(bitset_is_set(env->scheduled, get_irn_idx(node))) {
			ir_fprintf(stderr, "Verify warning: %+F appears to be schedule twice\n");
			env->problem_found = 1;
		}
		bitset_set(env->scheduled, get_irn_idx(node));

184
		/* Check that scheduled nodes are in the correct block */
185
186
187
188
189
		if(get_nodes_block(node) != block) {
			ir_fprintf(stderr, "Verify warning: %+F is in block %+F but scheduled in %+F\n", node, get_nodes_block(node), block);
			env->problem_found = 1;
		}

190
		/* Check that timesteps are increasing */
191
192
193
194
195
196
197
		timestep = sched_get_time_step(node);
		if(timestep <= last_timestep) {
			ir_fprintf(stderr, "Verify warning: Schedule timestep did not increase at node %+F\n",
			           node);
			env->problem_found = 1;
		}
		last_timestep = timestep;
198

199
		/* Check that phis come before any other node */
200
		if (is_Phi(node)) {
Matthias Braun's avatar
Matthias Braun committed
201
202
203
			if (non_phi_found != NULL) {
				ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes (for example %+F) in block %+F (%s)\n",
					node, non_phi_found, block, get_irg_dump_name(env->irg));
204
205
				env->problem_found = 1;
			}
Matthias Braun's avatar
Matthias Braun committed
206
		} else {
Matthias Braun's avatar
Matthias Braun committed
207
			non_phi_found = node;
208
		}
209

210
		/* Check for control flow changing nodes */
211
		if (is_cfop(node) && get_irn_opcode(node) != iro_Start) {
Christian Würdig's avatar
Christian Würdig committed
212
213
214
			/* check, that only one CF operation is scheduled */
			if (cfchange_found == 1) {
				ir_fprintf(stderr, "Verify Warning: More than 1 control flow changing node (%+F) scheduled in block %+F (%s)\n",
215
					node, block, get_irg_dump_name(env->irg));
216
217
218
				env->problem_found = 1;
			}
			cfchange_found = 1;
Christian Würdig's avatar
Christian Würdig committed
219
		} else if (cfchange_found) {
220
			/* proj and keepany aren't real instructions... */
221
222
223
224
225
226
227
228
229
			if(!is_Proj(node) && !be_is_Keep(node)) {
				/* check for delay branches */
				if (delay_branches == 0) {
					ir_fprintf(stderr, "Verify Warning: Node %+F scheduled after control flow changing node (+delay branches) in block %+F (%s)\n",
						node, block, get_irg_dump_name(env->irg));
					env->problem_found = 1;
				} else {
					delay_branches--;
				}
230
231
			}
		}
232

233
		/* Check that all uses come before their definitions */
234
		if(!is_Phi(node)) {
235
			int nodetime = sched_get_time_step(node);
236
			for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
237
238
239
240
241
242
243
244
245
246
				ir_node *arg = get_irn_n(node, i);
				if(get_nodes_block(arg) != block
				   || !sched_is_scheduled(arg))
					continue;

				if(sched_get_time_step(arg) >= nodetime) {
					ir_fprintf(stderr, "Verify Warning: Value %+F used by %+F before it was defined in block %+F (%s)\n",
					           arg, node, block, get_irg_dump_name(env->irg));
					env->problem_found = 1;
				}
247
			}
248
		}
249

250
		/* Check that no dead nodes are scheduled */
251
252
253
254
255
		if(get_irn_n_edges(node) == 0) {
			ir_fprintf(stderr, "Verify warning: Node %+F is dead but scheduled in block %+F (%s)\n",
			           node, block, get_irg_dump_name(env->irg));
			env->problem_found = 1;
		}
256

257
		if(be_is_Keep(node) || be_is_CopyKeep(node)) {
258
259
260
261
262
			/* at least 1 of the keep arguments has to be it schedule
			 * predecessor */
			int      arity   = get_irn_arity(node);
			int      problem = 1;
			ir_node *prev    = sched_prev(node);
263
			while(be_is_Keep(prev) || be_is_CopyKeep(prev))
264
265
				prev = sched_prev(prev);

Matthias Braun's avatar
Matthias Braun committed
266
267
			for(i = 0; i < arity; ++i) {
				ir_node *in = get_irn_n(node, i);
268
269
270
				in = skip_Proj(in);
				if(in == prev)
					problem = 0;
271
			}
Matthias Braun's avatar
Matthias Braun committed
272
			if(problem) {
Matthias Braun's avatar
Matthias Braun committed
273
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
274
275
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
276
277
			}
		}
278
279
	}

280
	/* check that all delay branches are filled (at least with NOPs) */
Christian Würdig's avatar
Christian Würdig committed
281
	if (cfchange_found && delay_branches != 0) {
282
		ir_fprintf(stderr, "Verify warning: Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
283
			block, get_irg_dump_name(env->irg));
284
285
286
		env->problem_found = 1;
	}
}
287

288
289
static int should_be_scheduled(ir_node *node)
{
290
	switch(get_irn_opcode(node)) {
291
292
	case iro_Bad:
	case iro_Block:
293
294
	case iro_End:
	case iro_NoMem:
295
296
297
	case iro_Pin:
	case iro_Proj:
	case iro_Sync:
298
	case iro_Unknown:
299
		return 0;
300
301
302
303
	case iro_Phi:
		if (get_irn_mode(node) == mode_M)
			return 0;
		break;
304
305
	case iro_Start:
	case iro_Jmp:
306
307
	case beo_Return:
		return 1;
308
309
310
311
	default:
		break;
	}

312
313
314
315
	if (get_irn_mode(node) != mode_T) {
		if (arch_irn_is_ignore(node))
			return -1;
	}
316

317
318
319
	return 1;
}

320
321
static void check_schedule(ir_node *node, void *data)
{
322
323
	be_verify_schedule_env_t *env = data;
	int should_be;
324
	int scheduled;
325

326
	should_be = should_be_scheduled(node);
327
328
	if(should_be == -1)
		return;
329

330
331
332
	scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0;
	should_be = should_be ? 1 : 0;
	if(should_be != scheduled) {
333
		ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n",
334
			node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not");
335
336
337
338
		env->problem_found = 1;
	}
}

Christian Würdig's avatar
Christian Würdig committed
339
340
341
/**
 * Start a walk over the irg and check schedule.
 */
342
int be_verify_schedule(const be_irg_t *birg)
343
344
345
346
{
	be_verify_schedule_env_t env;

	env.problem_found = 0;
347
348
	env.irg           = be_get_birg_irg(birg);
	env.scheduled     = bitset_alloca(get_irg_last_idx(env.irg));
349

350
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
351
	/* check if all nodes are scheduled */
352
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
353

Christian Würdig's avatar
Christian Würdig committed
354
	return ! env.problem_found;
355
}
356

357
358


359
/*--------------------------------------------------------------------------- */
360
361


362
363
364

typedef struct _spill_t {
	ir_node *spill;
365
	ir_entity *ent;
366
367
368
} spill_t;

typedef struct {
369
370
371
372
	ir_graph  *irg;
	set       *spills;
	ir_node  **reloads;
	int        problem_found;
373
374
} be_verify_spillslots_env_t;

375
376
static int cmp_spill(const void* d1, const void* d2, size_t size)
{
377
378
	const spill_t* s1 = d1;
	const spill_t* s2 = d2;
379
380
	(void) size;

381
382
383
	return s1->spill != s2->spill;
}

384
385
static spill_t *find_spill(be_verify_spillslots_env_t *env, ir_node *node)
{
386
387
388
389
390
391
	spill_t spill;

	spill.spill = node;
	return set_find(env->spills, &spill, sizeof(spill), HASH_PTR(node));
}

392
393
static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent)
{
394
395
396
397
398
399
400
401
402
403
404
405
406
407
	spill_t spill, *res;
	int hash = HASH_PTR(node);

	spill.spill = node;
	res = set_find(env->spills, &spill, sizeof(spill), hash);

	if(res == NULL) {
		spill.ent = ent;
		res = set_insert(env->spills, &spill, sizeof(spill), hash);
	}

	return res;
}

408
409
static ir_node *get_memory_edge(const ir_node *node)
{
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
	int i, arity;
	ir_node *result = NULL;

	arity = get_irn_arity(node);
	for(i = arity - 1; i >= 0; --i) {
		ir_node *arg = get_irn_n(node, i);
		if(get_irn_mode(arg) == mode_M) {
			assert(result == NULL);
			result = arg;
		}
	}

	return result;
}

425
426
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
427

428
static
429
430
void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent)
{
431
432
433
434
435
436
	if(ent == NULL) {
		ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have an entity assigned\n",
		           node, get_nodes_block(node), get_irg_dump_name(env->irg));
	}
}

437
static
438
439
void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent)
{
440
	ir_entity *spillent = arch_get_frame_entity(node);
441
	be_check_entity(env, node, spillent);
442
443
444
445
446
447
448
449
450
	get_spill(env, node, ent);

	if(spillent != ent) {
		ir_fprintf(stderr, "Verify warning: Spill %+F has different entity than reload %+F in block %+F(%s)\n",
			node, reload, get_nodes_block(node), get_irg_dump_name(env->irg));
		env->problem_found = 1;
	}
}

451
452
static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent)
{
453
454
455
456
457
	int i, arity;
	spill_t spill, *res;
	int hash = HASH_PTR(node);
	int out;
	ir_node* memperm;
458
	ir_entity *spillent;
459
460
461
462
463
464
465

	assert(is_Proj(node));

	memperm = get_Proj_pred(node);
	out = get_Proj_proj(node);

	spillent = be_get_MemPerm_out_entity(memperm, out);
466
	be_check_entity(env, memperm, spillent);
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
	if(spillent != ent) {
		ir_fprintf(stderr, "Verify warning: MemPerm %+F has different entity than reload %+F in block %+F(%s)\n",
			node, reload, get_nodes_block(node), get_irg_dump_name(env->irg));
		env->problem_found = 1;
	}

	spill.spill = node;
	res = set_find(env->spills, &spill, sizeof(spill), hash);
	if(res != NULL) {
		return;
	}

	spill.ent = spillent;
	res = set_insert(env->spills, &spill, sizeof(spill), hash);

482
483
	for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) {
		ir_node* arg = get_irn_n(memperm, i + 1);
484
		ir_entity* argent = be_get_MemPerm_in_entity(memperm, i);
485
486
487
488
489

		collect(env, arg, memperm, argent);
	}
}

490
491
static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent)
{
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
	int i, arity;
	spill_t spill, *res;
	int hash = HASH_PTR(node);

	assert(is_Phi(node));

	spill.spill = node;
	res = set_find(env->spills, &spill, sizeof(spill), hash);
	if(res != NULL) {
		return;
	}

	spill.ent = ent;
	res = set_insert(env->spills, &spill, sizeof(spill), hash);

507
	/* is 1 of the arguments a spill? */
508
509
510
511
512
513
	for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
		ir_node* arg = get_irn_n(node, i);
		collect(env, arg, reload, ent);
	}
}

514
515
static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent)
{
516
517
518
519
520
521
522
	if(be_is_Spill(node)) {
		collect_spill(env, node, reload, ent);
	} else if(is_Proj(node)) {
		collect_memperm(env, node, reload, ent);
	} else if(is_Phi(node) && get_irn_mode(node) == mode_M) {
		collect_memphi(env, node, reload, ent);
	} else {
523
		/* Disabled for now, spills might get transformed by the backend */
524
#if 0
525
526
527
		ir_fprintf(stderr, "Verify warning: No spill, memperm or memphi attached to node %+F found from node %+F in block %+F(%s)\n",
			node, reload, get_nodes_block(node), get_irg_dump_name(env->irg));
		env->problem_found = 1;
528
#endif
529
530
531
532
533
534
535
	}
}

/**
 * This walker function searches for reloads and collects all the spills
 * and memphis attached to them.
 */
536
537
static void collect_spills_walker(ir_node *node, void *data)
{
538
539
	be_verify_spillslots_env_t *env = data;

540
	/* @@@ ia32_classify returns classification of Proj_pred :-/ */
541
542
543
	if(is_Proj(node))
		return;

544
	if (arch_irn_class_is(node, reload)) {
545
		ir_node *spill = get_memory_edge(node);
546
		ir_entity *ent;
Matthias Braun's avatar
Matthias Braun committed
547

548
549
550
551
552
553
		if(spill == NULL) {
			ir_fprintf(stderr, "Verify warning: No spill attached to reload %+F in block %+F(%s)\n",
			           node, get_nodes_block(node), get_irg_dump_name(env->irg));
			env->problem_found = 1;
			return;
		}
554
		ent = arch_get_frame_entity(node);
555
		be_check_entity(env, node, ent);
556
557
558
559
560
561

		collect(env, spill, node, ent);
		ARR_APP1(ir_node*, env->reloads, node);
	}
}

562
563
564
565
566
567
static void check_spillslot_interference(be_verify_spillslots_env_t *env)
{
	int       spillcount = set_count(env->spills);
	spill_t **spills     = ALLOCAN(spill_t*, spillcount);
	spill_t  *spill;
	int       i;
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582

	for(spill = set_first(env->spills), i = 0; spill != NULL; spill = set_next(env->spills), ++i) {
		spills[i] = spill;
	}

	for(i = 0; i < spillcount; ++i) {
		spill_t *sp1 = spills[i];
		int i2;

		for(i2 = i+1; i2 < spillcount; ++i2) {
			spill_t *sp2 = spills[i2];

			if(sp1->ent != sp2->ent)
				continue;

583
			if(my_values_interfere(sp1->spill, sp2->spill)) {
584
585
586
587
				ir_fprintf(stderr, "Verify warning: Spillslots for %+F in block %+F(%s) and %+F in block %+F(%s) interfere\n",
					sp1->spill, get_nodes_block(sp1->spill), get_irg_dump_name(env->irg),
					sp2->spill, get_nodes_block(sp2->spill), get_irg_dump_name(env->irg));
				env->problem_found = 1;
588
				my_values_interfere(sp1->spill, sp2->spill);
589
590
591
592
593
			}
		}
	}
}

594
595
static void check_lonely_spills(ir_node *node, void *data)
{
596
597
598
599
600
	be_verify_spillslots_env_t *env = data;

	if(be_is_Spill(node) || (is_Proj(node) && be_is_MemPerm(get_Proj_pred(node)))) {
		spill_t *spill = find_spill(env, node);
		if(be_is_Spill(node)) {
601
			ir_entity *ent = arch_get_frame_entity(node);
602
			be_check_entity(env, node, ent);
603
604
605
606
607
608
609
610
611
		}

		if(spill == NULL) {
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) not connected to a reaload\n",
			           node, get_nodes_block(node), get_irg_dump_name(env->irg));
		}
	}
}

612
int be_verify_spillslots(ir_graph *irg)
613
614
615
616
617
618
619
620
621
{
	be_verify_spillslots_env_t env;

	env.irg = irg;
	env.spills = new_set(cmp_spill, 10);
	env.reloads = NEW_ARR_F(ir_node*, 0);
	env.problem_found = 0;

	irg_walk_graph(irg, collect_spills_walker, NULL, &env);
622
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
623
624
625
626
627
628
629
630
631

	check_spillslot_interference(&env);

	DEL_ARR_F(env.reloads);
	del_set(env.spills);

	return ! env.problem_found;
}

632
633


634
/*--------------------------------------------------------------------------- */
635
636
637
638
639
640
641
642



/**
 * Check, if two values interfere.
 * @param a The first value.
 * @param b The second value.
 * @return 1, if a and b interfere, 0 if not.
643
 */
644
645
static int my_values_interfere(const ir_node *a, const ir_node *b)
{
646
647
	const ir_edge_t *edge;
	ir_node *bb;
648
649
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682

	/* If there is no dominance relation, they do not interfere. */
	if(!a2b && !b2a)
		return 0;

	/*
	 * Adjust a and b so, that a dominates b if
	 * a dominates b or vice versa.
	 */
	if(b2a) {
		const ir_node *t = a;
		a = b;
		b = t;
	}

	bb = get_nodes_block(b);

	/*
	 * 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.
	 */
	foreach_out_edge(a, edge) {
		const ir_node *user = get_edge_src_irn(edge);
		if(b == user)
			continue;

683
684
685
		if(get_irn_opcode(user) == iro_End)
			continue;

686
		/* in case of phi arguments we compare with the block the value comes from */
687
688
		if(is_Phi(user)) {
			ir_node *phiblock = get_nodes_block(user);
689
690
			if(phiblock == bb)
				continue;
691
692
693
			user = get_irn_n(phiblock, get_edge_src_pos(edge));
		}

694
		if(value_dominates(b, user))
695
696
697
698
699
			return 1;
	}

	return 0;
}
700
701
702



703
/*--------------------------------------------------------------------------- */
704

705
706
707
708
709
710
711
static const arch_env_t            *arch_env;
static ir_graph                    *irg;
static be_lv_t                     *lv;
static int                          problem_found;
static const arch_register_class_t *regclass;
static ir_node                    **registers;

712
static void check_output_constraints(ir_node *node)
713
{
714
	/* verify output register */
715
716
	if (arch_get_irn_reg_class_out(node) == regclass) {
		const arch_register_t *reg = arch_get_irn_register(node);
717
		if (reg == NULL) {
718
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
719
720
					node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
721
		} else if (!arch_register_type_is(reg, joker) && !arch_reg_out_is_allocatable(node, reg)) {
722
			ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n",
723
724
					reg->name, node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
725
726
		}
	}
727
728
729
730
731
732
}

static void check_input_constraints(ir_node *node)
{
	const arch_register_t *reg;
	int                    i, arity;
733

734
	/* verify input register */
735
	arity = get_irn_arity(node);
736
	for (i = 0; i < arity; ++i) {
737
738
		ir_node *pred = get_irn_n(node, i);

739
740
741
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
742
743
		if (is_Bad(pred)) {
			ir_fprintf(stderr, "Verify warning: %+F in block %+F(%s) has Bad as input %d\n",
744
745
				node, get_nodes_block(node), get_irg_dump_name(irg), i);
			problem_found = 1;
Christian Würdig's avatar
Christian Würdig committed
746
747
748
			continue;
		}

749
		if (arch_get_irn_reg_class(node, i) == NULL)
750
751
			continue;

752
		reg = arch_get_irn_register(pred);
753
		if (reg == NULL) {
754
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned (%+F input constraint)\n",
755
756
			           pred, get_nodes_block(pred), get_irg_dump_name(irg), node);
			problem_found = 1;
757
			continue;
758
		} else if (!arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(node, i, reg)) {
759
			ir_fprintf(stderr, "Verify warning: Register %s as input %d of %+F not allowed (register constraint) in block %+F(%s)\n",
760
761
			           reg->name, i, node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
762
763
764
		}
	}

765
766
767
768
	/* phis should be NOPs at this point, which means all input regs
	 * must be the same as the output reg */
	if (is_Phi(node)) {
		int i, arity;
769

770
		reg = arch_get_irn_register(node);
771

772
773
774
		arity = get_irn_arity(node);
		for (i = 0; i < arity; ++i) {
			ir_node               *pred     = get_Phi_pred(node, i);
775
			const arch_register_t *pred_reg = arch_get_irn_register(pred);
776

777
			if (reg != pred_reg && !arch_register_type_is(pred_reg, joker)) {
778
779
				const char *pred_name = pred_reg != NULL ? pred_reg->name : "(null)";
				const char *reg_name  = reg != NULL ? reg->name : "(null)";
780
				ir_fprintf(stderr, "Verify warning: Input %d of %+F in block %+F(%s) uses register %s instead of %s\n",
781
782
				           i, node, get_nodes_block(node),
				           get_irg_dump_name(irg), pred_name, reg_name);
783
784
				problem_found = 1;
			}
785
786
		}
	}
787
}
788

789
790
static void value_used(ir_node *block, ir_node *node)
{
791
792
	const arch_register_t *reg;
	ir_node               *reg_node;
793

794
	if (arch_get_irn_reg_class_out(node) != regclass)
795
796
		return;

797
	reg = arch_get_irn_register(node);
798
	if (reg == NULL || reg->type & arch_register_type_virtual)
799
800
801
802
803
		return;

	reg_node = registers[reg->index];
	if (reg_node != NULL && reg_node != node) {
		ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s) (nodes %+F %+F)\n",
804
			       reg->name, block, get_irg_dump_name(irg),
805
806
807
808
809
810
811
812
813
814
815
816
			       node, reg_node);
		problem_found = 1;
	}

	registers[reg->index] = node;
}

static void value_def(ir_node *node)
{
	const arch_register_t *reg;
	ir_node               *reg_node;

817
	if (arch_get_irn_reg_class_out(node) != regclass)
818
819
		return;

820
	reg = arch_get_irn_register(node);
821
	if (reg == NULL || reg->type & arch_register_type_virtual)
822
823
824
825
826
827
828
829
		return;

	reg_node = registers[reg->index];

	if (reg_node != node) {
		ir_fprintf(stderr, "Verify warning: Node %+F not registered as value for Register %s (but %+F) in block %+F(%s)\n",
			       node, reg->name, reg_node, get_nodes_block(node), get_irg_dump_name(irg));
		problem_found = 1;
830
	}
831
	registers[reg->index] = NULL;
832
833
}

834
835
static void verify_block_register_allocation(ir_node *block, void *data)
{
836
	int i, nregclasses;
837
	(void) data;
838

839
	nregclasses = arch_env_get_n_reg_class(arch_env);
840
	for (i = 0; i < nregclasses; ++i) {
841
842
		ir_node *node;
		int      idx, i2, n_regs;
843
844

		regclass = arch_env_get_reg_class(arch_env, i);
845

846
847
		assert(lv->nodes && "live sets must be computed");

Michael Beck's avatar
Michael Beck committed
848
		n_regs    = arch_register_class_n_regs(regclass);
849
		registers = ALLOCANZ(ir_node*, n_regs);
850

Michael Beck's avatar
Michael Beck committed
851
852
		be_lv_foreach(lv, block, be_lv_state_end, idx) {
			ir_node *node = be_lv_get_irn(lv, block, idx);
853
			value_used(block, node);
854
		}
855
856

		sched_foreach_reverse(block, node) {
857
858
859
860
861
862
863
			int arity;

			if (get_irn_mode(node) == mode_T) {
				const ir_edge_t *edge;
				foreach_out_edge(node, edge) {
					ir_node *def = get_edge_src_irn(edge);
					value_def(def);
864
					check_output_constraints(def);
865
866
867
				}
			} else {
				value_def(node);
868
				check_output_constraints(node);
869
870
			}

871
			check_input_constraints(node);
872

873
874
875
876
877
			/* process uses. (Phi inputs are no real uses) */
			if (!is_Phi(node)) {
				arity = get_irn_arity(node);
				for (i2 = 0; i2 < arity; ++i2) {
					ir_node *use = get_irn_n(node, i2);
878
					value_used(block, use);
879
				}
880
881
			}
		}
882

Michael Beck's avatar
Michael Beck committed
883
884
		be_lv_foreach(lv, block, be_lv_state_in, idx) {
			ir_node *node = be_lv_get_irn(lv, block, idx);
885
			value_def(node);
886
887
		}

888
889
890
891
892
893
894
895
896
		/* set must be empty now */
		for (i2 = 0; i2 < n_regs; ++i2) {
			if (registers[i2] == NULL)
				continue;

			ir_fprintf(stderr, "Verify warning: Node %+F not live-in and no def found in block %+F(%s)\n",
					registers[i2], block, get_irg_dump_name(irg));
			problem_found = 1;
		}
897
898
899
	}
}

900
901
int be_verify_register_allocation(const be_irg_t *birg)
{
902
903
	arch_env      = be_get_birg_arch_env(birg);
	irg           = be_get_birg_irg(birg);
904
	lv            = be_liveness(irg);
905
	problem_found = 0;
906

907
908
	be_liveness_assure_sets(lv);
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, NULL);
909

910
	be_liveness_free(lv);
911

912
	return !problem_found;
913
}
914
915
916



917
/*--------------------------------------------------------------------------- */
918
919
920
921
922
923
924
925
926



typedef struct _verify_out_dead_nodes_env {
	ir_graph *irg;
	bitset_t *reachable;
	int problem_found;
} verify_out_dead_nodes_env;

927
928
static void check_out_edges(ir_node *node, verify_out_dead_nodes_env *env)
{
929
	ir_graph *irg = env->irg;
930
931
	const ir_edge_t* edge;

932
	if (irn_visited_else_mark(node))
933
934
		return;

935
936
937
938
	/* we find too many (uncritical) dead nodes in block out edges */
	if(is_Block(node))
		return;

939
940
941
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

Matthias Braun's avatar
Matthias Braun committed
942
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(src)) {
Matthias Braun's avatar
Matthias Braun committed
943
944
945
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) only reachable through out edges from %+F\n",
			           src, get_nodes_block(src), get_irg_dump_name(irg), node);
			env->problem_found = 1;
946
			continue;
947
948
		}

Matthias Braun's avatar
Matthias Braun committed
949
		check_out_edges(src, env);
950
951
952
953
954
955
956
957
958
	}
}

static void set_reachable(ir_node *node, void* data)
{
	bitset_t* reachable = data;
	bitset_set(reachable, get_irn_idx(node));
}

959
960
int be_verify_out_edges(ir_graph *irg)
{
961
	verify_out_dead_nodes_env env;
962

963
return 1;
964
965
966
	env.irg           = irg;
	env.reachable     = bitset_alloca(get_irg_last_idx(irg));
	env.problem_found = edges_verify(irg);
967

968
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
969
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
970
	inc_irg_visited(irg);
971
972
	check_out_edges(get_irg_start(irg), &env);

973
	return ! env.problem_found;
974
}