benode.c 15.3 KB
Newer Older
Sebastian Hack's avatar
Sebastian Hack committed
1
2
3
4
5
6
7
/**
 * @file   benode.c
 * @date   17.05.2005
 * @author Sebastian Hack
 *
 * Backend node support.
 *
8
9
 * This file provdies Perm, Copy, Spill and Reload nodes.
 *
Sebastian Hack's avatar
Sebastian Hack committed
10
11
12
 * Copyright (C) 2005 Universitaet Karlsruhe
 * Released under the GPL
 */
13

Michael Beck's avatar
Michael Beck committed
14
15
16
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
Sebastian Hack's avatar
Sebastian Hack committed
17
18
19
20
21
22

#include <stdlib.h>

#include "obst.h"
#include "set.h"
#include "pmap.h"
23
#include "util.h"
Sebastian Hack's avatar
Sebastian Hack committed
24
#include "debug.h"
25
#include "fourcc.h"
Sebastian Hack's avatar
Sebastian Hack committed
26
27
28
29

#include "irop_t.h"
#include "irmode_t.h"
#include "irnode_t.h"
30
#include "ircons_t.h"
31
#include "irprintf.h"
Sebastian Hack's avatar
Sebastian Hack committed
32

33
34
35
#include "be_t.h"
#include "belive_t.h"
#include "besched_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
36
37
#include "benode_t.h"

38
39
#include "beirgmod.h"

Sebastian Hack's avatar
Sebastian Hack committed
40
41
/* Sometimes we want to put const nodes into get_irn_generic_attr ... */
#define get_irn_attr(irn) get_irn_generic_attr((ir_node *) (irn))
Daniel Grund's avatar
Daniel Grund committed
42

Sebastian Hack's avatar
Sebastian Hack committed
43
static unsigned be_node_tag = FOURCC('B', 'E', 'N', 'O');
44

Sebastian Hack's avatar
Sebastian Hack committed
45
typedef enum _node_kind_t {
Christian Würdig's avatar
Christian Würdig committed
46
47
48
49
	node_kind_spill,
	node_kind_reload,
	node_kind_perm,
	node_kind_copy,
Sebastian Hack's avatar
Sebastian Hack committed
50
	node_kind_kill,
Christian Würdig's avatar
Christian Würdig committed
51
	node_kind_last
Sebastian Hack's avatar
Sebastian Hack committed
52
53
54
} node_kind_t;

typedef struct {
Christian Würdig's avatar
Christian Würdig committed
55
56
57
58
59
	node_kind_t kind;
	const arch_register_class_t *cls;
	ir_op *op;
	int n_pos;
	int *pos;
Sebastian Hack's avatar
Sebastian Hack committed
60
61
} be_op_t;

Sebastian Hack's avatar
Sebastian Hack committed
62
63
64
65
66
67
68
typedef struct {
	arch_register_req_t req;
	unsigned            negate_limited : 1;
	void                (*old_limited)(void *ptr, bitset_t *bs);
	void                *old_limited_env;
} be_req_t;

69
typedef struct {
70
	const arch_register_t *reg;
Sebastian Hack's avatar
Sebastian Hack committed
71
	be_req_t              req;
72
73
74
} be_reg_data_t;

typedef struct {
Sebastian Hack's avatar
Sebastian Hack committed
75
76
77
	int                         n_outs;
	const arch_register_class_t *cls;
	be_reg_data_t               *reg_data;
78
79
80
} be_node_attr_t;

typedef struct {
Sebastian Hack's avatar
Sebastian Hack committed
81
	be_node_attr_t node_attr;
82
	ir_node *spill_ctx;  /**< The node in whose context this spill was introduced. */
83
	entity *ent;     /**< The entity in the stack frame the spill writes to. */
84
85
} be_spill_attr_t;

Sebastian Hack's avatar
Sebastian Hack committed
86
87
88
89
90
static ir_op *op_Spill;
static ir_op *op_Reload;
static ir_op *op_Perm;
static ir_op *op_Copy;
static ir_op *op_Keep;
Sebastian Hack's avatar
Sebastian Hack committed
91

Sebastian Hack's avatar
Sebastian Hack committed
92
static int beo_base = -1;
Sebastian Hack's avatar
Sebastian Hack committed
93

Sebastian Hack's avatar
Sebastian Hack committed
94
static const ir_op_ops be_node_op_ops;
Sebastian Hack's avatar
Sebastian Hack committed
95

Sebastian Hack's avatar
Sebastian Hack committed
96
97
98
void be_node_init(void) {
	static int inited = 0;
	int i;
Sebastian Hack's avatar
Sebastian Hack committed
99

Sebastian Hack's avatar
Sebastian Hack committed
100
101
	if(inited)
		return;
Sebastian Hack's avatar
Sebastian Hack committed
102

Sebastian Hack's avatar
Sebastian Hack committed
103
	inited = 1;
Sebastian Hack's avatar
Sebastian Hack committed
104

Sebastian Hack's avatar
Sebastian Hack committed
105
	beo_base = get_next_ir_opcode();
Sebastian Hack's avatar
Sebastian Hack committed
106

Sebastian Hack's avatar
Sebastian Hack committed
107
108
109
	/* Acquire all needed opcodes. We assume that they are consecutive! */
	for(i = beo_Spill; i < beo_Last; ++i)
		get_next_ir_opcode();
Sebastian Hack's avatar
Sebastian Hack committed
110

Sebastian Hack's avatar
Sebastian Hack committed
111
112
113
114
115
	op_Spill  = new_ir_op(beo_base + beo_Spill,  "Spill",  op_pin_state_mem_pinned, 0, oparity_unary,    0, sizeof(be_spill_attr_t), &be_node_op_ops);
	op_Reload = new_ir_op(beo_base + beo_Reload, "Reload", op_pin_state_mem_pinned, 0, oparity_zero,     0, sizeof(be_node_attr_t),  &be_node_op_ops);
	op_Perm   = new_ir_op(beo_base + beo_Perm,   "Perm",   op_pin_state_pinned,     0, oparity_variable, 0, sizeof(be_node_attr_t),  &be_node_op_ops);
	op_Copy   = new_ir_op(beo_base + beo_Copy,   "Copy",   op_pin_state_pinned,     0, oparity_unary,    0, sizeof(be_node_attr_t),  &be_node_op_ops);
	op_Keep   = new_ir_op(beo_base + beo_Keep,   "Keep",   op_pin_state_pinned,     0, oparity_variable, 0, sizeof(be_node_attr_t),  &be_node_op_ops);
Sebastian Hack's avatar
Sebastian Hack committed
116

Sebastian Hack's avatar
Sebastian Hack committed
117
118
119
120
121
122
	set_op_tag(op_Spill,  &be_node_tag);
	set_op_tag(op_Reload, &be_node_tag);
	set_op_tag(op_Perm,   &be_node_tag);
	set_op_tag(op_Copy,   &be_node_tag);
	set_op_tag(op_Keep,   &be_node_tag);
}
123

Sebastian Hack's avatar
Sebastian Hack committed
124
125
126
127
128
129
130
131
132
133
134
135
136
137
static void *init_node_attr(ir_node* irn, const arch_register_class_t *cls, ir_graph *irg, int n_outs)
{
	be_node_attr_t *a = get_irn_attr(irn);

	a->n_outs   = n_outs;
	a->cls      = cls;
	a->reg_data = NULL;

	if(n_outs > 0) {
		int i;

		a->reg_data = NEW_ARR_D(be_reg_data_t, get_irg_obstack(irg), n_outs);
		memset(a->reg_data, 0, n_outs * sizeof(a->reg_data[0]));
		for(i = 0; i < n_outs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
138
139
			a->reg_data[i].req.req.cls  = cls;
			a->reg_data[i].req.req.type = arch_register_req_type_normal;
Sebastian Hack's avatar
Sebastian Hack committed
140
141
142
143
144
		}
	}

	return a;
}
145

146
147
static INLINE int is_be_node(const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
148
	return get_op_tag(get_irn_op(irn)) == &be_node_tag;
149
150
}

Sebastian Hack's avatar
Sebastian Hack committed
151
be_opcode_t get_irn_be_opcode(const ir_node *irn)
152
{
Sebastian Hack's avatar
Sebastian Hack committed
153
	return is_be_node(irn) ? get_irn_opcode(irn) - beo_base : beo_NoBeOp;
154
155
}

Sebastian Hack's avatar
Sebastian Hack committed
156
ir_node *be_new_Spill(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *to_spill, ir_node *ctx)
157
{
Sebastian Hack's avatar
Sebastian Hack committed
158
159
160
	be_spill_attr_t *a;
	ir_node *in[1];
	ir_node *res;
161

Sebastian Hack's avatar
Sebastian Hack committed
162
163
164
	in[0] = to_spill;
	res   = new_ir_node(NULL, irg, bl, op_Spill, mode_M, 1, in);
	a     = init_node_attr(res, cls, irg, 0);
Sebastian Hack's avatar
Sebastian Hack committed
165
	a->ent       = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
166
167
168
	a->spill_ctx = ctx;
	return res;
}
169

Sebastian Hack's avatar
Sebastian Hack committed
170
ir_node *be_new_Reload(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_mode *mode, ir_node *mem)
171
{
Sebastian Hack's avatar
Sebastian Hack committed
172
173
	ir_node *in[1];
	ir_node *res;
174

Sebastian Hack's avatar
Sebastian Hack committed
175
176
177
178
179
	in[0] = mem;
	res   = new_ir_node(NULL, irg, bl, op_Reload, mode, 1, in);
	init_node_attr(res, cls, irg, 1);
	return res;
}
180

Sebastian Hack's avatar
Sebastian Hack committed
181
182
183
184
185
186
ir_node *be_new_Perm(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
{
	ir_node *irn = new_ir_node(NULL, irg, bl, op_Perm, mode_T, n, in);
	init_node_attr(irn, cls, irg, n);
	return irn;
}
187

Sebastian Hack's avatar
Sebastian Hack committed
188
189
190
191
ir_node *be_new_Copy(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *op)
{
	ir_node *in[1];
	ir_node *res;
192

Sebastian Hack's avatar
Sebastian Hack committed
193
194
195
196
	in[0] = op;
	res   = new_ir_node(NULL, irg, bl, op_Copy, get_irn_mode(op), 1, in);
	init_node_attr(res, cls, irg, 1);
	return res;
197
198
}

Sebastian Hack's avatar
Sebastian Hack committed
199
ir_node *be_new_Keep(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
Sebastian Hack's avatar
Sebastian Hack committed
200
{
Sebastian Hack's avatar
Sebastian Hack committed
201
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
202

Sebastian Hack's avatar
Sebastian Hack committed
203
204
205
206
	irn = new_ir_node(NULL, irg, bl, op_Keep, mode_ANY, n, in);
	init_node_attr(irn, cls, irg, 0);
	keep_alive(irn);
	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
207
208
}

Sebastian Hack's avatar
Sebastian Hack committed
209
int be_is_Spill(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
210
{
Sebastian Hack's avatar
Sebastian Hack committed
211
212
	return get_irn_be_opcode(irn) == beo_Spill;
}
Sebastian Hack's avatar
Sebastian Hack committed
213

Sebastian Hack's avatar
Sebastian Hack committed
214
215
216
int be_is_Reload(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Reload;
Sebastian Hack's avatar
Sebastian Hack committed
217
218
}

Sebastian Hack's avatar
Sebastian Hack committed
219
220
221
222
int be_is_Copy(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Copy;
}
Sebastian Hack's avatar
Sebastian Hack committed
223

Sebastian Hack's avatar
Sebastian Hack committed
224
225
226
227
int be_is_Perm(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Perm;
}
Sebastian Hack's avatar
Sebastian Hack committed
228

Sebastian Hack's avatar
Sebastian Hack committed
229
int be_is_Keep(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
230
{
Sebastian Hack's avatar
Sebastian Hack committed
231
232
	return get_irn_be_opcode(irn) == beo_Keep;
}
Sebastian Hack's avatar
Sebastian Hack committed
233

Sebastian Hack's avatar
Sebastian Hack committed
234
static void be_limited(void *data, bitset_t *bs)
Sebastian Hack's avatar
Sebastian Hack committed
235
{
Sebastian Hack's avatar
Sebastian Hack committed
236
237
238
239
240
241
242
243
244
245
246
	be_req_t *req = data;

	req->old_limited(req->old_limited_env, bs);
	if(req->negate_limited)
		bitset_flip_all(bs);
}

void be_set_Perm_out_req(ir_node *irn, int pos, const arch_register_req_t *req, unsigned negate_limited)
{
	be_node_attr_t *a   = get_irn_attr(irn);
	be_req_t       *r = &a->reg_data[pos].req;
Sebastian Hack's avatar
Sebastian Hack committed
247

Sebastian Hack's avatar
Sebastian Hack committed
248
249
	assert(be_is_Perm(irn));
	assert(pos >= 0 && pos < get_irn_arity(irn));
Sebastian Hack's avatar
Sebastian Hack committed
250
251
252
253
254
255
256
257
258
	memcpy(&r->req, req, sizeof(req[0]));

	if(arch_register_req_is(req, limited)) {
		r->old_limited     = r->req.limited;
		r->old_limited_env = r->req.limited_env;
		r->req.limited     = be_limited;
		r->req.limited_env = r;
		r->negate_limited  = negate_limited;
	}
Sebastian Hack's avatar
Sebastian Hack committed
259
260
}

261
void be_set_Spill_entity(ir_node *irn, entity *ent)
262
{
Sebastian Hack's avatar
Sebastian Hack committed
263
264
	be_spill_attr_t *a = get_irn_attr(irn);
	assert(be_is_Spill(irn));
265
	a->ent = ent;
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
}

static ir_node *find_a_spill_walker(ir_node *irn, unsigned visited_nr)
{
	if(get_irn_visited(irn) < visited_nr) {
		set_irn_visited(irn, visited_nr);

		if(is_Phi(irn)) {
			int i, n;
			for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
				ir_node *n = find_a_spill_walker(get_irn_n(irn, i), visited_nr);
				if(n != NULL)
					return n;
			}
		}

Sebastian Hack's avatar
Sebastian Hack committed
282
		else if(get_irn_be_opcode(irn) == beo_Spill)
283
284
285
286
287
288
			return irn;
	}

	return NULL;
}

Sebastian Hack's avatar
Sebastian Hack committed
289
290
291
ir_node *be_get_Spill_context(const ir_node *irn) {
	const be_spill_attr_t *a = get_irn_attr(irn);
	assert(be_is_Spill(irn));
292
293
294
	return a->spill_ctx;
}

295
296
297
298
299
300
301
302
303
304
305
/**
 * Finds a spill for a reload.
 * If the reload is directly using the spill, this is simple,
 * else we perform DFS from the reload (over all PhiMs) and return
 * the first spill node we find.
 */
static INLINE ir_node *find_a_spill(ir_node *irn)
{
	ir_graph *irg       = get_irn_irg(irn);
	unsigned visited_nr = get_irg_visited(irg) + 1;

Sebastian Hack's avatar
Sebastian Hack committed
306
	assert(be_is_Reload(irn));
307
308
309
310
	set_irg_visited(irg, visited_nr);
	return find_a_spill_walker(irn, visited_nr);
}

311
entity *be_get_spill_entity(ir_node *irn)
312
{
Sebastian Hack's avatar
Sebastian Hack committed
313
	int opc           = get_irn_opcode(irn);
314

Sebastian Hack's avatar
Sebastian Hack committed
315
316
	switch(get_irn_be_opcode(irn)) {
	case beo_Reload:
317
		return be_get_spill_entity(find_a_spill(irn));
Sebastian Hack's avatar
Sebastian Hack committed
318
319
320
	case beo_Spill:
		{
			be_spill_attr_t *a = get_irn_attr(irn);
321
			return a->ent;
Sebastian Hack's avatar
Sebastian Hack committed
322
		}
323
	default:
Sebastian Hack's avatar
Sebastian Hack committed
324
		assert(0 && "Must give spill/reload node");
325
326
	}

327
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
328
329
}

Sebastian Hack's avatar
Sebastian Hack committed
330
ir_node *be_spill(const arch_env_t *arch_env, ir_node *irn, ir_node *ctx)
Sebastian Hack's avatar
Sebastian Hack committed
331
{
Christian Würdig's avatar
Christian Würdig committed
332
	const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
333

Christian Würdig's avatar
Christian Würdig committed
334
335
	ir_node *bl    = get_nodes_block(irn);
	ir_graph *irg  = get_irn_irg(bl);
Sebastian Hack's avatar
Sebastian Hack committed
336
	ir_node *spill = be_new_Spill(cls, irg, bl, irn, ctx);
Sebastian Hack's avatar
Sebastian Hack committed
337
338
339
340
341
342
343
344
345
346
347
348
	ir_node *insert;

	/*
	 * search the right insertion point. a spill of a phi cannot be put
	 * directly after the phi, if there are some phis behind the one which
	 * is spilled.
	 */
	insert = sched_next(irn);
	while(is_Phi(insert) && !sched_is_end(insert))
		insert = sched_next(insert);

	sched_add_before(insert, spill);
Christian Würdig's avatar
Christian Würdig committed
349
	return spill;
Sebastian Hack's avatar
Sebastian Hack committed
350
351
}

Sebastian Hack's avatar
Sebastian Hack committed
352
353
354
ir_node *be_reload(const arch_env_t *arch_env,
				   const arch_register_class_t *cls,
				   ir_node *irn, int pos, ir_mode *mode, ir_node *spill)
Sebastian Hack's avatar
Sebastian Hack committed
355
356
357
{
	ir_node *reload;

Christian Würdig's avatar
Christian Würdig committed
358
359
	ir_node *bl   = get_nodes_block(irn);
	ir_graph *irg = get_irn_irg(bl);
Sebastian Hack's avatar
Sebastian Hack committed
360

Sebastian Hack's avatar
Sebastian Hack committed
361
	assert(be_is_Spill(spill) || (is_Phi(spill) && get_irn_mode(spill) == mode_M));
Sebastian Hack's avatar
Sebastian Hack committed
362

Sebastian Hack's avatar
Sebastian Hack committed
363
	reload = be_new_Reload(cls, irg, bl, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
364

Sebastian Hack's avatar
Sebastian Hack committed
365
	set_irn_n(irn, pos, reload);
Christian Würdig's avatar
Christian Würdig committed
366
367
	sched_add_before(irn, reload);
	return reload;
Sebastian Hack's avatar
Sebastian Hack committed
368
}
Sebastian Hack's avatar
Sebastian Hack committed
369

Sebastian Hack's avatar
Sebastian Hack committed
370
static int redir_proj(const ir_node **node, int pos)
Sebastian Hack's avatar
Sebastian Hack committed
371
{
Christian Würdig's avatar
Christian Würdig committed
372
	const ir_node *n = *node;
Sebastian Hack's avatar
Sebastian Hack committed
373

Christian Würdig's avatar
Christian Würdig committed
374
	if(is_Proj(n)) {
Sebastian Hack's avatar
Sebastian Hack committed
375
		assert(pos == -1 && "Illegal pos for a Proj");
Christian Würdig's avatar
Christian Würdig committed
376
		*node = get_Proj_pred(n);
Sebastian Hack's avatar
Sebastian Hack committed
377
		return get_Proj_proj(n);
Christian Würdig's avatar
Christian Würdig committed
378
	}
Sebastian Hack's avatar
Sebastian Hack committed
379

Sebastian Hack's avatar
Sebastian Hack committed
380
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
381
382
}

Sebastian Hack's avatar
Sebastian Hack committed
383
static void *put_out_reg_req(arch_register_req_t *req, const ir_node *irn, int out_pos)
Sebastian Hack's avatar
Sebastian Hack committed
384
{
Sebastian Hack's avatar
Sebastian Hack committed
385
	const be_node_attr_t *a = get_irn_attr(irn);
Daniel Grund's avatar
Daniel Grund committed
386

Sebastian Hack's avatar
Sebastian Hack committed
387

Sebastian Hack's avatar
Sebastian Hack committed
388
389
390
391
392
	if(out_pos < a->n_outs)
		memcpy(req, &a->reg_data[out_pos].req, sizeof(req[0]));
	else {
		req->type = arch_register_req_type_none;
		req->cls  = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
393
	}
Sebastian Hack's avatar
Sebastian Hack committed
394

Sebastian Hack's avatar
Sebastian Hack committed
395
	return req;
Sebastian Hack's avatar
Sebastian Hack committed
396
397
}

Sebastian Hack's avatar
Sebastian Hack committed
398
static void *put_in_reg_req(arch_register_req_t *req, const ir_node *irn, int pos)
399
{
Sebastian Hack's avatar
Sebastian Hack committed
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
	const be_node_attr_t *a = get_irn_attr(irn);
	int n                   = get_irn_arity(irn);

	req->type = arch_register_req_type_none;
	req->cls  = NULL;

	switch(get_irn_be_opcode(irn)) {
	case beo_Spill:
	case beo_Copy:
	case beo_Keep:
	case beo_Perm:
		if(pos < n) {
			req->type = arch_register_req_type_normal;
			req->cls  = a->cls;
		}
		break;
	case beo_Reload:
	default:
		req = NULL;
	}

	return req;
422
423
}

Sebastian Hack's avatar
Sebastian Hack committed
424
static const arch_register_req_t *
425
be_node_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos)
Sebastian Hack's avatar
Sebastian Hack committed
426
{
Sebastian Hack's avatar
Sebastian Hack committed
427
	int out_pos = pos;
Sebastian Hack's avatar
Sebastian Hack committed
428

Sebastian Hack's avatar
Sebastian Hack committed
429
430
431
	if(pos < 0) {
		if(get_irn_mode(irn) == mode_T)
			return NULL;
Daniel Grund's avatar
Daniel Grund committed
432

Sebastian Hack's avatar
Sebastian Hack committed
433
434
435
436
		out_pos = redir_proj((const ir_node **) &irn, pos);
		assert(is_be_node(irn));
		return put_out_reg_req(req, irn, out_pos);
	}
Daniel Grund's avatar
Daniel Grund committed
437

Sebastian Hack's avatar
Sebastian Hack committed
438
439
440
	else {
		return is_be_node(irn) ? put_in_reg_req(req, irn, pos) : NULL;
	}
Daniel Grund's avatar
Daniel Grund committed
441

Sebastian Hack's avatar
Sebastian Hack committed
442
	return req;
Sebastian Hack's avatar
Sebastian Hack committed
443
444
}

Sebastian Hack's avatar
Sebastian Hack committed
445
static void
446
be_node_set_irn_reg(const void *_self, ir_node *irn, const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
447
{
Sebastian Hack's avatar
Sebastian Hack committed
448
449
	int out_pos;
	be_node_attr_t *a;
Sebastian Hack's avatar
Sebastian Hack committed
450

Christian Würdig's avatar
Christian Würdig committed
451
	out_pos = redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
452
453
454
455
456
457
	a       = get_irn_attr(irn);

	assert(is_be_node(irn));
	assert(out_pos < a->n_outs && "position too high");
	a->reg_data[out_pos].reg = reg;
}
Daniel Grund's avatar
Daniel Grund committed
458

Sebastian Hack's avatar
Sebastian Hack committed
459
const arch_register_t *
460
be_node_get_irn_reg(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
461
462
463
{
	int out_pos;
	be_node_attr_t *a;
Daniel Grund's avatar
Daniel Grund committed
464

Christian Würdig's avatar
Christian Würdig committed
465
	out_pos = redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
466
	a       = get_irn_attr(irn);
Daniel Grund's avatar
Daniel Grund committed
467

Sebastian Hack's avatar
Sebastian Hack committed
468
469
	assert(is_be_node(irn));
	assert(out_pos < a->n_outs && "position too high");
Daniel Grund's avatar
Daniel Grund committed
470

Sebastian Hack's avatar
Sebastian Hack committed
471
	return a->reg_data[out_pos].reg;
Sebastian Hack's avatar
Sebastian Hack committed
472
473
}

474
arch_irn_class_t be_node_classify(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
475
{
Christian Würdig's avatar
Christian Würdig committed
476
	redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
477

Sebastian Hack's avatar
Sebastian Hack committed
478
479
480
481
482
483
	switch(get_irn_be_opcode(irn)) {
#define XXX(a,b) case beo_ ## a: return arch_irn_class_ ## b;
		XXX(Spill, spill)
		XXX(Reload, reload)
		XXX(Perm, perm)
		XXX(Copy, copy)
Sebastian Hack's avatar
Sebastian Hack committed
484
#undef XXX
Sebastian Hack's avatar
Sebastian Hack committed
485
486
		default:
		return 0;
Sebastian Hack's avatar
Sebastian Hack committed
487
488
	}

Christian Würdig's avatar
Christian Würdig committed
489
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
490
491
}

492
arch_irn_class_t be_node_get_flags(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
493
494
495
496
{
	return 0;
}

497
static const arch_irn_ops_if_t be_node_irn_ops_if = {
Sebastian Hack's avatar
Sebastian Hack committed
498
499
500
501
502
503
	be_node_get_irn_reg_req,
	be_node_set_irn_reg,
	be_node_get_irn_reg,
	be_node_classify,
	be_node_get_flags,
};
504

505
506
507
508
509
static const arch_irn_ops_t be_node_irn_ops = {
	&be_node_irn_ops_if
};

const void *be_node_get_arch_ops(const arch_irn_handler_t *self, const ir_node *irn)
510
{
Sebastian Hack's avatar
Sebastian Hack committed
511
512
	redir_proj((const ir_node **) &irn, -1);
	return is_be_node(irn) ? &be_node_irn_ops : NULL;
Sebastian Hack's avatar
Sebastian Hack committed
513
514
}

Sebastian Hack's avatar
Sebastian Hack committed
515
516
517
const arch_irn_handler_t be_node_irn_handler = {
	be_node_get_arch_ops
};
Sebastian Hack's avatar
Sebastian Hack committed
518

519
520
static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
{
Sebastian Hack's avatar
Sebastian Hack committed
521
	be_node_attr_t *at = get_irn_attr(irn);
522
523
	int i;

524
525
	assert(is_be_node(irn));

526
527
	switch(reason) {
		case dump_node_opcode_txt:
Sebastian Hack's avatar
Sebastian Hack committed
528
			fprintf(f, get_op_name(get_irn_op(irn)));
529
530
531
532
533
534
535
			break;
		case dump_node_mode_txt:
			fprintf(f, get_mode_name(get_irn_mode(irn)));
			break;
		case dump_node_nodeattr_txt:
			break;
		case dump_node_info_txt:
536
			fprintf(f, "reg class: %s\n", at->cls->name);
Sebastian Hack's avatar
Sebastian Hack committed
537
			for(i = 0; i < at->n_outs; ++i) {
538
				const arch_register_t *reg = at->reg_data[i].reg;
539
540
541
				fprintf(f, "reg #%d: %s\n", i, reg ? reg->name : "n/a");
			}

Sebastian Hack's avatar
Sebastian Hack committed
542
			if(get_irn_be_opcode(irn) == beo_Spill) {
543
				be_spill_attr_t *a = (be_spill_attr_t *) at;
Sebastian Hack's avatar
Sebastian Hack committed
544
				unsigned ofs = get_entity_offset_bytes(a->ent);
545
				ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
Sebastian Hack's avatar
Sebastian Hack committed
546
				ir_fprintf(f, "spill entity: %+F offset %x (%d)\n", a->ent, ofs, ofs);
547
548
549
550
			}
			break;
	}

551
	return 0;
552
553
}

Sebastian Hack's avatar
Sebastian Hack committed
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
static const ir_op_ops be_node_op_ops = {
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	dump_node,
	NULL
};

Sebastian Hack's avatar
Sebastian Hack committed
570
pset *nodes_live_at(const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live)
Sebastian Hack's avatar
Sebastian Hack committed
571
{
Sebastian Hack's avatar
Sebastian Hack committed
572
573
574
	firm_dbg_module_t *dbg = firm_dbg_register("firm.be.node");
	ir_node *bl            = get_nodes_block(pos);
	ir_node *irn;
Christian Würdig's avatar
Christian Würdig committed
575
	irn_live_t *li;
Daniel Grund's avatar
Daniel Grund committed
576
577
578

	live_foreach(bl, li) {
		ir_node *irn = (ir_node *) li->irn;
Sebastian Hack's avatar
Sebastian Hack committed
579
		if(live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
Daniel Grund's avatar
Daniel Grund committed
580
581
582
			pset_insert_ptr(live, irn);
	}

Christian Würdig's avatar
Christian Würdig committed
583
	sched_foreach_reverse(bl, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
584
		int i, n;
Christian Würdig's avatar
Christian Würdig committed
585
		ir_node *x;
Sebastian Hack's avatar
Sebastian Hack committed
586

Sebastian Hack's avatar
Sebastian Hack committed
587
588
589
590
		/*
		 * If we encounter the node we want to insert the Perm after,
		* exit immediately, so that this node is still live
		*/
Christian Würdig's avatar
Christian Würdig committed
591
		if(irn == pos)
Sebastian Hack's avatar
Sebastian Hack committed
592
			return live;
593

Christian Würdig's avatar
Christian Würdig committed
594
595
596
		DBG((dbg, LEVEL_1, "%+F\n", irn));
		for(x = pset_first(live); x; x = pset_next(live))
			DBG((dbg, LEVEL_1, "\tlive: %+F\n", x));
597

Christian Würdig's avatar
Christian Würdig committed
598
599
		if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
			pset_remove_ptr(live, irn);
600

Christian Würdig's avatar
Christian Würdig committed
601
602
		for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
			ir_node *op = get_irn_n(irn, i);
603

Sebastian Hack's avatar
Sebastian Hack committed
604
			if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
Christian Würdig's avatar
Christian Würdig committed
605
606
607
				pset_insert_ptr(live, op);
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
608

Sebastian Hack's avatar
Sebastian Hack committed
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
	return NULL;
}

ir_node *insert_Perm_after(const arch_env_t *arch_env,
						   const arch_register_class_t *cls,
						   dom_front_info_t *dom_front,
						   ir_node *pos)
{
	ir_node *bl                 = is_Block(pos) ? pos : get_nodes_block(pos);
	ir_graph *irg               = get_irn_irg(bl);
	pset *live                  = pset_new_ptr_default();
	firm_dbg_module_t *dbg      = firm_dbg_register("be.node");

	ir_node *curr, *irn, *perm, **nodes;
	int i, n;

	DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));

	if(!nodes_live_at(arch_env, cls, pos, live))
		assert(0 && "position not found");

Christian Würdig's avatar
Christian Würdig committed
630
	n = pset_count(live);
631
632
633
634

	if(n == 0)
		return NULL;

Christian Würdig's avatar
Christian Würdig committed
635
	nodes = malloc(n * sizeof(nodes[0]));
Sebastian Hack's avatar
Sebastian Hack committed
636

Christian Würdig's avatar
Christian Würdig committed
637
638
639
640
641
	DBG((dbg, LEVEL_1, "live:\n"));
	for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
		DBG((dbg, LEVEL_1, "\t%+F\n", irn));
		nodes[i] = irn;
	}
642

Sebastian Hack's avatar
Sebastian Hack committed
643
	perm = be_new_Perm(cls, irg, bl, n, nodes);
Christian Würdig's avatar
Christian Würdig committed
644
645
	sched_add_after(pos, perm);
	free(nodes);
646

Christian Würdig's avatar
Christian Würdig committed
647
648
649
650
	curr = perm;
	for(i = 0; i < n; ++i) {
		ir_node *copies[1];
		ir_node *perm_op = get_irn_n(perm, i);
651
		const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
652

Christian Würdig's avatar
Christian Würdig committed
653
654
655
		ir_mode *mode = get_irn_mode(perm_op);
		ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
		arch_set_irn_register(arch_env, proj, reg);
656

Christian Würdig's avatar
Christian Würdig committed
657
658
		sched_add_after(curr, proj);
		curr = proj;
659

Christian Würdig's avatar
Christian Würdig committed
660
		copies[0] = proj;
Sebastian Hack's avatar
Sebastian Hack committed
661
		be_introduce_copies(dom_front, perm_op, 1, copies);
Christian Würdig's avatar
Christian Würdig committed
662
663
	}
	return perm;
Sebastian Hack's avatar
Sebastian Hack committed
664
}