beschednormal.c 8.53 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 "heights.h"
17
#include "irgwalk.h"
18
#include "benode.h"
19
#include "bemodule.h"
20
#include "util.h"
21
#include "array.h"
22

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

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

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

Matthias Braun's avatar
Matthias Braun committed
31
32
33
34
35
36
37
38
39
40
41
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)
42
{
Matthias Braun's avatar
Matthias Braun committed
43
44
45
46
47
48
	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);
49
50
}

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

66
	return ir_nodeset_first(ready_set);
67
68
}

Matthias Braun's avatar
Matthias Braun committed
69
static int cost_cmp(const void *a, const void *b)
70
{
Matthias Braun's avatar
Matthias Braun committed
71
72
	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
73
	int ret = (int)b1->cost - (int)a1->cost;
74
75
	if (ret == 0)
		ret = (int)get_irn_idx(a1->irn) - (int)get_irn_idx(b1->irn);
76
	return ret;
77
78
}

Matthias Braun's avatar
Matthias Braun committed
79
static unsigned count_result(const ir_node *irn)
80
{
Matthias Braun's avatar
Matthias Braun committed
81
	const ir_mode *mode = get_irn_mode(irn);
82
83
	if (mode == mode_M || mode == mode_X)
		return 0;
84
85
86
	if (mode == mode_T)
		return 1;

87
	arch_register_req_t const *const req = arch_get_irn_register_req(irn);
Matthias Braun's avatar
Matthias Braun committed
88
	return arch_register_req_is(req, ignore) ? 0 : 1;
89
90
}

Matthias Braun's avatar
Matthias Braun committed
91
static unsigned normal_tree_cost(ir_node *irn)
92
{
Matthias Braun's avatar
Matthias Braun committed
93
	/* TODO: high cost for store trees */
94
95
	if (be_is_Keep(irn))
		return 0;
Matthias Braun's avatar
Matthias Braun committed
96
	if (is_Proj(irn))
Matthias Braun's avatar
Matthias Braun committed
97
		return normal_tree_cost(get_Proj_pred(irn));
Michael Beck's avatar
Michael Beck committed
98

Matthias Braun's avatar
Matthias Braun committed
99
	int            arity = get_irn_arity(irn);
Matthias Braun's avatar
Matthias Braun committed
100
	flag_and_cost *fc    = get_irn_flag_and_cost(irn);
101
	if (fc == NULL) {
Matthias Braun's avatar
Matthias Braun committed
102
		ir_node *block = get_nodes_block(irn);
103

Matthias Braun's avatar
Matthias Braun committed
104
		fc = OALLOCF(&obst, flag_and_cost, costs, arity);
Matthias Braun's avatar
Matthias Braun committed
105
106
		fc->no_root = false;
		irn_cost_pair *costs = fc->costs;
107

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

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

130
		QSORT(costs, arity, cost_cmp);
Matthias Braun's avatar
Matthias Braun committed
131
		set_irn_flag_and_cost(irn, fc);
132
133
	}

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

Matthias Braun's avatar
Matthias Braun committed
151
	DB((dbg, LEVEL_1, "reguse of %+F is %u\n", irn, cost));
152
153
154
	return cost;
}

Matthias Braun's avatar
Matthias Braun committed
155
static void normal_cost_walker(ir_node *irn, void *data)
156
{
Matthias Braun's avatar
Matthias Braun committed
157
	(void)data;
Matthias Braun's avatar
Matthias Braun committed
158
	DB((dbg, LEVEL_1, "cost walking node %+F\n", irn));
159
160
161
162
163
	if (is_Block(irn)) {
		ir_node **const roots = NEW_ARR_F(ir_node*, 0);
		set_irn_link(irn, roots);
		return;
	}
164
	if (arch_is_irn_not_scheduled(irn))
Matthias Braun's avatar
Matthias Braun committed
165
		return;
Matthias Braun's avatar
Matthias Braun committed
166
	normal_tree_cost(irn);
167
168
}

Matthias Braun's avatar
Matthias Braun committed
169
static void collect_roots(ir_node *irn, void *env)
170
171
{
	(void)env;
172
	if (arch_is_irn_not_scheduled(irn))
Matthias Braun's avatar
Matthias Braun committed
173
		return;
174

Matthias Braun's avatar
Matthias Braun committed
175
176
	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 "));
177
	if (is_root) {
Matthias Braun's avatar
Matthias Braun committed
178
179
		ir_node  *block = get_nodes_block(irn);
		ir_node **roots = (ir_node**)get_irn_link(block);
180
181
182
183
184
		ARR_APP1(ir_node*, roots, irn);
		set_irn_link(block, roots);
	}
}

Matthias Braun's avatar
Matthias Braun committed
185
static ir_node **sched_node(ir_node **sched, ir_node *irn)
186
{
Matthias Braun's avatar
Matthias Braun committed
187
188
	if (irn_visited_else_mark(irn))
		return sched;
189

190
	if (!is_Phi(irn) && !be_is_Keep(irn)) {
Matthias Braun's avatar
Matthias Braun committed
191
		ir_node       *block = get_nodes_block(irn);
Matthias Braun's avatar
Matthias Braun committed
192
		flag_and_cost *fc    = get_irn_flag_and_cost(irn);
Matthias Braun's avatar
Matthias Braun committed
193
194
195
196
197
198
199
200
201
202
		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);
203
204
205
206
207
208
209
210
			sched = sched_node(sched, pred);
		}
	}

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

Matthias Braun's avatar
Matthias Braun committed
211
static int root_cmp(const void *a, const void *b)
212
{
Matthias Braun's avatar
Matthias Braun committed
213
214
	const irn_cost_pair *const a1 = (const irn_cost_pair*)a;
	const irn_cost_pair *const b1 = (const irn_cost_pair*)b;
215
	int ret;
216
	if (is_cfop(a1->irn) && !is_cfop(b1->irn)) {
217
		ret = 1;
218
	} else if (is_cfop(b1->irn) && !is_cfop(a1->irn)) {
219
220
		ret = -1;
	} else {
Matthias Braun's avatar
Matthias Braun committed
221
		ret = (int)b1->cost - (int)a1->cost;
222
223
224
		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
225
226
			/* compare node idx */
			if (ret == 0)
227
				ret = get_irn_idx(a1->irn) - get_irn_idx(b1->irn);
228
229
		}
	}
Matthias Braun's avatar
Matthias Braun committed
230
231
	DB((dbg, LEVEL_1, "root %+F %s %+F\n", a1->irn,
	    ret < 0 ? "<" : ret > 0 ? ">" : "=", b1->irn));
232
233
234
	return ret;
}

Matthias Braun's avatar
Matthias Braun committed
235
static void normal_sched_block(ir_node *block, void *env)
236
{
Matthias Braun's avatar
Matthias Braun committed
237
238
	ir_node     **roots   = (ir_node**)get_irn_link(block);
	ir_heights_t *heights = (ir_heights_t*)env;
239

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

242
243
	int const root_count = ARR_LEN(roots);
	if (root_count == 0) {
Matthias Braun's avatar
Matthias Braun committed
244
		DB((dbg, LEVEL_1, "has no roots\n"));
245
246
247
		return;
	}

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

Matthias Braun's avatar
Matthias Braun committed
264
265
266
	ir_node **sched = NEW_ARR_F(ir_node*, 0);
	for (int i = 0; i < root_count; ++i) {
		ir_node *irn = root_costs[i].irn;
267
		assert(!arch_is_irn_not_scheduled(irn));
268
269
		sched = sched_node(sched, irn);
	}
Michael Beck's avatar
Michael Beck committed
270
	set_irn_link(block, sched);
271
	DEL_ARR_F(roots);
272

Matthias Braun's avatar
Matthias Braun committed
273
274
#ifdef DEBUG_libfirm
	DB((dbg, LEVEL_1, "Scheduling of %+F:\n", block));
Matthias Braun's avatar
Matthias Braun committed
275
	for (int i = 0, n = ARR_LEN(sched); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
276
		DB((dbg, LEVEL_1, "  %+F\n", sched[i]));
277
	}
Matthias Braun's avatar
Matthias Braun committed
278
	DB((dbg, LEVEL_1, "\n"));
279
280
281
#endif
}

Matthias Braun's avatar
Matthias Braun committed
282
static void real_sched_block(ir_node *block, void *data)
283
{
Matthias Braun's avatar
Matthias Braun committed
284
285
286
	(void)data;
	ir_node **sched = (ir_node**)get_irn_link(block);
	ir_node  *first = NULL;
287

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

Matthias Braun's avatar
Matthias Braun committed
301
302
303
304
305
306
	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
307
}
308

309
310
static void sched_normal(ir_graph *irg)
{
Matthias Braun's avatar
Matthias Braun committed
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
	/* 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);
332
333
}

Matthias Braun's avatar
Matthias Braun committed
334
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched_normal)
335
336
337
void be_init_sched_normal(void)
{
	be_register_scheduler("normal", sched_normal);
Matthias Braun's avatar
Matthias Braun committed
338
	FIRM_DBG_REGISTER(dbg, "firm.be.sched.normal");
339
}