beverify.c 26.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;
Matthias Braun's avatar
Matthias Braun committed
161
	ir_node *non_phi_found = NULL;
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)) {
Matthias Braun's avatar
Matthias Braun committed
203
204
205
			if (non_phi_found != NULL) {
				ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes (for example %+F) in block %+F (%s)\n",
					node, non_phi_found, block, get_irg_dump_name(env->irg));
206
207
				env->problem_found = 1;
			}
Matthias Braun's avatar
Matthias Braun committed
208
		} else {
Matthias Braun's avatar
Matthias Braun committed
209
			non_phi_found = node;
210
		}
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);
265
266
267
			while(be_is_Keep(prev))
				prev = sched_prev(prev);

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

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

290
static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
291
292
293
	if(is_Block(node))
		return -1;

294
295
296
	if(is_Proj(node))
		return 0;

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

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

314
315
316
	if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
		return -1;

317
318
319
320
321
322
	return 1;
}

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

325
	should_be = should_be_scheduled(env, node);
326
327
	if(should_be == -1)
		return;
328

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

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

	env.problem_found = 0;
346
347
	env.irg           = be_get_birg_irg(birg);
	env.scheduled     = bitset_alloca(get_irg_last_idx(env.irg));
348
	env.arch_env      = birg->main_env->arch_env;
349

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

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

357
358


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


362
363
364

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

typedef struct {
369
	const arch_env_t *arch_env;
370
371
372
373
374
375
376
377
378
	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;
379
380
	(void) size;

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

384
385
386
387
388
389
390
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));
}

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

406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
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;
}

422
423
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
424

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

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

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

	assert(is_Proj(node));

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

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

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

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

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

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

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

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

532
	/* @@@ ia32_classify returns classification of Proj_pred :-/ */
533
534
535
536
537
	if(is_Proj(node))
		return;

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

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

		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;

574
			if(my_values_interfere(sp1->spill, sp2->spill)) {
575
576
577
578
				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;
579
				my_values_interfere(sp1->spill, sp2->spill);
580
581
582
583
584
			}
		}
	}
}

585
586
587
588
589
590
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)) {
591
			ir_entity *ent = arch_get_frame_entity(node);
592
			be_check_entity(env, node, ent);
593
594
595
596
597
598
599
600
601
		}

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

602
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
603
604
605
{
	be_verify_spillslots_env_t env;

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

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

623
624


625
/*--------------------------------------------------------------------------- */
626
627
628
629
630
631
632
633



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

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

673
674
675
		if(get_irn_opcode(user) == iro_End)
			continue;

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

684
		if(value_dominates(b, user))
685
686
687
688
689
			return 1;
	}

	return 0;
}
690
691
692



693
/*--------------------------------------------------------------------------- */
694

695
696
697
698
699
700
701
702
static const arch_env_t            *arch_env;
static ir_graph                    *irg;
static be_lv_t                     *lv;
static int                          problem_found;
static const arch_register_class_t *regclass;
static ir_node                    **registers;

static void check_register_constraints(ir_node *node)
703
{
704
	const arch_register_t *reg;
705
	int                   i, arity;
706

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

721
	/* verify input register */
722
	arity = get_irn_arity(node);
723
	for (i = 0; i < arity; ++i) {
724
725
		ir_node *pred = get_irn_n(node, i);

726
727
728
		if (is_Unknown(pred))
			continue;

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

736
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
737
738
739
			continue;

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

753
754
755
756
	/* phis should be NOPs at this point, which means all input regs
	 * must be the same as the output reg */
	if (is_Phi(node)) {
		int i, arity;
757
758

		reg = arch_get_irn_register(arch_env, node);
759

760
761
762
763
		arity = get_irn_arity(node);
		for (i = 0; i < arity; ++i) {
			ir_node               *pred     = get_Phi_pred(node, i);
			const arch_register_t *pred_reg = arch_get_irn_register(arch_env, pred);
764

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

774
775
776
static void value_used(ir_node *node) {
	const arch_register_t *reg;
	ir_node               *reg_node;
777

778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
	if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
		return;

	reg = arch_get_irn_register(arch_env, node);
	if (reg->type & arch_register_type_virtual)
		return;

	reg_node = registers[reg->index];
	if (reg_node != NULL && reg_node != node) {
		ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s) (nodes %+F %+F)\n",
			       reg->name, get_nodes_block(node), get_irg_dump_name(irg),
			       node, reg_node);
		problem_found = 1;
	}

	registers[reg->index] = node;
}

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

	if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
		return;

	reg = arch_get_irn_register(arch_env, node);
	if (reg->type & arch_register_type_virtual)
		return;

	reg_node = registers[reg->index];

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

static void verify_block_register_allocation(ir_node *block, void *data) {
	int i, nregclasses;
820
	(void) data;
821

822
	nregclasses = arch_env_get_n_reg_class(arch_env);
823
	for (i = 0; i < nregclasses; ++i) {
824
		ir_node               *node;
Michael Beck's avatar
Michael Beck committed
825
		int                   idx, i2, n_regs;
826
827

		regclass = arch_env_get_reg_class(arch_env, i);
828

829
830
		assert(lv->nodes && "live sets must be computed");

Michael Beck's avatar
Michael Beck committed
831
832
		n_regs    = arch_register_class_n_regs(regclass);
		registers = alloca(n_regs * sizeof(registers[0]));
833
834
		memset(registers, 0, n_regs * sizeof(registers[0]));

Michael Beck's avatar
Michael Beck committed
835
836
		be_lv_foreach(lv, block, be_lv_state_end, idx) {
			ir_node *node = be_lv_get_irn(lv, block, idx);
837
838
			value_used(node);
		}
839
840

		sched_foreach_reverse(block, node) {
841
842
843
844
845
846
847
848
849
850
851
852
853
			int arity;

			if (get_irn_mode(node) == mode_T) {
				const ir_edge_t *edge;
				foreach_out_edge(node, edge) {
					ir_node *def = get_edge_src_irn(edge);
					value_def(def);
				}
			} else {
				value_def(node);
			}

			check_register_constraints(node);
854
			if (is_Phi(node))
855
856
857
858
859
860
861
862
				continue;

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

Michael Beck's avatar
Michael Beck committed
864
865
		be_lv_foreach(lv, block, be_lv_state_in, idx) {
			ir_node *node = be_lv_get_irn(lv, block, idx);
866
			value_def(node);
867
868
		}

869
870
871
872
873
874
875
876
877
		/* set must be empty now */
		for (i2 = 0; i2 < n_regs; ++i2) {
			if (registers[i2] == NULL)
				continue;

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

Sebastian Hack's avatar
Sebastian Hack committed
881
int be_verify_register_allocation(const be_irg_t *birg) {
882
883
884
885
	arch_env      = be_get_birg_arch_env(birg);
	irg           = be_get_birg_irg(birg);
	lv            = be_liveness(birg);
	problem_found = 0;
886

887
888
	be_liveness_assure_sets(lv);
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, NULL);
889

890
	be_liveness_free(lv);
891

892
	return !problem_found;
893
}
894
895
896



897
/*--------------------------------------------------------------------------- */
898
899
900
901
902
903
904
905
906
907



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) {
908
	ir_graph *irg = env->irg;
909
910
	const ir_edge_t* edge;

911
	if (irn_visited_else_mark(node))
912
913
		return;

914
915
916
917
	/* we find too many (uncritical) dead nodes in block out edges */
	if(is_Block(node))
		return;

918
919
920
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

Matthias Braun's avatar
Matthias Braun committed
921
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(src)) {
Matthias Braun's avatar
Matthias Braun committed
922
923
924
			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;
925
			continue;
926
927
		}

Matthias Braun's avatar
Matthias Braun committed
928
		check_out_edges(src, env);
929
930
931
932
933
934
935
936
937
938
939
	}
}

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;
940
941
942
943

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

945
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
946
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
947
	inc_irg_visited(irg);
948
949
	check_out_edges(get_irg_start(irg), &env);

950
	return ! env.problem_found;
951
}