beschednormal.c 8.7 KB
Newer Older
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
 */

/**
Matthias Braun's avatar
Matthias Braun committed
7
8
 * @brief   Schedule using the strong normal form theorem (though it does not
 *          hold)
9
10
11
12
 * @author  Christoph Mallon
 */
#include <stdlib.h>

13
#include "besched.h"
14
#include "belistsched.h"
Matthias Braun's avatar
Matthias Braun committed
15
#include "belive.h"
16
#include "beutil.h"
17
#include "heights.h"
18
#include "irgwalk.h"
19
#include "benode.h"
20
#include "bemodule.h"
21
#include "util.h"
22
#include "array.h"
23

Matthias Braun's avatar
Matthias Braun committed
24
#include "irprintf.h"
25
#include "irtools.h"
26

Matthias Braun's avatar
Matthias Braun committed
27
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
Matthias Braun's avatar
Matthias Braun committed
28

Matthias Braun's avatar
Matthias Braun committed
29
30
static struct obstack obst;
static ir_node       *curr_list;
31

Matthias Braun's avatar
Matthias Braun committed
32
33
34
35
36
37
38
39
40
41
42
typedef struct irn_cost_pair {
	ir_node *irn;
	unsigned cost;
} irn_cost_pair;

typedef struct flag_and_cost {
	bool          no_root;
	irn_cost_pair costs[];
} flag_and_cost;

static flag_and_cost *get_irn_flag_and_cost(const ir_node *node)
43
{
Matthias Braun's avatar
Matthias Braun committed
44
45
46
47
48
49
	return (flag_and_cost*)get_irn_link(node);
}

static void set_irn_flag_and_cost(ir_node *node, flag_and_cost *fc)
{
	set_irn_link(node, fc);
50
51
}

Matthias Braun's avatar
Matthias Braun committed
52
53
54
55
static bool must_be_scheduled(const ir_node *const irn)
{
	return !is_Proj(irn) && !arch_irn_is(irn, not_scheduled);
}
56

Matthias Braun's avatar
Matthias Braun committed
57
static ir_node *normal_select(ir_nodeset_t *ready_set)
58
{
Matthias Braun's avatar
Matthias Braun committed
59
	for (ir_node *irn = curr_list, *last = NULL, *next; irn != NULL;
Matthias Braun's avatar
Matthias Braun committed
60
	     last = irn, irn = next) {
61
		next = (ir_node*)get_irn_link(irn);
62
		if (ir_nodeset_contains(ready_set, irn)) {
Matthias Braun's avatar
Matthias Braun committed
63
			DB((dbg, LEVEL_1, "Scheduling %+F\n", irn));
64
			if (last == NULL)
Matthias Braun's avatar
Matthias Braun committed
65
				curr_list = next;
66
67
			else
				set_irn_link(last, next);
68
69
70
71
			return irn;
		}
	}

72
	return ir_nodeset_first(ready_set);
73
74
}

Matthias Braun's avatar
Matthias Braun committed
75
static int cost_cmp(const void *a, const void *b)
76
{
Matthias Braun's avatar
Matthias Braun committed
77
78
	const irn_cost_pair *const a1 = (const irn_cost_pair*)a;
	const irn_cost_pair *const b1 = (const irn_cost_pair*)b;
Matthias Braun's avatar
Matthias Braun committed
79
	int ret = (int)b1->cost - (int)a1->cost;
80
81
	if (ret == 0)
		ret = (int)get_irn_idx(a1->irn) - (int)get_irn_idx(b1->irn);
82
	return ret;
83
84
}

Matthias Braun's avatar
Matthias Braun committed
85
static unsigned count_result(const ir_node *irn)
86
{
Matthias Braun's avatar
Matthias Braun committed
87
	const ir_mode *mode = get_irn_mode(irn);
88
89
	if (mode == mode_M || mode == mode_X)
		return 0;
90
91
92
	if (mode == mode_T)
		return 1;

93
	arch_register_req_t const *const req = arch_get_irn_register_req(irn);
Matthias Braun's avatar
Matthias Braun committed
94
	return arch_register_req_is(req, ignore) ? 0 : 1;
95
96
}

Matthias Braun's avatar
Matthias Braun committed
97
static unsigned normal_tree_cost(ir_node *irn)
98
{
Matthias Braun's avatar
Matthias Braun committed
99
	/* TODO: high cost for store trees */
100
101
	if (be_is_Keep(irn))
		return 0;
Matthias Braun's avatar
Matthias Braun committed
102
	if (is_Proj(irn))
Matthias Braun's avatar
Matthias Braun committed
103
		return normal_tree_cost(get_Proj_pred(irn));
Michael Beck's avatar
Michael Beck committed
104

Matthias Braun's avatar
Matthias Braun committed
105
	int            arity = get_irn_arity(irn);
Matthias Braun's avatar
Matthias Braun committed
106
	flag_and_cost *fc    = get_irn_flag_and_cost(irn);
107
	if (fc == NULL) {
Matthias Braun's avatar
Matthias Braun committed
108
		ir_node *block = get_nodes_block(irn);
109

Matthias Braun's avatar
Matthias Braun committed
110
		fc = OALLOCF(&obst, flag_and_cost, costs, arity);
Matthias Braun's avatar
Matthias Braun committed
111
112
		fc->no_root = false;
		irn_cost_pair *costs = fc->costs;
113

114
		foreach_irn_in(irn, i, pred) {
Matthias Braun's avatar
Matthias Braun committed
115
			unsigned cost;
116
			if (is_Phi(irn) || get_irn_mode(pred) == mode_M) {
117
118
119
120
				cost = 0;
			} else if (get_nodes_block(pred) != block) {
				cost = 1;
			} else {
Matthias Braun's avatar
Matthias Braun committed
121
				cost = normal_tree_cost(pred);
122
				if (!arch_irn_is_ignore(pred)) {
Matthias Braun's avatar
Matthias Braun committed
123
124
					ir_node       *real_pred = is_Proj(pred)
					                         ? get_Proj_pred(pred) : pred;
Matthias Braun's avatar
Matthias Braun committed
125
					flag_and_cost *pred_fc = get_irn_flag_and_cost(real_pred);
Matthias Braun's avatar
Matthias Braun committed
126
					pred_fc->no_root = true;
Matthias Braun's avatar
Matthias Braun committed
127
128
					DB((dbg, LEVEL_1, "%+F says that %+F is no root\n", irn,
					    real_pred));
129
				}
130
131
132
133
134
135
			}

			costs[i].irn  = pred;
			costs[i].cost = cost;
		}

136
		QSORT(costs, arity, cost_cmp);
Matthias Braun's avatar
Matthias Braun committed
137
		set_irn_flag_and_cost(irn, fc);
138
139
	}

Matthias Braun's avatar
Matthias Braun committed
140
141
142
	unsigned cost     = 0;
	unsigned n_op_res = 0;
	ir_node *last     = 0;
143
	for (int i = 0; i < arity; ++i) {
Matthias Braun's avatar
Matthias Braun committed
144
		ir_node *op = fc->costs[i].irn;
145
146
		if (op == last)
			continue;
Matthias Braun's avatar
Matthias Braun committed
147
		ir_mode *mode = get_irn_mode(op);
Matthias Braun's avatar
Matthias Braun committed
148
		if (mode == mode_M || arch_irn_is_ignore(op))
149
			continue;
Christoph Mallon's avatar
Christoph Mallon committed
150
		cost = MAX(fc->costs[i].cost + n_op_res, cost);
151
		last = op;
Christoph Mallon's avatar
Christoph Mallon committed
152
		++n_op_res;
153
	}
Matthias Braun's avatar
Matthias Braun committed
154
	unsigned n_res = count_result(irn);
Christoph Mallon's avatar
Christoph Mallon committed
155
	cost = MAX(n_res, cost);
156

Matthias Braun's avatar
Matthias Braun committed
157
	DB((dbg, LEVEL_1, "reguse of %+F is %u\n", irn, cost));
158
159
160
	return cost;
}

Matthias Braun's avatar
Matthias Braun committed
161
static void normal_cost_walker(ir_node *irn, void *data)
162
{
Matthias Braun's avatar
Matthias Braun committed
163
	(void)data;
Matthias Braun's avatar
Matthias Braun committed
164
	DB((dbg, LEVEL_1, "cost walking node %+F\n", irn));
165
166
167
168
169
	if (is_Block(irn)) {
		ir_node **const roots = NEW_ARR_F(ir_node*, 0);
		set_irn_link(irn, roots);
		return;
	}
Matthias Braun's avatar
Matthias Braun committed
170
171
	if (!must_be_scheduled(irn))
		return;
Matthias Braun's avatar
Matthias Braun committed
172
	normal_tree_cost(irn);
173
174
}

Matthias Braun's avatar
Matthias Braun committed
175
static void collect_roots(ir_node *irn, void *env)
176
177
{
	(void)env;
Matthias Braun's avatar
Matthias Braun committed
178
179
	if (!must_be_scheduled(irn))
		return;
180

Matthias Braun's avatar
Matthias Braun committed
181
182
	bool is_root = be_is_Keep(irn) || !get_irn_flag_and_cost(irn)->no_root;
	DB((dbg, LEVEL_1, "%+F is %sroot\n", irn, is_root ? "" : "no "));
183
	if (is_root) {
Matthias Braun's avatar
Matthias Braun committed
184
185
		ir_node  *block = get_nodes_block(irn);
		ir_node **roots = (ir_node**)get_irn_link(block);
186
187
188
189
190
		ARR_APP1(ir_node*, roots, irn);
		set_irn_link(block, roots);
	}
}

Matthias Braun's avatar
Matthias Braun committed
191
static ir_node **sched_node(ir_node **sched, ir_node *irn)
192
{
Matthias Braun's avatar
Matthias Braun committed
193
194
	if (irn_visited_else_mark(irn))
		return sched;
195

196
	if (!is_Phi(irn) && !be_is_Keep(irn)) {
Matthias Braun's avatar
Matthias Braun committed
197
		ir_node       *block = get_nodes_block(irn);
Matthias Braun's avatar
Matthias Braun committed
198
		flag_and_cost *fc    = get_irn_flag_and_cost(irn);
Matthias Braun's avatar
Matthias Braun committed
199
200
201
202
203
204
205
206
207
208
		irn_cost_pair *irns  = fc->costs;

		for (int i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
			ir_node *pred = irns[i].irn;
			if (get_nodes_block(pred) != block)
				continue;
			if (get_irn_mode(pred) == mode_M)
				continue;
			if (is_Proj(pred))
				pred = get_Proj_pred(pred);
209
210
211
212
213
214
215
216
			sched = sched_node(sched, pred);
		}
	}

	ARR_APP1(ir_node*, sched, irn);
	return sched;
}

Matthias Braun's avatar
Matthias Braun committed
217
static int root_cmp(const void *a, const void *b)
218
{
Matthias Braun's avatar
Matthias Braun committed
219
220
	const irn_cost_pair *const a1 = (const irn_cost_pair*)a;
	const irn_cost_pair *const b1 = (const irn_cost_pair*)b;
221
	int ret;
222
	if (is_irn_forking(a1->irn) && !is_irn_forking(b1->irn)) {
223
		ret = 1;
224
	} else if (is_irn_forking(b1->irn) && !is_irn_forking(a1->irn)) {
225
226
		ret = -1;
	} else {
Matthias Braun's avatar
Matthias Braun committed
227
		ret = (int)b1->cost - (int)a1->cost;
228
229
230
		if (ret == 0) {
			/* place live-out nodes later */
			ret = (count_result(a1->irn) != 0) - (count_result(b1->irn) != 0);
Matthias Braun's avatar
Matthias Braun committed
231
232
			/* compare node idx */
			if (ret == 0)
233
				ret = get_irn_idx(a1->irn) - get_irn_idx(b1->irn);
234
235
		}
	}
Matthias Braun's avatar
Matthias Braun committed
236
237
	DB((dbg, LEVEL_1, "root %+F %s %+F\n", a1->irn,
	    ret < 0 ? "<" : ret > 0 ? ">" : "=", b1->irn));
238
239
240
	return ret;
}

Matthias Braun's avatar
Matthias Braun committed
241
static void normal_sched_block(ir_node *block, void *env)
242
{
Matthias Braun's avatar
Matthias Braun committed
243
244
	ir_node     **roots   = (ir_node**)get_irn_link(block);
	ir_heights_t *heights = (ir_heights_t*)env;
245

Matthias Braun's avatar
Matthias Braun committed
246
	DB((dbg, LEVEL_1, "sched walking block %+F\n", block));
247

248
249
	int const root_count = ARR_LEN(roots);
	if (root_count == 0) {
Matthias Braun's avatar
Matthias Braun committed
250
		DB((dbg, LEVEL_1, "has no roots\n"));
251
252
253
		return;
	}

254
	irn_cost_pair *root_costs = ALLOCAN(irn_cost_pair, root_count);
Matthias Braun's avatar
Matthias Braun committed
255
	for (int i = 0; i < root_count; ++i) {
256
		root_costs[i].irn  = roots[i];
257
		root_costs[i].cost = get_irn_height(heights, roots[i]);
Matthias Braun's avatar
Matthias Braun committed
258
259
		DB((dbg, LEVEL_1, "height of %+F is %u\n", roots[i],
		    root_costs[i].cost));
260
	}
261
	QSORT(root_costs, root_count, root_cmp);
Matthias Braun's avatar
Matthias Braun committed
262
263
#ifdef DEBUG_libfirm
	DB((dbg, LEVEL_1, "Root Scheduling of %+F:\n", block));
Matthias Braun's avatar
Matthias Braun committed
264
	for (int i = 0, n = root_count; i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
265
		DB((dbg, LEVEL_1, "  %+F\n", root_costs[i].irn));
266
	}
Matthias Braun's avatar
Matthias Braun committed
267
	DB((dbg, LEVEL_1, "\n"));
268
#endif
269

Matthias Braun's avatar
Matthias Braun committed
270
271
272
	ir_node **sched = NEW_ARR_F(ir_node*, 0);
	for (int i = 0; i < root_count; ++i) {
		ir_node *irn = root_costs[i].irn;
273
		assert(must_be_scheduled(irn));
274
275
		sched = sched_node(sched, irn);
	}
Michael Beck's avatar
Michael Beck committed
276
	set_irn_link(block, sched);
277
	DEL_ARR_F(roots);
278

Matthias Braun's avatar
Matthias Braun committed
279
280
#ifdef DEBUG_libfirm
	DB((dbg, LEVEL_1, "Scheduling of %+F:\n", block));
Matthias Braun's avatar
Matthias Braun committed
281
	for (int i = 0, n = ARR_LEN(sched); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
282
		DB((dbg, LEVEL_1, "  %+F\n", sched[i]));
283
	}
Matthias Braun's avatar
Matthias Braun committed
284
	DB((dbg, LEVEL_1, "\n"));
285
286
287
#endif
}

Matthias Braun's avatar
Matthias Braun committed
288
static void real_sched_block(ir_node *block, void *data)
289
{
Matthias Braun's avatar
Matthias Braun committed
290
291
292
	(void)data;
	ir_node **sched = (ir_node**)get_irn_link(block);
	ir_node  *first = NULL;
293

Matthias Braun's avatar
Matthias Braun committed
294
295
	/* turn into a list, so we can easily remove nodes. The link field is used
	 * anyway. */
Matthias Braun's avatar
Matthias Braun committed
296
297
	for (int i = ARR_LEN(sched); i-- > 0; ) {
		ir_node *irn = sched[i];
298
		if (!is_cfop(irn)) {
299
300
301
302
303
			set_irn_link(irn, first);
			first = irn;
		}
	}
	/* note: we can free sched here, there should be no attempt to schedule
Matthias Braun's avatar
Matthias Braun committed
304
	 * a block twice */
305
306
	DEL_ARR_F(sched);
	set_irn_link(block, sched);
Matthias Braun's avatar
Matthias Braun committed
307
	curr_list = first;
308

Matthias Braun's avatar
Matthias Braun committed
309
310
311
312
313
314
	ir_nodeset_t *cands = be_list_sched_begin_block(block);
	while (ir_nodeset_size(cands) > 0) {
		ir_node *node = normal_select(cands);
		be_list_sched_schedule(node);
	}
	be_list_sched_end_block();
Michael Beck's avatar
Michael Beck committed
315
}
316

317
318
static void sched_normal(ir_graph *irg)
{
Matthias Braun's avatar
Matthias Braun committed
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
	/* block uses the link field to store the schedule */
	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);

	obstack_init(&obst);

	irg_walk_graph(irg, firm_clear_link, NULL, NULL);
	irg_walk_graph(irg, normal_cost_walker,  NULL, NULL);
	irg_walk_graph(irg, collect_roots, NULL, NULL);
	ir_heights_t *heights = heights_new(irg);
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
	inc_irg_visited(irg);
	irg_block_walk_graph(irg, normal_sched_block, NULL, heights);
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
	heights_free(heights);

	be_list_sched_begin(irg);
	irg_block_walk_graph(irg, real_sched_block, NULL, NULL);
	be_list_sched_finish();

	ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
	obstack_free(&obst, NULL);
340
341
}

Matthias Braun's avatar
Matthias Braun committed
342
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched_normal)
343
344
345
void be_init_sched_normal(void)
{
	be_register_scheduler("normal", sched_normal);
Matthias Braun's avatar
Matthias Braun committed
346
	FIRM_DBG_REGISTER(dbg, "firm.be.sched.normal");
347
}