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

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

	return ! env.problem_found;
133
134
}

135
136
137
138
139
140


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



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

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

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

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

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

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

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

		// check that all projs/keeps are behind their nodes
Matthias Braun's avatar
Matthias Braun committed
253
254
255
256
257
		if(is_Proj(node)) {
			ir_node *prev = sched_prev(node);
			while(is_Proj(prev))
				prev = sched_prev(prev);
			if(get_Proj_pred(node) != prev) {
Matthias Braun's avatar
Matthias Braun committed
258
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
259
260
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
261
			}
Matthias Braun's avatar
Matthias Braun committed
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
		}
		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);
291
292
				}
			}
Matthias Braun's avatar
Matthias Braun committed
293
			if(problem) {
Matthias Braun's avatar
Matthias Braun committed
294
				ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n",
Matthias Braun's avatar
Matthias Braun committed
295
296
				           node, block, get_irg_dump_name(env->irg));
				env->problem_found = 1;
297
298
			}
		}
299
300
	}

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

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

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

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

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

340
341
342
343
344
345
	return 1;
}

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

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

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

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

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

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

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

380
381


382
383
384
//---------------------------------------------------------------------------


385
386
387

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

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

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

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

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

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

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

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

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

	assert(is_Proj(node));

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

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

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

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

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

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

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

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

561
562
563
564
565
566
		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
567
		ent = arch_get_frame_entity(env->arch_env, node);
568
		be_check_entity(env, node, ent);
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
594

		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;

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

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

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

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

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

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

644
645
646
647
648
649
650
651
652
653
654


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



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

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

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

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

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

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



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



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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

		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;

Sebastian Hack's avatar
Sebastian Hack committed
853
	be_liveness_assure_sets(env.lv);
854
855
856
857
858
859
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env);

	be_liveness_free(env.lv);

	return !env.problem_found;
}
860
861
862
863
864
865
866
867
868
869
870
871
872
873



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



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

877
878
879
880
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

881
882
883
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

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

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

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;
903
904
905
906

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

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

913
	return ! env.problem_found;
914
}