beverify.c 25.7 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

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

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

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

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

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

		// check that all projs/keeps are behind their nodes
Matthias Braun's avatar
Matthias Braun committed
252
253
254
255
256
		if(is_Proj(node)) {
			ir_node *prev = sched_prev(node);
			while(is_Proj(prev))
				prev = sched_prev(prev);
			if(get_Proj_pred(node) != prev) {
257
				ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
258
259
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
260
			}
Matthias Braun's avatar
Matthias Braun committed
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
		}
		if(be_is_Keep(node)) {
			int arity   = get_irn_arity(node);
			int problem = 0;
			for(i = 0; i < arity; ++i) {
				ir_node *in = get_irn_n(node, i);
				ir_node *succ = sched_next(in);
				while(succ != node && !sched_is_end(succ)) {
					/* the node in between has to be another input of the
					 * keep or a Proj */
					int i2;
					int found = 0;

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

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

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

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

308
static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
309
310
311
	if(is_Block(node))
		return -1;

312
	if(get_irn_mode(node) == mode_M) {
313
		if(is_Proj(node))
314
			return 0;
Michael Beck's avatar
Michael Beck committed
315
		if(is_Phi(node) || is_Sync(node) || is_Pin(node))
316
317
			return 0;
	}
Matthias Braun's avatar
Matthias Braun committed
318
319
320
321
322
	if(is_Proj(node)) {
		if(get_irn_mode(node) == mode_X)
			return 0;
		return should_be_scheduled(env, get_Proj_pred(node));
	}
323
	if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
324
325
		return 0;

326
327
328
329
	switch(get_irn_opcode(node)) {
	case iro_End:
	case iro_NoMem:
	case iro_Bad:
330
	case iro_Unknown:
331
332
333
334
335
		return 0;
	default:
		break;
	}

336
337
338
	if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
		return -1;

339
340
341
342
343
344
	return 1;
}

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

347
	should_be = should_be_scheduled(env, node);
348
349
	if(should_be == -1)
		return;
350

351
352
353
	scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0;
	should_be = should_be ? 1 : 0;
	if(should_be != scheduled) {
354
		ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n",
355
			node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not");
356
357
358
359
		env->problem_found = 1;
	}
}

Christian Würdig's avatar
Christian Würdig committed
360
361
362
/**
 * Start a walk over the irg and check schedule.
 */
363
int be_verify_schedule(const be_irg_t *birg)
364
365
366
367
{
	be_verify_schedule_env_t env;

	env.problem_found = 0;
368
369
370
	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;
371

372
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
373
	// check if all nodes are scheduled
374
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
375

Christian Würdig's avatar
Christian Würdig committed
376
	return ! env.problem_found;
377
}
378

379
380


381
382
383
//---------------------------------------------------------------------------


384
385
386

typedef struct _spill_t {
	ir_node *spill;
387
	ir_entity *ent;
388
389
390
} spill_t;

typedef struct {
391
	const arch_env_t *arch_env;
392
393
394
395
396
397
398
399
400
401
402
403
	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;
}

404
405
406
407
408
409
410
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));
}

411
static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
412
413
414
415
416
417
418
419
420
421
422
423
424
425
	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;
}

426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
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;
}

442
443
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
444

445
446
static
void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
447
448
449
450
451
452
	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));
	}
}

453
454
static
void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
455
	ir_entity *spillent = arch_get_frame_entity(env->arch_env, node);
456
	be_check_entity(env, node, spillent);
457
458
459
460
461
462
463
464
465
	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;
	}
}

466
static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
467
468
469
470
471
	int i, arity;
	spill_t spill, *res;
	int hash = HASH_PTR(node);
	int out;
	ir_node* memperm;
472
	ir_entity *spillent;
473
474
475
476
477
478
479

	assert(is_Proj(node));

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

	spillent = be_get_MemPerm_out_entity(memperm, out);
480
	be_check_entity(env, memperm, spillent);
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
	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);

496
497
	for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) {
		ir_node* arg = get_irn_n(memperm, i + 1);
498
		ir_entity* argent = be_get_MemPerm_in_entity(memperm, i);
499
500
501
502
503

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

504
static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) {
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
	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);
	}
}

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

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

552
553
554
555
556
557
	// @@@ 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);
558
		ir_entity *ent;
Matthias Braun's avatar
Matthias Braun committed
559

560
561
562
563
564
565
		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
566
		ent = arch_get_frame_entity(env->arch_env, node);
567
		be_check_entity(env, node, ent);
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593

		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;

594
			if(my_values_interfere(sp1->spill, sp2->spill)) {
595
596
597
598
				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;
599
				my_values_interfere(sp1->spill, sp2->spill);
600
601
602
603
604
			}
		}
	}
}

605
606
607
608
609
610
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)) {
611
			ir_entity *ent = arch_get_frame_entity(env->arch_env, node);
612
			be_check_entity(env, node, ent);
613
614
615
616
617
618
619
620
621
		}

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

622
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
623
624
625
{
	be_verify_spillslots_env_t env;

626
	env.arch_env = arch_env;
627
628
629
630
631
632
	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);
633
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
634
635
636
637
638
639
640
641
642

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

643
644
645
646
647
648
649
650
651
652
653


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



/**
 * 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.
654
 */
655
static int my_values_interfere(const ir_node *a, const ir_node *b) {
656
657
	const ir_edge_t *edge;
	ir_node *bb;
658
659
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
660
661
662
663
664
665
666
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

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

693
694
695
		if(get_irn_opcode(user) == iro_End)
			continue;

696
697
698
		// 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);
699
700
			if(phiblock == bb)
				continue;
701
702
703
			user = get_irn_n(phiblock, get_edge_src_pos(edge));
		}

704
		if(value_dominates(b, user))
705
706
707
708
709
			return 1;
	}

	return 0;
}
710
711
712
713
714
715
716
717
718
719
720
721
722
723



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



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;

724
static void check_register_constraints(ir_node *node, be_verify_register_allocation_env_t *env) {
725
	const arch_env_t      *arch_env = env->arch_env;
726
	const arch_register_t *reg;
727
	int                   i, arity;
728

729
730
	/* verify output register */
	if (arch_get_irn_reg_class(arch_env, node, -1) != NULL) {
731
		reg = arch_get_irn_register(arch_env, node);
732
		if (reg == NULL) {
733
734
735
736
			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;
		}
737
		else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, reg)) {
738
739
740
741
742
743
			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;
		}
	}

744
	/* verify input register */
745
	arity = get_irn_arity(node);
746
	for (i = 0; i < arity; ++i) {
747
748
		ir_node *pred = get_irn_n(node, i);

749
750
751
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
752
753
754
755
756
757
758
		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;
		}

759
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
760
761
762
			continue;

		reg = arch_get_irn_register(arch_env, pred);
763
		if (reg == NULL) {
764
765
766
767
768
			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;
		}
769
		else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, reg)) {
770
771
772
773
774
775
776
			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;
		}
	}
}

777
778
static void check_register_allocation(be_verify_register_allocation_env_t *env,
                                      const arch_register_class_t *regclass, pset *nodes) {
779
780
781
782
783
	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;
784
785

	foreach_pset(nodes, node) {
786
		if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
787
788
789
			continue;

		reg = arch_get_irn_register(arch_env, node);
790
791
792
793
794
795

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

		if (bitset_is_set(registers, reg->index)) {
796
797
798
			pset_break(nodes);
			fail = 1;
			break;
799
800
801
		}
		bitset_set(registers, reg->index);
	}
802

803
804
805
806
807
808
809
810
811
812
813
	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);
			}
		}
	}
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
}

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);
837
			check_register_constraints(node, env);
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
		}

		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;
}
858
859
860
861
862
863
864
865
866
867
868
869
870
871



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



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) {
872
	ir_graph *irg = env->irg;
873
874
	const ir_edge_t* edge;

875
876
877
878
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

879
880
881
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

882
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) {
Matthias Braun's avatar
Matthias Braun committed
883
884
885
			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;
886
			continue;
887
888
		}

Matthias Braun's avatar
Matthias Braun committed
889
		check_out_edges(src, env);
890
891
892
893
894
895
896
897
898
899
900
	}
}

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;
901
902
903
904

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

906
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
907
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
908
	inc_irg_visited(irg);
909
910
	check_out_edges(get_irg_start(irg), &env);

911
	return ! env.problem_found;
912
}