beverify.c 25.9 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * 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
static void print_living_values(FILE *F, pset *live_nodes) {
66
67
	ir_node *node;

Christian Würdig's avatar
Christian Würdig committed
68
	ir_fprintf(F, "\t");
69
	foreach_pset(live_nodes, node) {
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
80
	be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data;
	pset    *live_nodes = pset_new_ptr_default();
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
	be_liveness_end_of_block(env->lv, env->arch_env, env->cls, block, live_nodes);
Christian Würdig's avatar
Christian Würdig committed
86

87
88
89
90
91
92
93
	pressure = pset_count(live_nodes);
	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);
		print_living_values(stderr, live_nodes);
		env->problem_found = 1;
	}
94

95
	sched_foreach_reverse(block, irn) {
Christian Würdig's avatar
Christian Würdig committed
96
		if (is_Phi(irn))
97
98
			break;

99
100
101
102
		be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes);

		pressure = pset_count(live_nodes);

103
		if(pressure > env->registers_available) {
104
105
			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);
Christian Würdig's avatar
Christian Würdig committed
106
			print_living_values(stderr, live_nodes);
107
108
109
110
111
112
			env->problem_found = 1;
		}
	}
	del_pset(live_nodes);
}

Christian Würdig's avatar
Christian Würdig committed
113
114
115
/**
 * Start a walk over the irg and check the register pressure.
 */
116
117
118
int be_verify_register_pressure(const be_irg_t *birg,
                                const arch_register_class_t *cls,
                                ir_graph *irg) {
119
120
	be_verify_register_pressure_env_t env;

Sebastian Hack's avatar
Sebastian Hack committed
121
	env.lv                  = be_liveness(irg);
Christian Würdig's avatar
Christian Würdig committed
122
	env.irg                 = irg;
Sebastian Hack's avatar
Sebastian Hack committed
123
	env.arch_env            = birg->main_env->arch_env;
Christian Würdig's avatar
Christian Würdig committed
124
	env.cls                 = cls;
Sebastian Hack's avatar
Sebastian Hack committed
125
	env.registers_available = env.cls->n_regs - be_put_ignore_regs(birg, env.cls, NULL);
Christian Würdig's avatar
Christian Würdig committed
126
	env.problem_found       = 0;
127

Sebastian Hack's avatar
Sebastian Hack committed
128
	be_liveness_assure_sets(env.lv);
Christian Würdig's avatar
Christian Würdig committed
129
	irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env);
Sebastian Hack's avatar
Sebastian Hack committed
130
	be_liveness_free(env.lv);
Christian Würdig's avatar
Christian Würdig committed
131
132

	return ! env.problem_found;
133
134
}

135
136


137
/*--------------------------------------------------------------------------- */
138
139
140



141
typedef struct be_verify_schedule_env_t_ {
142
143
144
145
	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 */
146
147
} be_verify_schedule_env_t;

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

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

172
		/* this node is scheduled */
173
174
175
176
177
178
		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));

179
		/* Check that scheduled nodes are in the correct block */
180
181
182
183
184
		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;
		}

185
		/* Check that timesteps are increasing */
186
187
188
189
190
191
192
		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;
193

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

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

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

245
		/* Check that no dead nodes are scheduled */
246
247
248
249
250
		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;
		}
251

252
253
#ifdef SCHEDULE_PROJS
		/* check that all projs/keeps are behind their nodes */
Matthias Braun's avatar
Matthias Braun committed
254
255
256
257
258
		if(is_Proj(node)) {
			ir_node *prev = sched_prev(node);
			while(is_Proj(prev))
				prev = sched_prev(prev);
			if(get_Proj_pred(node) != prev) {
Matthias Braun's avatar
Matthias Braun committed
259
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
260
261
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
262
			}
Matthias Braun's avatar
Matthias Braun committed
263
		}
264
#endif
Matthias Braun's avatar
Matthias Braun committed
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
		if(be_is_Keep(node)) {
			int arity   = get_irn_arity(node);
			int problem = 0;
			for(i = 0; i < arity; ++i) {
				ir_node *in = get_irn_n(node, i);
				ir_node *succ = sched_next(in);
				while(succ != node && !sched_is_end(succ)) {
					/* the node in between has to be another input of the
					 * keep or a Proj */
					int i2;
					int found = 0;

					if(is_Proj(succ)) {
						succ = sched_next(succ);
						continue;
					}

					for(i2 = 0; i2 < arity; ++i2) {
						ir_node *in2 = get_irn_n(node, i2);
						if(in2 == succ) {
							found = 1;
							break;
						}
					}
					if(!found)
						problem = 1;

					succ = sched_next(succ);
293
294
				}
			}
Matthias Braun's avatar
Matthias Braun committed
295
			if(problem) {
Matthias Braun's avatar
Matthias Braun committed
296
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
297
298
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
299
300
			}
		}
301
302
	}

303
	/* check that all delay branches are filled (at least with NOPs) */
Christian Würdig's avatar
Christian Würdig committed
304
	if (cfchange_found && delay_branches != 0) {
305
		ir_fprintf(stderr, "Verify warning: Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
306
			block, get_irg_dump_name(env->irg));
307
308
309
		env->problem_found = 1;
	}
}
310

311
static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
312
313
314
	if(is_Block(node))
		return -1;

315
	if(get_irn_mode(node) == mode_M) {
316
		if(is_Proj(node))
317
			return 0;
Michael Beck's avatar
Michael Beck committed
318
		if(is_Phi(node) || is_Sync(node) || is_Pin(node))
319
320
			return 0;
	}
321
#ifdef SCHEDULE_PROJS
Matthias Braun's avatar
Matthias Braun committed
322
323
324
325
326
	if(is_Proj(node)) {
		if(get_irn_mode(node) == mode_X)
			return 0;
		return should_be_scheduled(env, get_Proj_pred(node));
	}
327
328
329
330
#else
	if(is_Proj(node))
		return 0;
#endif
331
	if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
332
333
		return 0;

334
335
336
337
	switch(get_irn_opcode(node)) {
	case iro_End:
	case iro_NoMem:
	case iro_Bad:
338
	case iro_Unknown:
339
340
341
342
343
		return 0;
	default:
		break;
	}

344
345
346
	if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
		return -1;

347
348
349
350
351
352
	return 1;
}

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

355
	should_be = should_be_scheduled(env, node);
356
357
	if(should_be == -1)
		return;
358

359
360
361
	scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0;
	should_be = should_be ? 1 : 0;
	if(should_be != scheduled) {
362
		ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n",
363
			node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not");
364
365
366
367
		env->problem_found = 1;
	}
}

Christian Würdig's avatar
Christian Würdig committed
368
369
370
/**
 * Start a walk over the irg and check schedule.
 */
371
int be_verify_schedule(const be_irg_t *birg)
372
373
374
375
{
	be_verify_schedule_env_t env;

	env.problem_found = 0;
376
377
378
	env.irg           = be_get_birg_irg(birg);
	env.scheduled     = bitset_alloca(get_irg_last_idx(env.irg));
	env.arch_env      = birg->main_env->arch_env;
379

380
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
381
	/* check if all nodes are scheduled */
382
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
383

Christian Würdig's avatar
Christian Würdig committed
384
	return ! env.problem_found;
385
}
386

387
388


389
/*--------------------------------------------------------------------------- */
390
391


392
393
394

typedef struct _spill_t {
	ir_node *spill;
395
	ir_entity *ent;
396
397
398
} spill_t;

typedef struct {
399
	const arch_env_t *arch_env;
400
401
402
403
404
405
406
407
408
	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;
409
410
	(void) size;

411
412
413
	return s1->spill != s2->spill;
}

414
415
416
417
418
419
420
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));
}

421
static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
422
423
424
425
426
427
428
429
430
431
432
433
434
435
	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;
}

436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
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;
}

452
453
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
454

455
456
static
void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
457
458
459
460
461
462
	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));
	}
}

463
464
static
void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
465
	ir_entity *spillent = arch_get_frame_entity(env->arch_env, node);
466
	be_check_entity(env, node, spillent);
467
468
469
470
471
472
473
474
475
	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;
	}
}

476
static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
477
478
479
480
481
	int i, arity;
	spill_t spill, *res;
	int hash = HASH_PTR(node);
	int out;
	ir_node* memperm;
482
	ir_entity *spillent;
483
484
485
486
487
488
489

	assert(is_Proj(node));

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

	spillent = be_get_MemPerm_out_entity(memperm, out);
490
	be_check_entity(env, memperm, spillent);
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
	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);

506
507
	for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) {
		ir_node* arg = get_irn_n(memperm, i + 1);
508
		ir_entity* argent = be_get_MemPerm_in_entity(memperm, i);
509
510
511
512
513

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

514
static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) {
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
	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);

530
	/* is 1 of the arguments a spill? */
531
532
533
534
535
536
	for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
		ir_node* arg = get_irn_n(node, i);
		collect(env, arg, reload, ent);
	}
}

537
static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
538
539
540
541
542
543
544
	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 {
545
		/* Disabled for now, spills might get transformed by the backend */
546
#if 0
547
548
549
		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;
550
#endif
551
552
553
554
555
556
557
558
559
	}
}

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

562
	/* @@@ ia32_classify returns classification of Proj_pred :-/ */
563
564
565
566
567
	if(is_Proj(node))
		return;

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

570
571
572
573
574
575
		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
576
		ent = arch_get_frame_entity(env->arch_env, node);
577
		be_check_entity(env, node, ent);
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603

		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;

604
			if(my_values_interfere(sp1->spill, sp2->spill)) {
605
606
607
608
				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;
609
				my_values_interfere(sp1->spill, sp2->spill);
610
611
612
613
614
			}
		}
	}
}

615
616
617
618
619
620
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)) {
621
			ir_entity *ent = arch_get_frame_entity(env->arch_env, node);
622
			be_check_entity(env, node, ent);
623
624
625
626
627
628
629
630
631
		}

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

632
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
633
634
635
{
	be_verify_spillslots_env_t env;

636
	env.arch_env = arch_env;
637
638
639
640
641
642
	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);
643
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
644
645
646
647
648
649
650
651
652

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

653
654


655
/*--------------------------------------------------------------------------- */
656
657
658
659
660
661
662
663



/**
 * 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.
664
 */
665
static int my_values_interfere(const ir_node *a, const ir_node *b) {
666
667
	const ir_edge_t *edge;
	ir_node *bb;
668
669
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702

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

703
704
705
		if(get_irn_opcode(user) == iro_End)
			continue;

706
		/* in case of phi arguments we compare with the block the value comes from */
707
708
		if(is_Phi(user)) {
			ir_node *phiblock = get_nodes_block(user);
709
710
			if(phiblock == bb)
				continue;
711
712
713
			user = get_irn_n(phiblock, get_edge_src_pos(edge));
		}

714
		if(value_dominates(b, user))
715
716
717
718
719
			return 1;
	}

	return 0;
}
720
721
722



723
/*--------------------------------------------------------------------------- */
724
725
726
727
728
729
730
731
732
733



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;

734
static void check_register_constraints(ir_node *node, be_verify_register_allocation_env_t *env) {
735
	const arch_env_t      *arch_env = env->arch_env;
736
	const arch_register_t *reg;
737
	int                   i, arity;
738

739
740
	/* verify output register */
	if (arch_get_irn_reg_class(arch_env, node, -1) != NULL) {
741
		reg = arch_get_irn_register(arch_env, node);
742
		if (reg == NULL) {
743
744
745
746
			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;
		}
747
		else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, reg)) {
748
749
750
751
752
753
			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;
		}
	}

754
	/* verify input register */
755
	arity = get_irn_arity(node);
756
	for (i = 0; i < arity; ++i) {
757
758
		ir_node *pred = get_irn_n(node, i);

759
760
761
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
762
763
764
765
766
767
768
		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;
		}

769
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
770
771
772
			continue;

		reg = arch_get_irn_register(arch_env, pred);
773
		if (reg == NULL) {
774
775
776
777
778
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
			           pred, get_nodes_block(pred), get_irg_dump_name(env->irg));
			env->problem_found = 1;
			continue;
		}
779
		else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, reg)) {
780
781
782
783
784
785
786
			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;
		}
	}
}

787
788
static void check_register_allocation(be_verify_register_allocation_env_t *env,
                                      const arch_register_class_t *regclass, pset *nodes) {
789
790
791
792
793
	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;
794
795

	foreach_pset(nodes, node) {
796
		if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
797
798
799
			continue;

		reg = arch_get_irn_register(arch_env, node);
800
801
802
803
804
805

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

		if (bitset_is_set(registers, reg->index)) {
806
807
808
			pset_break(nodes);
			fail = 1;
			break;
809
810
811
		}
		bitset_set(registers, reg->index);
	}
812

813
814
815
816
817
818
819
820
821
822
823
	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;

		foreach_pset(nodes, node) {
			if (arch_get_irn_register(arch_env, node) == reg) {
				ir_fprintf(stderr, "  at node %+F\n", node);
			}
		}
	}
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
}

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;
	const arch_isa_t *isa = arch_env->isa;
	int i, nregclasses;

	nregclasses = arch_isa_get_n_reg_class(isa);
	for (i = 0; i < nregclasses; ++i) {
		const arch_register_class_t *regclass = arch_isa_get_reg_class(isa, i);
		ir_node *node;
		pset *live_nodes = pset_new_ptr_default();

		be_liveness_end_of_block(env->lv, env->arch_env, regclass, block, live_nodes);
		check_register_allocation(env, regclass, live_nodes);

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

			be_liveness_transfer(env->arch_env, regclass, node, live_nodes);
			check_register_allocation(env, regclass, live_nodes);
847
			check_register_constraints(node, env);
848
849
850
851
852
853
854
855
856
857
858
859
860
861
		}

		del_pset(live_nodes);
	}
}

int be_verify_register_allocation(const arch_env_t *arch_env, ir_graph *irg) {
	be_verify_register_allocation_env_t env;

	env.arch_env = arch_env;
	env.irg = irg;
	env.lv = be_liveness(irg);
	env.problem_found = 0;

Sebastian Hack's avatar
Sebastian Hack committed
862
	be_liveness_assure_sets(env.lv);
863
864
865
866
867
868
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env);

	be_liveness_free(env.lv);

	return !env.problem_found;
}
869
870
871



872
/*--------------------------------------------------------------------------- */
873
874
875
876
877
878
879
880
881
882



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) {
883
	ir_graph *irg = env->irg;
884
885
	const ir_edge_t* edge;

886
887
888
889
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

890
891
892
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

893
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) {
Matthias Braun's avatar
Matthias Braun committed
894
895
896
			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;
897
			continue;
898
899
		}

Matthias Braun's avatar
Matthias Braun committed
900
		check_out_edges(src, env);
901
902
903
904
905
906
907
908
909
910
911
	}
}

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;
912
913
914
915

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

917
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
918
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
919
	inc_irg_visited(irg);
920
921
	check_out_edges(get_irg_start(irg), &env);

922
	return ! env.problem_found;
923
}