beverify.c 24.4 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
166
	sched_foreach(block, node) {
		int i, arity;
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
		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;
190

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

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

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

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

250
	/* check that all delay branches are filled (at least with NOPs) */
Christian Würdig's avatar
Christian Würdig committed
251
	if (cfchange_found && delay_branches != 0) {
252
		ir_fprintf(stderr, "Verify warning: Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
253
			block, get_irg_dump_name(env->irg));
254
255
256
		env->problem_found = 1;
	}
}
257

258
static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
259
260
261
	if(is_Block(node))
		return -1;

262
	if(get_irn_mode(node) == mode_M) {
263
264
		if(is_Proj(node))
			return -1;
Michael Beck's avatar
Michael Beck committed
265
		if(is_Phi(node) || is_Sync(node) || is_Pin(node))
266
267
			return 0;
	}
Matthias Braun's avatar
Matthias Braun committed
268
269
270
271
272
	if(is_Proj(node)) {
		if(get_irn_mode(node) == mode_X)
			return 0;
		return should_be_scheduled(env, get_Proj_pred(node));
	}
273
	if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
274
275
		return 0;

276
277
278
279
	switch(get_irn_opcode(node)) {
	case iro_End:
	case iro_NoMem:
	case iro_Bad:
280
	case iro_Unknown:
281
282
283
284
285
		return 0;
	default:
		break;
	}

286
287
288
	if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
		return -1;

289
290
291
292
293
294
	return 1;
}

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

297
	should_be = should_be_scheduled(env, node);
298
299
	if(should_be == -1)
		return;
300

301
302
303
	scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0;
	should_be = should_be ? 1 : 0;
	if(should_be != scheduled) {
304
		ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n",
305
			node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not");
306
307
308
309
		env->problem_found = 1;
	}
}

Christian Würdig's avatar
Christian Würdig committed
310
311
312
/**
 * Start a walk over the irg and check schedule.
 */
313
int be_verify_schedule(const be_irg_t *birg)
314
315
316
317
{
	be_verify_schedule_env_t env;

	env.problem_found = 0;
318
319
320
	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;
321

322
	irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
323
	// check if all nodes are scheduled
324
	irg_walk_graph(env.irg, check_schedule, NULL, &env);
325

Christian Würdig's avatar
Christian Würdig committed
326
	return ! env.problem_found;
327
}
328

329
330


331
332
333
//---------------------------------------------------------------------------


334
335
336

typedef struct _spill_t {
	ir_node *spill;
337
	ir_entity *ent;
338
339
340
} spill_t;

typedef struct {
341
	const arch_env_t *arch_env;
342
343
344
345
346
347
348
349
350
351
352
353
	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;
}

354
355
356
357
358
359
360
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));
}

361
static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
362
363
364
365
366
367
368
369
370
371
372
373
374
375
	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;
}

376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
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;
}

392
393
static
void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
394

395
396
static
void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
397
398
399
400
401
402
	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));
	}
}

403
404
static
void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
405
	ir_entity *spillent = arch_get_frame_entity(env->arch_env, node);
406
	be_check_entity(env, node, spillent);
407
408
409
410
411
412
413
414
415
	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;
	}
}

416
static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
417
418
419
420
421
	int i, arity;
	spill_t spill, *res;
	int hash = HASH_PTR(node);
	int out;
	ir_node* memperm;
422
	ir_entity *spillent;
423
424
425
426
427
428
429

	assert(is_Proj(node));

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

	spillent = be_get_MemPerm_out_entity(memperm, out);
430
	be_check_entity(env, memperm, spillent);
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
	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);

446
447
	for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) {
		ir_node* arg = get_irn_n(memperm, i + 1);
448
		ir_entity* argent = be_get_MemPerm_in_entity(memperm, i);
449
450
451
452
453

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

454
static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) {
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
	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);
	}
}

477
static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
478
479
480
481
482
483
484
	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 {
485
486
		// Disabled for now, spills might get transformed by the backend
#if 0
487
488
489
		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;
490
#endif
491
492
493
494
495
496
497
498
499
	}
}

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

502
503
504
505
506
507
	// @@@ 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);
508
		ir_entity *ent;
Matthias Braun's avatar
Matthias Braun committed
509

510
511
512
513
514
515
		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
516
		ent = arch_get_frame_entity(env->arch_env, node);
517
		be_check_entity(env, node, ent);
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543

		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;

544
			if(my_values_interfere(sp1->spill, sp2->spill)) {
545
546
547
548
				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;
549
				my_values_interfere(sp1->spill, sp2->spill);
550
551
552
553
554
			}
		}
	}
}

555
556
557
558
559
560
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)) {
561
			ir_entity *ent = arch_get_frame_entity(env->arch_env, node);
562
			be_check_entity(env, node, ent);
563
564
565
566
567
568
569
570
571
		}

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

572
int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
573
574
575
{
	be_verify_spillslots_env_t env;

576
	env.arch_env = arch_env;
577
578
579
580
581
582
	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);
583
	irg_walk_graph(irg, check_lonely_spills, NULL, &env);
584
585
586
587
588
589
590
591
592

	check_spillslot_interference(&env);

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

	return ! env.problem_found;
}

593
594
595
596
597
598
599
600
601
602
603


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



/**
 * 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.
604
 */
605
static int my_values_interfere(const ir_node *a, const ir_node *b) {
606
607
	const ir_edge_t *edge;
	ir_node *bb;
608
609
	int a2b = value_dominates(a, b);
	int b2a = value_dominates(b, a);
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642

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

643
644
645
		if(get_irn_opcode(user) == iro_End)
			continue;

646
647
648
		// 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);
649
650
			if(phiblock == bb)
				continue;
651
652
653
			user = get_irn_n(phiblock, get_edge_src_pos(edge));
		}

654
		if(value_dominates(b, user))
655
656
657
658
659
			return 1;
	}

	return 0;
}
660
661
662
663
664
665
666
667
668
669
670
671
672
673



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



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;

674
static void check_register_constraints(ir_node *node, be_verify_register_allocation_env_t *env) {
675
	const arch_env_t      *arch_env = env->arch_env;
676
	const arch_register_t *reg;
677
	int                   i, arity;
678

679
680
	/* verify output register */
	if (arch_get_irn_reg_class(arch_env, node, -1) != NULL) {
681
		reg = arch_get_irn_register(arch_env, node);
682
		if (reg == NULL) {
683
684
685
686
			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;
		}
687
		else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, reg)) {
688
689
690
691
692
693
			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;
		}
	}

694
	/* verify input register */
695
	arity = get_irn_arity(node);
696
	for (i = 0; i < arity; ++i) {
697
698
		ir_node *pred = get_irn_n(node, i);

699
700
701
		if (is_Unknown(pred))
			continue;

Christian Würdig's avatar
Christian Würdig committed
702
703
704
705
706
707
708
		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;
		}

709
		if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
710
711
712
			continue;

		reg = arch_get_irn_register(arch_env, pred);
713
		if (reg == NULL) {
714
715
716
717
718
			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;
		}
719
		else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, reg)) {
720
721
722
723
724
725
726
			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;
		}
	}
}

727
728
static void check_register_allocation(be_verify_register_allocation_env_t *env,
                                      const arch_register_class_t *regclass, pset *nodes) {
729
730
731
732
733
	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;
734
735

	foreach_pset(nodes, node) {
736
		if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
737
738
739
			continue;

		reg = arch_get_irn_register(arch_env, node);
740
741
742
743
744
745

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

		if (bitset_is_set(registers, reg->index)) {
746
747
748
			pset_break(nodes);
			fail = 1;
			break;
749
750
751
		}
		bitset_set(registers, reg->index);
	}
752

753
754
755
756
757
758
759
760
761
762
763
	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);
			}
		}
	}
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
}

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);
787
			check_register_constraints(node, env);
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
		}

		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;
}
808
809
810
811
812
813
814
815
816
817
818
819
820
821



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



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) {
822
	ir_graph *irg = env->irg;
823
824
	const ir_edge_t* edge;

825
826
827
828
	if(irn_visited(node))
		return;
	mark_irn_visited(node);

829
830
831
	foreach_out_edge(node, edge) {
		ir_node* src = get_edge_src_irn(edge);

832
		if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) {
Matthias Braun's avatar
Matthias Braun committed
833
834
835
			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;
836
			continue;
837
838
		}

Matthias Braun's avatar
Matthias Braun committed
839
		check_out_edges(src, env);
840
841
842
843
844
845
846
847
848
849
850
	}
}

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;
851
852
853
854

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

856
	irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
Matthias Braun's avatar
Matthias Braun committed
857
	irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
858
	inc_irg_visited(irg);
859
860
	check_out_edges(get_irg_start(irg), &env);

861
	return ! env.problem_found;
862
}