beverify.c 26.3 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Christian Würdig's avatar
Christian Würdig committed
20
21
22
23
24
25
/**
 * @file
 * @brief       Various verify routines that check a scheduled graph for correctness.
 * @author      Matthias Braun
 * @date        05.05.2006
 * @version     $Id$
26
27
 */
#ifdef HAVE_CONFIG_H
28
#include "config.h"
29
30
#endif

31
32
#include <limits.h>

33
34
35
#include "bitset.h"
#include "set.h"
#include "array.h"
36
37
38
39
40
41

#include "irnode.h"
#include "irgraph.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "irdump_t.h"
42
#include "iredges.h"
43
44
45
46

#include "beverify.h"
#include "belive.h"
#include "besched_t.h"
47
#include "benode_t.h"
48
#include "beirg_t.h"
49
#include "beintlive_t.h"
50

51
52
static int my_values_interfere(const ir_node *a, const ir_node *b);

53
typedef struct be_verify_register_pressure_env_t_ {
Christian Würdig's avatar
Christian Würdig committed
54
	ir_graph                    *irg;                 /**< the irg to verify */
Sebastian Hack's avatar
Sebastian Hack committed
55
	 be_lv_t                    *lv;                  /**< Liveness information. */
Christian Würdig's avatar
Christian Würdig committed
56
57
58
59
	const arch_env_t            *arch_env;            /**< an architecture environment */
	const arch_register_class_t *cls;                 /**< the register class to check for */
	int                         registers_available;  /**< number of available registers */
	int                         problem_found;        /**< flag indicating if a problem was found */
60
61
} be_verify_register_pressure_env_t;

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

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

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

Christian Würdig's avatar
Christian Würdig committed
84
	/* collect register pressure info, start with end of a block */
Sebastian Hack's avatar
Sebastian Hack committed
85
	be_liveness_end_of_block(env->lv, env->arch_env, env->cls, block, live_nodes);
Christian Würdig's avatar
Christian Würdig committed
86

87
88
89
90
91
92
93
	pressure = pset_count(live_nodes);
	if(pressure > env->registers_available) {
		ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n",
			block, get_irg_dump_name(env->irg), pressure, env->registers_available);
		print_living_values(stderr, live_nodes);
		env->problem_found = 1;
	}
94

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

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

		pressure = pset_count(live_nodes);

103
		if(pressure > env->registers_available) {
104
105
			ir_fprintf(stderr, "Verify Warning: Register pressure too high before node %+F in %+F(%s) (%d/%d):\n",
				irn, block, get_irg_dump_name(env->irg), pressure, env->registers_available);
Christian Würdig's avatar
Christian Würdig committed
106
			print_living_values(stderr, live_nodes);
107
108
109
110
111
112
			env->problem_found = 1;
		}
	}
	del_pset(live_nodes);
}

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

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

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

	return ! env.problem_found;
132
133
}

134
135
136
137
138
139


//---------------------------------------------------------------------------



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

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

	/*
162
163
164
165
	 * 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
166
167
	 *   4. mode_T nodes have all projs scheduled behind them followed by Keeps
	 *       (except mode_X projs)
168
	 */
169
170
	sched_foreach(block, node) {
		int i, arity;
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
		int timestep;

		// this node is scheduled
		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));

		// Check that scheduled nodes are in the correct block
		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;
		}

		// Check that timesteps are increasing
		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;
194

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

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

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

246
		// Check that no dead nodes are scheduled
247
248
249
250
251
		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;
		}
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304

		// check that all projs/keeps are behind their nodes
		if(proj_keep_mode == 0) {
			if(is_Proj(node)) {
				proj_keep_mode = 1;
				proj_keep_node = get_Proj_pred(node);
				if(get_Proj_pred(node) != sched_prev(node)) {
					ir_fprintf(stderr, "Proj %+F not scheduled after by its pred node in block %+F (%s)\n",
					           node, block, get_irg_dump_name(env->irg));
					env->problem_found = 1;
				}
			} else if(be_is_Keep(node)) {
				proj_keep_mode = 2;
				proj_keep_node = get_irn_n(node, 0);
				if(proj_keep_node != sched_prev(node)) {
					ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n",
					           node, block, get_irg_dump_name(env->irg));
					env->problem_found = 1;
				}

			}
		} else if(proj_keep_mode == 1) {
			if(is_Proj(node)) {
				if(get_Proj_pred(node) != proj_keep_node) {
					ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n",
					           node, block, get_irg_dump_name(env->irg));
					env->problem_found = 1;
				}
			} else if(be_is_Keep(node)) {
				ir_node *pred = get_irn_n(node, 0);
				if(skip_Proj_const(pred) != proj_keep_node) {
					ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n",
					           node, block, get_irg_dump_name(env->irg));
		   			env->problem_found = 1;
				} else {
					proj_keep_mode = 2;
				}
			} else {
				proj_keep_mode = 0;
				proj_keep_node = NULL;
			}
		} else if(proj_keep_mode == 2) {
			if(be_is_Keep(skip_Proj_const(node))) {
				if(get_irn_n(node, 0) != proj_keep_node) {
					ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n",
					           node, block, get_irg_dump_name(env->irg));
		   			env->problem_found = 1;
				}
			} else {
				proj_keep_mode = 0;
				proj_keep_node = NULL;
			}
		}
305
306
	}

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

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

319
	if(get_irn_mode(node) == mode_M) {
320
321
		if(is_Proj(node))
			return -1;
Michael Beck's avatar
Michael Beck committed
322
		if(is_Phi(node) || is_Sync(node) || is_Pin(node))
323
324
			return 0;
	}
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
	if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
331
332
		return 0;

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

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

346
347
348
349
350
351
	return 1;
}

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

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

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

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

	env.problem_found = 0;
375
376
377
	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;
378

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

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

386
387


388
389
390
//---------------------------------------------------------------------------


391
392
393

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

typedef struct {
398
	const arch_env_t *arch_env;
399
400
401
402
403
404
405
406
407
408
409
410
	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;
	return s1->spill != s2->spill;
}

411
412
413
414
415
416
417
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));
}

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

433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
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;
}

449
450
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
451

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

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

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

	assert(is_Proj(node));

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

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

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

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

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

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

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

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

559
560
561
562
563
564
	// @@@ ia32_classify returns classification of Proj_pred :-/
	if(is_Proj(node))
		return;

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

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

		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;

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

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

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

629
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
630
631
632
{
	be_verify_spillslots_env_t env;

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

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

650
651
652
653
654
655
656
657
658
659
660


//---------------------------------------------------------------------------



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

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

700
701
702
		if(get_irn_opcode(user) == iro_End)
			continue;

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

711
		if(value_dominates(b, user))
712
713
714
715
716
			return 1;
	}

	return 0;
}
717
718
719
720
721
722
723
724
725
726
727
728
729
730



//---------------------------------------------------------------------------



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;

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

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

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

756
757
758
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
759
760
761
762
763
764
765
		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;
		}

766
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
767
768
769
			continue;

		reg = arch_get_irn_register(arch_env, pred);
770
		if (reg == NULL) {
771
772
773
774
775
			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;
		}
776
		else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, reg)) {
777
778
779
780
781
782
783
			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;
		}
	}
}

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

	foreach_pset(nodes, node) {
793
		if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
794
795
796
			continue;

		reg = arch_get_irn_register(arch_env, node);
797
798
799
800
801
802

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

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

810
811
812
813
814
815
816
817
818
819
820
	if (fail) {
		ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s)\n",
			       reg->name, get_nodes_block(node), get_irg_dump_name(env->irg));
		env->problem_found = 1;

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

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

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

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

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

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

		del_pset(live_nodes);
	}
}

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

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

	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env);

	be_liveness_free(env.lv);

	return !env.problem_found;
}
865
866
867
868
869
870
871
872
873
874
875
876
877
878



//---------------------------------------------------------------------------



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) {
879
	ir_graph *irg = env->irg;
880
881
	const ir_edge_t* edge;

882
883
884
885
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

886
887
888
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

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

Matthias Braun's avatar
Matthias Braun committed
896
		check_out_edges(src, env);
897
898
899
900
901
902
903
904
905
906
907
	}
}

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;
908
909
910
911

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

913
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
914
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
915
	inc_irg_visited(irg);
916
917
	check_out_edges(get_irg_start(irg), &env);

918
	return ! env.problem_found;
919
}