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
	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;
402
403
	(void) size;

404
405
406
	return s1->spill != s2->spill;
}

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

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

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

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

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

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

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

	assert(is_Proj(node));

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

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

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

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

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

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

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

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

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

		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;

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

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

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

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

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

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

646
647
648
649
650
651
652
653
654
655
656


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



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

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

696
697
698
		if(get_irn_opcode(user) == iro_End)
			continue;

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

707
		if(value_dominates(b, user))
708
709
710
711
712
			return 1;
	}

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



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



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;

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

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

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

752
753
754
		if (is_Unknown(pred))
			continue;

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

762
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
763
764
765
			continue;

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

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

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

		reg = arch_get_irn_register(arch_env, node);
793
794
795
796
797
798

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

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

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

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

		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
855
	be_liveness_assure_sets(env.lv);
856
857
858
859
860
861
	irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env);

	be_liveness_free(env.lv);

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



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



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

879
880
881
882
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

883
884
885
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

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

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

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;
905
906
907
908

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

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

915
	return ! env.problem_found;
916
}