beverify.c 26.3 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
 */
#ifdef HAVE_CONFIG_H
28
#include "config.h"
29
30
#endif

31
32
#include <limits.h>

33
34
35
#include "bitset.h"
#include "set.h"
#include "array.h"
36
37
38
39
40
41

#include "irnode.h"
#include "irgraph.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "irdump_t.h"
42
#include "iredges.h"
43
44
45
46

#include "beverify.h"
#include "belive.h"
#include "besched_t.h"
47
#include "benode_t.h"
48
#include "beirg_t.h"
49
#include "beintlive_t.h"
50

51
52
static int my_values_interfere(const ir_node *a, const ir_node *b);

53
typedef struct be_verify_register_pressure_env_t_ {
Christian Würdig's avatar
Christian Würdig committed
54
	ir_graph                    *irg;                 /**< the irg to verify */
Sebastian Hack's avatar
Sebastian Hack committed
55
	 be_lv_t                    *lv;                  /**< Liveness information. */
Christian Würdig's avatar
Christian Würdig committed
56
57
58
	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 */
59
60
} be_verify_register_pressure_env_t;

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

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

Christian Würdig's avatar
Christian Würdig committed
75
76
77
/**
 * Check if number of live nodes never exceeds the number of available registers.
 */
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;

Sebastian Hack's avatar
Sebastian Hack committed
127
	env.lv                  = be_liveness(birg);
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
static void verify_schedule_walker(ir_node *block, void *data) {
156
	be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data;
157
	ir_node *node;
Matthias Braun's avatar
Matthias Braun committed
158
	ir_node *non_phi_found = NULL;
159
	int cfchange_found = 0;
160
	/* TODO ask arch about delay branches */
161
	int delay_branches = 0;
162
	int last_timestep = INT_MIN;
163
164

	/*
165
166
167
168
	 * 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
169
170
	 *   4. mode_T nodes have all projs scheduled behind them followed by Keeps
	 *       (except mode_X projs)
171
	 */
172
173
	sched_foreach(block, node) {
		int i, arity;
174
175
		int timestep;

176
		/* this node is scheduled */
177
178
179
180
181
182
		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));

183
		/* Check that scheduled nodes are in the correct block */
184
185
186
187
188
		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;
		}

189
		/* Check that timesteps are increasing */
190
191
192
193
194
195
196
		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;
197

198
		/* Check that phis come before any other node */
199
		if (is_Phi(node)) {
Matthias Braun's avatar
Matthias Braun committed
200
201
202
			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));
203
204
				env->problem_found = 1;
			}
Matthias Braun's avatar
Matthias Braun committed
205
		} else {
Matthias Braun's avatar
Matthias Braun committed
206
			non_phi_found = node;
207
		}
208

209
		/* Check for control flow changing nodes */
210
		if (is_cfop(node) && get_irn_opcode(node) != iro_Start) {
Christian Würdig's avatar
Christian Würdig committed
211
212
213
			/* 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",
214
					node, block, get_irg_dump_name(env->irg));
215
216
217
				env->problem_found = 1;
			}
			cfchange_found = 1;
Christian Würdig's avatar
Christian Würdig committed
218
		} else if (cfchange_found) {
219
			/* proj and keepany aren't real instructions... */
220
221
222
223
224
225
226
227
228
			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--;
				}
229
230
			}
		}
231

232
		/* Check that all uses come before their definitions */
233
		if(!is_Phi(node)) {
234
			int nodetime = sched_get_time_step(node);
235
			for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
236
237
238
239
240
241
242
243
244
245
				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;
				}
246
			}
247
		}
248

249
		/* Check that no dead nodes are scheduled */
250
251
252
253
254
		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;
		}
255

Matthias Braun's avatar
Matthias Braun committed
256
		if(be_is_Keep(node)) {
257
258
259
260
261
			/* 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);
262
263
264
			while(be_is_Keep(prev))
				prev = sched_prev(prev);

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

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

287
288
static int should_be_scheduled(ir_node *node)
{
289
290
291
	if(is_Block(node))
		return -1;

292
293
294
	if(is_Proj(node))
		return 0;

295
	if(get_irn_mode(node) == mode_M) {
Michael Beck's avatar
Michael Beck committed
296
		if(is_Phi(node) || is_Sync(node) || is_Pin(node))
297
298
			return 0;
	}
299
	if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
300
301
		return 0;

302
303
304
305
	switch(get_irn_opcode(node)) {
	case iro_End:
	case iro_NoMem:
	case iro_Bad:
306
	case iro_Unknown:
307
308
309
310
311
		return 0;
	default:
		break;
	}

312
	if (arch_irn_get_flags(node) & arch_irn_flags_ignore)
313
314
		return -1;

315
316
317
318
319
320
	return 1;
}

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

323
	should_be = should_be_scheduled(node);
324
325
	if(should_be == -1)
		return;
326

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

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

	env.problem_found = 0;
344
345
	env.irg           = be_get_birg_irg(birg);
	env.scheduled     = bitset_alloca(get_irg_last_idx(env.irg));
346

347
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
348
	/* check if all nodes are scheduled */
349
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
350

Christian Würdig's avatar
Christian Würdig committed
351
	return ! env.problem_found;
352
}
353

354
355


356
/*--------------------------------------------------------------------------- */
357
358


359
360
361

typedef struct _spill_t {
	ir_node *spill;
362
	ir_entity *ent;
363
364
365
} spill_t;

typedef struct {
366
	const arch_env_t *arch_env;
367
368
369
370
371
372
373
374
375
	ir_graph *irg;
	set *spills;
	ir_node **reloads;
	int problem_found;
} be_verify_spillslots_env_t;

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

378
379
380
	return s1->spill != s2->spill;
}

381
382
383
384
385
386
387
static spill_t *find_spill(be_verify_spillslots_env_t *env, ir_node *node) {
	spill_t spill;

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

388
static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
389
390
391
392
393
394
395
396
397
398
399
400
401
402
	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;
}

403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
static ir_node *get_memory_edge(const ir_node *node) {
	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;
}

419
420
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
421

422
423
static
void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
424
425
426
427
428
429
	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));
	}
}

430
431
static
void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
432
	ir_entity *spillent = arch_get_frame_entity(node);
433
	be_check_entity(env, node, spillent);
434
435
436
437
438
439
440
441
442
	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;
	}
}

443
static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
444
445
446
447
448
	int i, arity;
	spill_t spill, *res;
	int hash = HASH_PTR(node);
	int out;
	ir_node* memperm;
449
	ir_entity *spillent;
450
451
452
453
454
455
456

	assert(is_Proj(node));

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

	spillent = be_get_MemPerm_out_entity(memperm, out);
457
	be_check_entity(env, memperm, spillent);
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
	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);

473
474
	for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) {
		ir_node* arg = get_irn_n(memperm, i + 1);
475
		ir_entity* argent = be_get_MemPerm_in_entity(memperm, i);
476
477
478
479
480

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

481
static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) {
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
	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);

497
	/* is 1 of the arguments a spill? */
498
499
500
501
502
503
	for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
		ir_node* arg = get_irn_n(node, i);
		collect(env, arg, reload, ent);
	}
}

504
static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
505
506
507
508
509
510
511
	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 {
512
		/* Disabled for now, spills might get transformed by the backend */
513
#if 0
514
515
516
		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;
517
#endif
518
519
520
521
522
523
524
525
526
527
	}
}

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

528
	/* @@@ ia32_classify returns classification of Proj_pred :-/ */
529
530
531
	if(is_Proj(node))
		return;

532
	if (arch_irn_class_is(node, reload)) {
533
		ir_node *spill = get_memory_edge(node);
534
		ir_entity *ent;
Matthias Braun's avatar
Matthias Braun committed
535

536
537
538
539
540
541
		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;
		}
542
		ent = arch_get_frame_entity(node);
543
		be_check_entity(env, node, ent);
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569

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

static void check_spillslot_interference(be_verify_spillslots_env_t *env) {
	int spillcount = set_count(env->spills);
	spill_t **spills = alloca(spillcount * sizeof(spills[0]));
	spill_t *spill;
	int i;

	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;

570
			if(my_values_interfere(sp1->spill, sp2->spill)) {
571
572
573
574
				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;
575
				my_values_interfere(sp1->spill, sp2->spill);
576
577
578
579
580
			}
		}
	}
}

581
582
583
584
585
586
static void check_lonely_spills(ir_node *node, void *data) {
	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)) {
587
			ir_entity *ent = arch_get_frame_entity(node);
588
			be_check_entity(env, node, ent);
589
590
591
592
593
594
595
596
597
		}

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

598
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
599
600
601
{
	be_verify_spillslots_env_t env;

602
	env.arch_env = arch_env;
603
604
605
606
607
608
	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);
609
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
610
611
612
613
614
615
616
617
618

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

619
620


621
/*--------------------------------------------------------------------------- */
622
623
624
625
626
627
628
629



/**
 * 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.
630
 */
631
static int my_values_interfere(const ir_node *a, const ir_node *b) {
632
633
	const ir_edge_t *edge;
	ir_node *bb;
634
635
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668

	/* 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;

669
670
671
		if(get_irn_opcode(user) == iro_End)
			continue;

672
		/* in case of phi arguments we compare with the block the value comes from */
673
674
		if(is_Phi(user)) {
			ir_node *phiblock = get_nodes_block(user);
675
676
			if(phiblock == bb)
				continue;
677
678
679
			user = get_irn_n(phiblock, get_edge_src_pos(edge));
		}

680
		if(value_dominates(b, user))
681
682
683
684
685
			return 1;
	}

	return 0;
}
686
687
688



689
/*--------------------------------------------------------------------------- */
690

691
692
693
694
695
696
697
698
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;

static void check_register_constraints(ir_node *node)
699
{
700
	const arch_register_t *reg;
701
	int                   i, arity;
702

703
	/* verify output register */
704
	if (arch_get_irn_reg_class(node, -1) != NULL) {
705
		reg = arch_get_irn_register(node);
706
		if (reg == NULL) {
707
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
708
709
					node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
710
		} else if (!arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(node, -1, reg)) {
711
			ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n",
712
713
					reg->name, node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
714
715
716
		}
	}

717
	/* verify input register */
718
	arity = get_irn_arity(node);
719
	for (i = 0; i < arity; ++i) {
720
721
		ir_node *pred = get_irn_n(node, i);

722
723
724
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
725
726
		if (is_Bad(pred)) {
			ir_fprintf(stderr, "Verify warning: %+F in block %+F(%s) has Bad as input %d\n",
727
728
				node, get_nodes_block(node), get_irg_dump_name(irg), i);
			problem_found = 1;
Christian Würdig's avatar
Christian Würdig committed
729
730
731
			continue;
		}

732
		if (arch_get_irn_reg_class(node, i) == NULL)
733
734
			continue;

735
		reg = arch_get_irn_register(pred);
736
		if (reg == NULL) {
737
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned (%+F input constraint)\n",
738
739
			           pred, get_nodes_block(pred), get_irg_dump_name(irg), node);
			problem_found = 1;
740
			continue;
741
		} else if (!arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(node, i, reg)) {
742
			ir_fprintf(stderr, "Verify warning: Register %s as input %d of %+F not allowed (register constraint) in block %+F(%s)\n",
743
744
			           reg->name, i, node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
745
746
747
		}
	}

748
749
750
751
	/* 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;
752

753
		reg = arch_get_irn_register(node);
754

755
756
757
		arity = get_irn_arity(node);
		for (i = 0; i < arity; ++i) {
			ir_node               *pred     = get_Phi_pred(node, i);
758
			const arch_register_t *pred_reg = arch_get_irn_register(pred);
759

760
			if (reg != pred_reg && !arch_register_type_is(pred_reg, joker)) {
761
762
				ir_fprintf(stderr, "Verify warning: Input %d of %+F in block %+F(%s) uses register %s instead of %s\n",
				           i, node, get_nodes_block(node), get_irg_dump_name(irg), pred_reg->name, reg->name);
763
764
				problem_found = 1;
			}
765
766
		}
	}
767
}
768

769
770
771
static void value_used(ir_node *node) {
	const arch_register_t *reg;
	ir_node               *reg_node;
772

773
	if (arch_get_irn_reg_class(node, -1) != regclass)
774
775
		return;

776
	reg = arch_get_irn_register(node);
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
	if (reg->type & arch_register_type_virtual)
		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",
			       reg->name, get_nodes_block(node), get_irg_dump_name(irg),
			       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;

796
	if (arch_get_irn_reg_class(node, -1) != regclass)
797
798
		return;

799
	reg = arch_get_irn_register(node);
800
801
802
803
804
805
806
807
808
	if (reg->type & arch_register_type_virtual)
		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;
809
	}
810
	registers[reg->index] = NULL;
811
812
813
814
}

static void verify_block_register_allocation(ir_node *block, void *data) {
	int i, nregclasses;
815
	(void) data;
816

817
	nregclasses = arch_env_get_n_reg_class(arch_env);
818
	for (i = 0; i < nregclasses; ++i) {
819
		ir_node               *node;
Michael Beck's avatar
Michael Beck committed
820
		int                   idx, i2, n_regs;
821
822

		regclass = arch_env_get_reg_class(arch_env, i);
823

824
825
		assert(lv->nodes && "live sets must be computed");

Michael Beck's avatar
Michael Beck committed
826
827
		n_regs    = arch_register_class_n_regs(regclass);
		registers = alloca(n_regs * sizeof(registers[0]));
828
829
		memset(registers, 0, n_regs * sizeof(registers[0]));

Michael Beck's avatar
Michael Beck committed
830
831
		be_lv_foreach(lv, block, be_lv_state_end, idx) {
			ir_node *node = be_lv_get_irn(lv, block, idx);
832
833
			value_used(node);
		}
834
835

		sched_foreach_reverse(block, node) {
836
837
838
839
840
841
842
843
844
845
846
847
848
			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);
				}
			} else {
				value_def(node);
			}

			check_register_constraints(node);
849
			if (is_Phi(node))
850
851
852
853
854
855
856
857
				continue;

			arity = get_irn_arity(node);
			for (i2 = 0; i2 < arity; ++i2) {
				ir_node *use = get_irn_n(node, i2);
				value_used(use);
			}
		}
858

Michael Beck's avatar
Michael Beck committed
859
860
		be_lv_foreach(lv, block, be_lv_state_in, idx) {
			ir_node *node = be_lv_get_irn(lv, block, idx);
861
			value_def(node);
862
863
		}

864
865
866
867
868
869
870
871
872
		/* 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;
		}
873
874
875
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
876
int be_verify_register_allocation(const be_irg_t *birg) {
877
878
879
880
	arch_env      = be_get_birg_arch_env(birg);
	irg           = be_get_birg_irg(birg);
	lv            = be_liveness(birg);
	problem_found = 0;
881

882
883
	be_liveness_assure_sets(lv);
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, NULL);
884

885
	be_liveness_free(lv);
886

887
	return !problem_found;
888
}
889
890
891



892
/*--------------------------------------------------------------------------- */
893
894
895
896
897
898
899
900
901
902



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

static void check_out_edges(ir_node *node, verify_out_dead_nodes_env *env) {
903
	ir_graph *irg = env->irg;
904
905
	const ir_edge_t* edge;

906
	if (irn_visited_else_mark(node))
907
908
		return;

909
910
911
912
	/* we find too many (uncritical) dead nodes in block out edges */
	if(is_Block(node))
		return;

913
914
915
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

Matthias Braun's avatar
Matthias Braun committed
916
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(src)) {
Matthias Braun's avatar
Matthias Braun committed
917
918
919
			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;
920
			continue;
921
922
		}

Matthias Braun's avatar
Matthias Braun committed
923
		check_out_edges(src, env);
924
925
926
927
928
929
930
931
932
933
934
	}
}

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

int be_verify_out_edges(ir_graph *irg) {
	verify_out_dead_nodes_env env;
935
936
937
938

	env.irg           = irg;
	env.reachable     = bitset_alloca(get_irg_last_idx(irg));
	env.problem_found = edges_verify(irg);
939

940
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
941
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
942
	inc_irg_visited(irg);
943
944
	check_out_edges(get_irg_start(irg), &env);

945
	return ! env.problem_found;
946
}