beverify.c 26.6 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
#include "config.h"
28

29
30
#include <limits.h>

31
32
33
#include "bitset.h"
#include "set.h"
#include "array.h"
34
35
36
37
38
39

#include "irnode.h"
#include "irgraph.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "irdump_t.h"
40
#include "iredges.h"
41
42
43

#include "beverify.h"
#include "belive.h"
44
#include "besched.h"
45
#include "benode.h"
46
#include "beirg.h"
47
#include "beintlive_t.h"
48

49
50
static int my_values_interfere(const ir_node *a, const ir_node *b);

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

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

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

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

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
101
		// print_living_values(stderr, &live_nodes);
102
		be_liveness_transfer(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
			env->problem_found = 1;
Sebastian Hack's avatar
Sebastian Hack committed
111
			assert(0);
112
113
		}
	}
114
	ir_nodeset_destroy(&live_nodes);
115
116
}

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

125
	env.lv                  = be_liveness(irg);
Christian Würdig's avatar
Christian Würdig committed
126
127
	env.irg                 = irg;
	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
	int      problem_found;     /**< flags indicating if there was a problem */
	bitset_t *scheduled;        /**< bitset of scheduled nodes */
	ir_graph *irg;              /**< the irg to check */
148
149
} be_verify_schedule_env_t;

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

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

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

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

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

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

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

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

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

254
		if(be_is_Keep(node) || be_is_CopyKeep(node)) {
255
256
257
258
259
			/* 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);
260
			while(be_is_Keep(prev) || be_is_CopyKeep(prev))
261
262
				prev = sched_prev(prev);

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

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

285
286
static int should_be_scheduled(ir_node *node)
{
287
	switch(get_irn_opcode(node)) {
288
289
	case iro_Bad:
	case iro_Block:
290
291
	case iro_End:
	case iro_NoMem:
292
293
294
	case iro_Pin:
	case iro_Proj:
	case iro_Sync:
295
	case iro_Unknown:
296
		return 0;
297
298
299
300
	case iro_Phi:
		if (get_irn_mode(node) == mode_M)
			return 0;
		break;
301
302
	case iro_Start:
	case iro_Jmp:
303
304
	case beo_Return:
		return 1;
305
306
307
308
	default:
		break;
	}

309
310
311
312
	if (get_irn_mode(node) != mode_T) {
		if (arch_irn_is_ignore(node))
			return -1;
	}
313

314
315
316
317
318
319
	return 1;
}

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

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

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

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

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

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

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

353
354


355
/*--------------------------------------------------------------------------- */
356
357


358
359
360

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

typedef struct {
365
366
367
368
	ir_graph  *irg;
	set       *spills;
	ir_node  **reloads;
	int        problem_found;
369
370
371
372
373
} 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;
374
375
	(void) size;

376
377
378
	return s1->spill != s2->spill;
}

379
380
381
382
383
384
385
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));
}

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

401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
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;
}

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

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

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

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

	assert(is_Proj(node));

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

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

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

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

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

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

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

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

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

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

534
535
536
537
538
539
		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;
		}
540
		ent = arch_get_frame_entity(node);
541
		be_check_entity(env, node, ent);
542
543
544
545
546
547

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

548
549
550
551
552
553
static void check_spillslot_interference(be_verify_spillslots_env_t *env)
{
	int       spillcount = set_count(env->spills);
	spill_t **spills     = ALLOCAN(spill_t*, spillcount);
	spill_t  *spill;
	int       i;
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568

	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;

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

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

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

597
int be_verify_spillslots(ir_graph *irg)
598
599
600
601
602
603
604
605
606
{
	be_verify_spillslots_env_t env;

	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);
607
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
608
609
610
611
612
613
614
615
616

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

617
618


619
/*--------------------------------------------------------------------------- */
620
621
622
623
624
625
626
627



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

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

667
668
669
		if(get_irn_opcode(user) == iro_End)
			continue;

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

678
		if(value_dominates(b, user))
679
680
681
682
683
			return 1;
	}

	return 0;
}
684
685
686



687
/*--------------------------------------------------------------------------- */
688

689
690
691
692
693
694
695
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;

696
static void check_output_constraints(ir_node *node)
697
{
698
	/* verify output register */
699
700
	if (arch_get_irn_reg_class_out(node) == regclass) {
		const arch_register_t *reg = arch_get_irn_register(node);
701
		if (reg == NULL) {
702
			ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
703
704
					node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
705
		} else if (!arch_register_type_is(reg, joker) && !arch_reg_out_is_allocatable(node, reg)) {
706
			ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n",
707
708
					reg->name, node, get_nodes_block(node), get_irg_dump_name(irg));
			problem_found = 1;
709
710
		}
	}
711
712
713
714
715
716
}

static void check_input_constraints(ir_node *node)
{
	const arch_register_t *reg;
	int                    i, arity;
717

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

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

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

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

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

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

754
		reg = arch_get_irn_register(node);
755

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

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

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

777
	if (arch_get_irn_reg_class_out(node) != regclass)
778
779
		return;

780
	reg = arch_get_irn_register(node);
781
	if (reg == NULL || reg->type & arch_register_type_virtual)
782
783
784
785
786
		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",
787
			       reg->name, block, get_irg_dump_name(irg),
788
789
790
791
792
793
794
795
796
797
798
799
			       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;

800
	if (arch_get_irn_reg_class_out(node) != regclass)
801
802
		return;

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

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

821
	nregclasses = arch_env_get_n_reg_class(arch_env);
822
	for (i = 0; i < nregclasses; ++i) {
823
824
		ir_node *node;
		int      idx, i2, n_regs;
825
826

		regclass = arch_env_get_reg_class(arch_env, i);
827

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

Michael Beck's avatar
Michael Beck committed
830
		n_regs    = arch_register_class_n_regs(regclass);
831
		registers = ALLOCANZ(ir_node*, n_regs);
832

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

		sched_foreach_reverse(block, node) {
839
840
841
842
843
844
845
			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);
846
					check_output_constraints(def);
847
848
849
				}
			} else {
				value_def(node);
850
				check_output_constraints(node);
851
852
			}

853
			check_input_constraints(node);
854

855
856
857
858
859
			/* process uses. (Phi inputs are no real uses) */
			if (!is_Phi(node)) {
				arity = get_irn_arity(node);
				for (i2 = 0; i2 < arity; ++i2) {
					ir_node *use = get_irn_n(node, i2);
860
					value_used(block, use);
861
				}
862
863
			}
		}
864

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

870
871
872
873
874
875
876
877
878
		/* 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;
		}
879
880
881
	}
}

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

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

891
	be_liveness_free(lv);
892

893
	return !problem_found;
894
}
895
896
897



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



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

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

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

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

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

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

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;
941

942
return 1;
943
944
945
	env.irg           = irg;
	env.reachable     = bitset_alloca(get_irg_last_idx(irg));
	env.problem_found = edges_verify(irg);
946

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

952
	return ! env.problem_found;
953
}