beverify.c 6.03 KB
Newer Older
1
/*
Christian Würdig's avatar
Christian Würdig committed
2
3
4
5
6
 * Author:    Matthias Braun
 * Date:      05.05.2006
 * Copyright: (c) Universitaet Karlsruhe
 * License:   This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 * CVS-Id:    $Id$
7
8
9
10
11
12
13
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "beverify.h"
#include "belive.h"
14
#include "besched_t.h"
15
16
17
18
19
20

#include "irnode.h"
#include "irgraph.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "irdump_t.h"
21
#include "benode_t.h"
22
23

typedef struct be_verify_register_pressure_env_t_ {
Christian Würdig's avatar
Christian Würdig committed
24
	ir_graph                    *irg;                 /**< the irg to verify */
Sebastian Hack's avatar
Sebastian Hack committed
25
	 be_lv_t                    *lv;                  /**< Liveness information. */
Christian Würdig's avatar
Christian Würdig committed
26
27
28
29
	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 */
30
31
} be_verify_register_pressure_env_t;

Christian Würdig's avatar
Christian Würdig committed
32
33
34
35
/**
 * Print all nodes of a pset into a file.
 */
static void print_living_values(FILE *F, pset *live_nodes)
36
37
38
{
	ir_node *node;

Christian Würdig's avatar
Christian Würdig committed
39
	ir_fprintf(F, "\t");
40
	foreach_pset(live_nodes, node) {
Christian Würdig's avatar
Christian Würdig committed
41
		ir_fprintf(F, "%+F ", node);
42
	}
Christian Würdig's avatar
Christian Würdig committed
43
	ir_fprintf(F, "\n");
44
45
}

Christian Würdig's avatar
Christian Würdig committed
46
47
48
/**
 * Check if number of live nodes never exceeds the number of available registers.
 */
49
static void verify_liveness_walker(ir_node *block, void *data)
50
{
Christian Würdig's avatar
Christian Würdig committed
51
52
	be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data;
	pset    *live_nodes = pset_new_ptr_default();
53
	ir_node *irn;
54
	int pressure;
55

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

59
60
61
62
63
64
65
	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;
	}
66

67
	sched_foreach_reverse(block, irn) {
Christian Würdig's avatar
Christian Würdig committed
68
		if (is_Phi(irn))
69
70
			break;

71
72
73
74
		be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes);

		pressure = pset_count(live_nodes);

75
		if(pressure > env->registers_available) {
76
77
			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
78
			print_living_values(stderr, live_nodes);
79
80
81
82
83
84
			env->problem_found = 1;
		}
	}
	del_pset(live_nodes);
}

Christian Würdig's avatar
Christian Würdig committed
85
86
87
/**
 * Start a walk over the irg and check the register pressure.
 */
88
int be_verify_register_pressure(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_graph *irg)
89
90
91
{
	be_verify_register_pressure_env_t env;

Sebastian Hack's avatar
Sebastian Hack committed
92
	env.lv                  = be_liveness(irg);
Christian Würdig's avatar
Christian Würdig committed
93
94
95
	env.irg                 = irg;
	env.arch_env            = arch_env;
	env.cls                 = cls;
96
	env.registers_available = arch_count_non_ignore_regs(arch_env, cls);
Christian Würdig's avatar
Christian Würdig committed
97
	env.problem_found       = 0;
98

Christian Würdig's avatar
Christian Würdig committed
99
	irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env);
Sebastian Hack's avatar
Sebastian Hack committed
100
	be_liveness_free(env.lv);
Christian Würdig's avatar
Christian Würdig committed
101
102

	return ! env.problem_found;
103
104
105
}

typedef struct be_verify_schedule_env_t_ {
Christian Würdig's avatar
Christian Würdig committed
106
107
	int      problem_found;    /**< flags indicating if there was a problem */
	ir_graph *irg;             /**< the irg to check */
108
109
} be_verify_schedule_env_t;

Christian Würdig's avatar
Christian Würdig committed
110
111
112
/**
 * Simple schedule checker.
 */
113
static void verify_schedule_walker(ir_node *block, void *data)
114
115
{
	be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data;
116
	ir_node *node;
Christian Würdig's avatar
Christian Würdig committed
117
	int non_phi_found  = 0;
118
	int cfchange_found = 0;
Matthias Braun's avatar
Matthias Braun committed
119
	// TODO ask arch about delay branches
120
	int delay_branches = 0;
121
	pset *uses = pset_new_ptr_default();
122
123

	/*
124
125
126
127
	 * 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
128
	 */
129
130
131
132
133
	sched_foreach(block, node) {
		int i, arity;

		// 1. Check for phis
		if (is_Phi(node)) {
Christian Würdig's avatar
Christian Würdig committed
134
135
			if (non_phi_found) {
				ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes in block %+F (%s)\n",
136
					node, block, get_irg_dump_name(env->irg));
137
138
				env->problem_found = 1;
			}
Matthias Braun's avatar
Matthias Braun committed
139
		} else {
140
141
			non_phi_found = 1;
		}
142

143
144
		// 2. Check for control flow changing nodes
		if (is_cfop(node) && get_irn_opcode(node) != iro_Start) {
Christian Würdig's avatar
Christian Würdig committed
145
146
147
			/* 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",
148
					node, block, get_irg_dump_name(env->irg));
149
150
151
				env->problem_found = 1;
			}
			cfchange_found = 1;
Christian Würdig's avatar
Christian Würdig committed
152
		} else if (cfchange_found) {
153
154
155
156
157
158
159
160
161
162
			// 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--;
				}
163
164
			}
		}
165
166
167
168
169
170
171

		// 3. Check for uses
		if(pset_find_ptr(uses, node)) {
			ir_fprintf(stderr, "Verify Warning: Value %+F used before it was defined in block %+F (%s)\n",
				node, block, get_irg_dump_name(env->irg));
			env->problem_found = 1;
		}
172
173
174
175
		if(!is_Phi(node)) {
			for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
				pset_insert_ptr(uses, get_irn_n(node, i));
			}
176
		}
177
	}
178
	del_pset(uses);
179

180
	/* check that all delay branches are filled (at least with NOPs) */
Christian Würdig's avatar
Christian Würdig committed
181
182
	if (cfchange_found && delay_branches != 0) {
		ir_fprintf(stderr, "Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
183
			block, get_irg_dump_name(env->irg));
184
185
186
		env->problem_found = 1;
	}
}
187

Christian Würdig's avatar
Christian Würdig committed
188
189
190
/**
 * Start a walk over the irg and check schedule.
 */
191
int be_verify_schedule(ir_graph *irg)
192
193
194
195
{
	be_verify_schedule_env_t env;

	env.problem_found = 0;
Christian Würdig's avatar
Christian Würdig committed
196
	env.irg           = irg;
197
198
199

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

Christian Würdig's avatar
Christian Würdig committed
200
	return ! env.problem_found;
201
}