beverify.c 26.2 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
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 */
86
87
88
	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
89

90
	pressure = ir_nodeset_size(&live_nodes);
91
92
93
	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);
94
		print_living_values(stderr, &live_nodes);
95
96
		env->problem_found = 1;
	}
97

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

102
		be_liveness_transfer(env->arch_env, env->cls, irn, &live_nodes);
103

104
		pressure = ir_nodeset_size(&live_nodes);
105

106
		if(pressure > env->registers_available) {
107
108
			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);
109
			print_living_values(stderr, &live_nodes);
110
111
112
			env->problem_found = 1;
		}
	}
113
	ir_nodeset_destroy(&live_nodes);
114
115
}

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

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

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

	return ! env.problem_found;
136
137
}

138
139


140
/*--------------------------------------------------------------------------- */
141
142
143



144
typedef struct be_verify_schedule_env_t_ {
145
146
147
148
	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 */
149
150
} be_verify_schedule_env_t;

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

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

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

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

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

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

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

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

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

255
256
#ifdef SCHEDULE_PROJS
		/* check that all projs/keeps are behind their nodes */
Matthias Braun's avatar
Matthias Braun committed
257
258
259
260
261
		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
262
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
263
264
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
265
			}
Matthias Braun's avatar
Matthias Braun committed
266
		}
267
#endif
Matthias Braun's avatar
Matthias Braun committed
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
293
294
295
		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);
296
297
				}
			}
Matthias Braun's avatar
Matthias Braun committed
298
			if(problem) {
Matthias Braun's avatar
Matthias Braun committed
299
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
300
301
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
302
303
			}
		}
304
305
	}

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

314
static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
315
316
317
	if(is_Block(node))
		return -1;

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

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

347
348
349
	if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
		return -1;

350
351
352
353
354
355
	return 1;
}

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

358
	should_be = should_be_scheduled(env, node);
359
360
	if(should_be == -1)
		return;
361

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

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

	env.problem_found = 0;
379
380
381
	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;
382

383
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
384
	/* check if all nodes are scheduled */
385
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
386

Christian Würdig's avatar
Christian Würdig committed
387
	return ! env.problem_found;
388
}
389

390
391


392
/*--------------------------------------------------------------------------- */
393
394


395
396
397

typedef struct _spill_t {
	ir_node *spill;
398
	ir_entity *ent;
399
400
401
} spill_t;

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

414
415
416
	return s1->spill != s2->spill;
}

417
418
419
420
421
422
423
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));
}

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

439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
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;
}

455
456
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
457

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

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

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

	assert(is_Proj(node));

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

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

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

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

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

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

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

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

565
	/* @@@ ia32_classify returns classification of Proj_pred :-/ */
566
567
568
569
570
	if(is_Proj(node))
		return;

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

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

		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;

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

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

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

635
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
636
637
638
{
	be_verify_spillslots_env_t env;

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

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

656
657


658
/*--------------------------------------------------------------------------- */
659
660
661
662
663
664
665
666



/**
 * 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.
667
 */
668
static int my_values_interfere(const ir_node *a, const ir_node *b) {
669
670
	const ir_edge_t *edge;
	ir_node *bb;
671
672
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
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
703
704
705

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

706
707
708
		if(get_irn_opcode(user) == iro_End)
			continue;

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

717
		if(value_dominates(b, user))
718
719
720
721
722
			return 1;
	}

	return 0;
}
723
724
725



726
/*--------------------------------------------------------------------------- */
727
728
729
730
731
732
733
734
735
736



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;

737
738
739
static void check_register_constraints(ir_node *node,
                                       be_verify_register_allocation_env_t *env)
{
740
	const arch_env_t      *arch_env = env->arch_env;
741
	const arch_register_t *reg;
742
	int                   i, arity;
743

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

759
	/* verify input register */
760
	arity = get_irn_arity(node);
761
	for (i = 0; i < arity; ++i) {
762
763
		ir_node *pred = get_irn_n(node, i);

764
765
766
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
767
768
769
770
771
772
773
		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;
		}

774
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
775
776
777
			continue;

		reg = arch_get_irn_register(arch_env, pred);
778
		if (reg == NULL) {
779
780
781
782
783
			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;
		}
784
		else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, reg)) {
785
786
787
788
789
790
791
			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;
		}
	}
}

792
static void check_register_allocation(be_verify_register_allocation_env_t *env,
793
794
795
                                      const arch_register_class_t *regclass,
                                      ir_nodeset_t *nodes)
{
796
797
798
799
800
	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;
801
	ir_nodeset_iterator_t  iter;
802

803
	foreach_ir_nodeset(nodes, node, iter) {
804
		if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
805
806
807
			continue;

		reg = arch_get_irn_register(arch_env, node);
808
809
810
811
812
813

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

		if (bitset_is_set(registers, reg->index)) {
814
815
			fail = 1;
			break;
816
817
818
		}
		bitset_set(registers, reg->index);
	}
819

820
821
822
823
824
	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;

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

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;
843
844
845
		ir_nodeset_t live_nodes;

		ir_nodeset_init(&live_nodes);
846

847
848
849
		be_liveness_end_of_block(env->lv, env->arch_env, regclass, block,
		                         &live_nodes);
		check_register_allocation(env, regclass, &live_nodes);
850
851
852
853
854

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

855
856
			be_liveness_transfer(env->arch_env, regclass, node, &live_nodes);
			check_register_allocation(env, regclass, &live_nodes);
857
			check_register_constraints(node, env);
858
859
		}

860
		ir_nodeset_destroy(&live_nodes);
861
862
863
864
865
866
867
868
869
870
871
	}
}

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
872
	be_liveness_assure_sets(env.lv);
873
874
875
876
877
878
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env);

	be_liveness_free(env.lv);

	return !env.problem_found;
}
879
880
881



882
/*--------------------------------------------------------------------------- */
883
884
885
886
887
888
889
890
891
892



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) {
893
	ir_graph *irg = env->irg;
894
895
	const ir_edge_t* edge;

896
897
898
899
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

900
901
902
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

903
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) {
Matthias Braun's avatar
Matthias Braun committed
904
905
906
			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;
907
			continue;
908
909
		}

Matthias Braun's avatar
Matthias Braun committed
910
		check_out_edges(src, env);
911
912
913
914
915
916
917
918
919
920
921
	}
}

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;
922
923
924
925

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

927
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
928
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
929
	inc_irg_visited(irg);
930
931
	check_out_edges(get_irg_start(irg), &env);

932
	return ! env.problem_found;
933
}