beverify.c 25.8 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
59
	const arch_env_t            *arch_env;            /**< an architecture environment */
	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 */
60
61
} be_verify_register_pressure_env_t;

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
91
	// print_living_values(stderr, &live_nodes);
92
	pressure = ir_nodeset_size(&live_nodes);
93
94
95
	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);
96
		print_living_values(stderr, &live_nodes);
97
98
		env->problem_found = 1;
	}
99

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

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

107
		pressure = ir_nodeset_size(&live_nodes);
108

109
		if(pressure > env->registers_available) {
110
111
			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);
112
			print_living_values(stderr, &live_nodes);
113
			env->problem_found = 1;
Sebastian Hack's avatar
Sebastian Hack committed
114
			assert(0);
115
116
		}
	}
117
	ir_nodeset_destroy(&live_nodes);
118
119
}

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

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

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

	return ! env.problem_found;
140
141
}

142
143


144
/*--------------------------------------------------------------------------- */
145
146
147



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

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

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

179
		/* this node is scheduled */
180
181
182
183
184
185
		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));

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

192
		/* Check that timesteps are increasing */
193
194
195
196
197
198
199
		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;
200

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

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

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

252
		/* Check that no dead nodes are scheduled */
253
254
255
256
257
		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;
		}
258

Matthias Braun's avatar
Matthias Braun committed
259
		if(be_is_Keep(node)) {
260
261
262
263
264
			/* 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);
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
static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
288
289
290
	if(is_Block(node))
		return -1;

291
	if(get_irn_mode(node) == mode_M) {
292
		if(is_Proj(node))
293
			return 0;
Michael Beck's avatar
Michael Beck committed
294
		if(is_Phi(node) || is_Sync(node) || is_Pin(node))
295
296
			return 0;
	}
297
#ifdef SCHEDULE_PROJS
Matthias Braun's avatar
Matthias Braun committed
298
299
300
301
302
	if(is_Proj(node)) {
		if(get_irn_mode(node) == mode_X)
			return 0;
		return should_be_scheduled(env, get_Proj_pred(node));
	}
303
304
305
306
#else
	if(is_Proj(node))
		return 0;
#endif
307
	if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
308
309
		return 0;

310
311
312
313
	switch(get_irn_opcode(node)) {
	case iro_End:
	case iro_NoMem:
	case iro_Bad:
314
	case iro_Unknown:
315
316
317
318
319
		return 0;
	default:
		break;
	}

320
321
322
	if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
		return -1;

323
324
325
326
327
328
	return 1;
}

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

331
	should_be = should_be_scheduled(env, node);
332
333
	if(should_be == -1)
		return;
334

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

Christian Würdig's avatar
Christian Würdig committed
344
345
346
/**
 * Start a walk over the irg and check schedule.
 */
347
int be_verify_schedule(const be_irg_t *birg)
348
349
350
351
{
	be_verify_schedule_env_t env;

	env.problem_found = 0;
352
353
	env.irg           = be_get_birg_irg(birg);
	env.scheduled     = bitset_alloca(get_irg_last_idx(env.irg));
354
	env.arch_env      = birg->main_env->arch_env;
355

356
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
357
	/* check if all nodes are scheduled */
358
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
359

Christian Würdig's avatar
Christian Würdig committed
360
	return ! env.problem_found;
361
}
362

363
364


365
/*--------------------------------------------------------------------------- */
366
367


368
369
370

typedef struct _spill_t {
	ir_node *spill;
371
	ir_entity *ent;
372
373
374
} spill_t;

typedef struct {
375
	const arch_env_t *arch_env;
376
377
378
379
380
381
382
383
384
	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;
385
386
	(void) size;

387
388
389
	return s1->spill != s2->spill;
}

390
391
392
393
394
395
396
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));
}

397
static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
398
399
400
401
402
403
404
405
406
407
408
409
410
411
	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;
}

412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
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;
}

428
429
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
430

431
432
static
void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
433
434
435
436
437
438
	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));
	}
}

439
440
static
void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
441
	ir_entity *spillent = arch_get_frame_entity(env->arch_env, node);
442
	be_check_entity(env, node, spillent);
443
444
445
446
447
448
449
450
451
	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;
	}
}

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
static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) {
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
	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);

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

513
static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
514
515
516
517
518
519
520
	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 {
521
		/* Disabled for now, spills might get transformed by the backend */
522
#if 0
523
524
525
		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;
526
#endif
527
528
529
530
531
532
533
534
535
	}
}

/**
 * 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;
536
	const arch_env_t *arch_env = env->arch_env;
537

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

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

546
547
548
549
550
551
		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;
		}
Matthias Braun's avatar
Matthias Braun committed
552
		ent = arch_get_frame_entity(env->arch_env, node);
553
		be_check_entity(env, node, ent);
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579

		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;

580
			if(my_values_interfere(sp1->spill, sp2->spill)) {
581
582
583
584
				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;
585
				my_values_interfere(sp1->spill, sp2->spill);
586
587
588
589
590
			}
		}
	}
}

591
592
593
594
595
596
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)) {
597
			ir_entity *ent = arch_get_frame_entity(env->arch_env, node);
598
			be_check_entity(env, node, ent);
599
600
601
602
603
604
605
606
607
		}

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

608
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
609
610
611
{
	be_verify_spillslots_env_t env;

612
	env.arch_env = arch_env;
613
614
615
616
617
618
	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);
619
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
620
621
622
623
624
625
626
627
628

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

629
630


631
/*--------------------------------------------------------------------------- */
632
633
634
635
636
637
638
639



/**
 * 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.
640
 */
641
static int my_values_interfere(const ir_node *a, const ir_node *b) {
642
643
	const ir_edge_t *edge;
	ir_node *bb;
644
645
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
646
647
648
649
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

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

679
680
681
		if(get_irn_opcode(user) == iro_End)
			continue;

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

690
		if(value_dominates(b, user))
691
692
693
694
695
			return 1;
	}

	return 0;
}
696
697
698



699
/*--------------------------------------------------------------------------- */
700
701
702
703
704
705
706
707
708
709



typedef struct _be_verify_register_allocation_env_t {
	const arch_env_t *arch_env;
	ir_graph *irg;
	be_lv_t *lv;
	int problem_found;
} be_verify_register_allocation_env_t;

710
711
712
static void check_register_constraints(ir_node *node,
                                       be_verify_register_allocation_env_t *env)
{
713
	const arch_env_t      *arch_env = env->arch_env;
714
	const arch_register_t *reg;
715
	int                   i, arity;
716

717
718
	/* verify output register */
	if (arch_get_irn_reg_class(arch_env, node, -1) != NULL) {
719
		reg = arch_get_irn_register(arch_env, node);
720
		if (reg == NULL) {
721
722
723
724
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
					node, get_nodes_block(node), get_irg_dump_name(env->irg));
			env->problem_found = 1;
		}
725
		else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, reg)) {
726
727
728
729
730
731
			ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n",
					reg->name, node, get_nodes_block(node), get_irg_dump_name(env->irg));
			env->problem_found = 1;
		}
	}

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

737
738
739
		if (is_Unknown(pred))
			continue;

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

747
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
748
749
750
			continue;

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

765
static void check_register_allocation(be_verify_register_allocation_env_t *env,
766
767
768
                                      const arch_register_class_t *regclass,
                                      ir_nodeset_t *nodes)
{
769
770
771
772
773
	const arch_env_t      *arch_env  = env->arch_env;
	const arch_register_t *reg       = NULL;
	int                   fail       = 0;
	bitset_t              *registers = bitset_alloca(arch_register_class_n_regs(regclass));
	ir_node               *node;
774
	ir_nodeset_iterator_t  iter;
775

776
	foreach_ir_nodeset(nodes, node, iter) {
777
		if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
778
779
780
			continue;

		reg = arch_get_irn_register(arch_env, node);
781
782
783
784
785
786

		/* this problem is already reported in 'check_register_constraints' */
		if (! reg)
			continue;

		if (bitset_is_set(registers, reg->index)) {
787
788
			fail = 1;
			break;
789
790
791
		}
		bitset_set(registers, reg->index);
	}
792

793
794
795
796
797
	if (fail) {
		ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s)\n",
			       reg->name, get_nodes_block(node), get_irg_dump_name(env->irg));
		env->problem_found = 1;

798
		foreach_ir_nodeset(nodes, node, iter) {
799
800
801
802
803
			if (arch_get_irn_register(arch_env, node) == reg) {
				ir_fprintf(stderr, "  at node %+F\n", node);
			}
		}
	}
804
805
806
807
808
809
810
}

static void verify_block_register_allocation(ir_node *block, void *data) {
	be_verify_register_allocation_env_t *env = data;
	const arch_env_t *arch_env = env->arch_env;
	int i, nregclasses;

811
	nregclasses = arch_env_get_n_reg_class(arch_env);
812
	for (i = 0; i < nregclasses; ++i) {
813
		const arch_register_class_t *regclass = arch_env_get_reg_class(arch_env, i);
814
		ir_node *node;
815
816
817
		ir_nodeset_t live_nodes;

		ir_nodeset_init(&live_nodes);
818

819
820
821
		be_liveness_end_of_block(env->lv, env->arch_env, regclass, block,
		                         &live_nodes);
		check_register_allocation(env, regclass, &live_nodes);
822
823
824
825
826

		sched_foreach_reverse(block, node) {
			if (is_Phi(node))
				break;

827
828
			be_liveness_transfer(env->arch_env, regclass, node, &live_nodes);
			check_register_allocation(env, regclass, &live_nodes);
829
			check_register_constraints(node, env);
830
831
		}

832
		ir_nodeset_destroy(&live_nodes);
833
834
835
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
836
int be_verify_register_allocation(const be_irg_t *birg) {
837
838
	be_verify_register_allocation_env_t env;

Sebastian Hack's avatar
Sebastian Hack committed
839
840
841
	env.arch_env = be_get_birg_arch_env(birg);
	env.irg      = be_get_birg_irg(birg);
	env.lv       = be_liveness(birg);
842
843
	env.problem_found = 0;

Sebastian Hack's avatar
Sebastian Hack committed
844
	be_liveness_assure_sets(env.lv);
Sebastian Hack's avatar
Sebastian Hack committed
845
	irg_block_walk_graph(env.irg, verify_block_register_allocation, NULL, &env);
846
847
848
849
850

	be_liveness_free(env.lv);

	return !env.problem_found;
}
851
852
853



854
/*--------------------------------------------------------------------------- */
855
856
857
858
859
860
861
862
863
864



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) {
865
	ir_graph *irg = env->irg;
866
867
	const ir_edge_t* edge;

868
869
870
871
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

872
873
874
875
	/* we find too many (uncritical) dead nodes in block out edges */
	if(is_Block(node))
		return;

876
877
878
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

Matthias Braun's avatar
Matthias Braun committed
879
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(src)) {
Matthias Braun's avatar
Matthias Braun committed
880
881
882
			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;
883
			continue;
884
885
		}

Matthias Braun's avatar
Matthias Braun committed
886
		check_out_edges(src, env);
887
888
889
890
891
892
893
894
895
896
897
	}
}

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;
898
899
900
901

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

903
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
904
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
905
	inc_irg_visited(irg);
906
907
	check_out_edges(get_irg_start(irg), &env);

908
	return ! env.problem_found;
909
}