benode.c 15.5 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

96
97
98
99
100
101
102
103
104
105
106
#define N   irop_flag_none
#define L   irop_flag_labeled
#define C   irop_flag_commutative
#define X   irop_flag_cfopcode
#define I   irop_flag_ip_cfopcode
#define F   irop_flag_fragile
#define Y   irop_flag_forking
#define H   irop_flag_highlevel
#define c   irop_flag_constlike
#define K   irop_flag_keep

Sebastian Hack's avatar
Sebastian Hack committed
107
108
void be_node_init(void) {
	static int inited = 0;
Sebastian Hack's avatar
Sebastian Hack committed
109

Sebastian Hack's avatar
Sebastian Hack committed
110
111
	if(inited)
		return;
Sebastian Hack's avatar
Sebastian Hack committed
112

Sebastian Hack's avatar
Sebastian Hack committed
113
	inited = 1;
Sebastian Hack's avatar
Sebastian Hack committed
114

115
116
	/* Acquire all needed opcodes. */
	beo_base = get_next_ir_opcodes(beo_Last - 1);
Sebastian Hack's avatar
Sebastian Hack committed
117

118
119
120
121
122
	op_Spill  = new_ir_op(beo_base + beo_Spill,  "Spill",  op_pin_state_mem_pinned, N, 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, N, 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,     N, 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,     N, 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,     K, oparity_variable, 0, sizeof(be_node_attr_t),  &be_node_op_ops);
Sebastian Hack's avatar
Sebastian Hack committed
123

Sebastian Hack's avatar
Sebastian Hack committed
124
125
126
127
128
129
	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);
}
130

Sebastian Hack's avatar
Sebastian Hack committed
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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
145
146
			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
147
148
149
150
151
		}
	}

	return a;
}
152

153
154
static INLINE int is_be_node(const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
155
	return get_op_tag(get_irn_op(irn)) == &be_node_tag;
156
157
}

Sebastian Hack's avatar
Sebastian Hack committed
158
be_opcode_t get_irn_be_opcode(const ir_node *irn)
159
{
Sebastian Hack's avatar
Sebastian Hack committed
160
	return is_be_node(irn) ? get_irn_opcode(irn) - beo_base : beo_NoBeOp;
161
162
}

Sebastian Hack's avatar
Sebastian Hack committed
163
ir_node *be_new_Spill(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *to_spill, ir_node *ctx)
164
{
Sebastian Hack's avatar
Sebastian Hack committed
165
166
167
	be_spill_attr_t *a;
	ir_node *in[1];
	ir_node *res;
168

Sebastian Hack's avatar
Sebastian Hack committed
169
170
171
	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
172
	a->ent       = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
173
174
175
	a->spill_ctx = ctx;
	return res;
}
176

Sebastian Hack's avatar
Sebastian Hack committed
177
ir_node *be_new_Reload(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_mode *mode, ir_node *mem)
178
{
Sebastian Hack's avatar
Sebastian Hack committed
179
180
	ir_node *in[1];
	ir_node *res;
181

Sebastian Hack's avatar
Sebastian Hack committed
182
183
184
185
186
	in[0] = mem;
	res   = new_ir_node(NULL, irg, bl, op_Reload, mode, 1, in);
	init_node_attr(res, cls, irg, 1);
	return res;
}
187

Sebastian Hack's avatar
Sebastian Hack committed
188
189
190
191
192
193
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;
}
194

Sebastian Hack's avatar
Sebastian Hack committed
195
196
197
198
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;
199

Sebastian Hack's avatar
Sebastian Hack committed
200
201
202
203
	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;
204
205
}

Sebastian Hack's avatar
Sebastian Hack committed
206
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
207
{
Sebastian Hack's avatar
Sebastian Hack committed
208
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
209

Sebastian Hack's avatar
Sebastian Hack committed
210
211
212
213
	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
214
215
}

Sebastian Hack's avatar
Sebastian Hack committed
216
int be_is_Spill(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
217
{
Sebastian Hack's avatar
Sebastian Hack committed
218
219
	return get_irn_be_opcode(irn) == beo_Spill;
}
Sebastian Hack's avatar
Sebastian Hack committed
220

Sebastian Hack's avatar
Sebastian Hack committed
221
222
223
int be_is_Reload(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Reload;
Sebastian Hack's avatar
Sebastian Hack committed
224
225
}

Sebastian Hack's avatar
Sebastian Hack committed
226
227
228
229
int be_is_Copy(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Copy;
}
Sebastian Hack's avatar
Sebastian Hack committed
230

Sebastian Hack's avatar
Sebastian Hack committed
231
232
233
234
int be_is_Perm(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Perm;
}
Sebastian Hack's avatar
Sebastian Hack committed
235

Sebastian Hack's avatar
Sebastian Hack committed
236
int be_is_Keep(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
237
{
Sebastian Hack's avatar
Sebastian Hack committed
238
239
	return get_irn_be_opcode(irn) == beo_Keep;
}
Sebastian Hack's avatar
Sebastian Hack committed
240

Sebastian Hack's avatar
Sebastian Hack committed
241
static void be_limited(void *data, bitset_t *bs)
Sebastian Hack's avatar
Sebastian Hack committed
242
{
Sebastian Hack's avatar
Sebastian Hack committed
243
244
245
246
247
248
249
250
251
252
253
	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
254

Sebastian Hack's avatar
Sebastian Hack committed
255
256
	assert(be_is_Perm(irn));
	assert(pos >= 0 && pos < get_irn_arity(irn));
Sebastian Hack's avatar
Sebastian Hack committed
257
258
259
260
261
262
263
264
265
	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
266
267
}

268
void be_set_Spill_entity(ir_node *irn, entity *ent)
269
{
Sebastian Hack's avatar
Sebastian Hack committed
270
271
	be_spill_attr_t *a = get_irn_attr(irn);
	assert(be_is_Spill(irn));
272
	a->ent = ent;
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
}

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
289
		else if(get_irn_be_opcode(irn) == beo_Spill)
290
291
292
293
294
295
			return irn;
	}

	return NULL;
}

Sebastian Hack's avatar
Sebastian Hack committed
296
297
298
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));
299
300
301
	return a->spill_ctx;
}

302
303
304
305
306
307
308
309
310
311
312
/**
 * 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
313
	assert(be_is_Reload(irn));
314
315
316
317
	set_irg_visited(irg, visited_nr);
	return find_a_spill_walker(irn, visited_nr);
}

318
entity *be_get_spill_entity(ir_node *irn)
319
{
Sebastian Hack's avatar
Sebastian Hack committed
320
	int opc           = get_irn_opcode(irn);
321

Sebastian Hack's avatar
Sebastian Hack committed
322
323
	switch(get_irn_be_opcode(irn)) {
	case beo_Reload:
324
		return be_get_spill_entity(find_a_spill(irn));
Sebastian Hack's avatar
Sebastian Hack committed
325
326
327
	case beo_Spill:
		{
			be_spill_attr_t *a = get_irn_attr(irn);
328
			return a->ent;
Sebastian Hack's avatar
Sebastian Hack committed
329
		}
330
	default:
Sebastian Hack's avatar
Sebastian Hack committed
331
		assert(0 && "Must give spill/reload node");
332
333
	}

334
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
335
336
}

Sebastian Hack's avatar
Sebastian Hack committed
337
ir_node *be_spill(const arch_env_t *arch_env, ir_node *irn, ir_node *ctx)
Sebastian Hack's avatar
Sebastian Hack committed
338
{
Christian Würdig's avatar
Christian Würdig committed
339
	const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
340

Christian Würdig's avatar
Christian Würdig committed
341
342
	ir_node *bl    = get_nodes_block(irn);
	ir_graph *irg  = get_irn_irg(bl);
Sebastian Hack's avatar
Sebastian Hack committed
343
	ir_node *spill = be_new_Spill(cls, irg, bl, irn, ctx);
Sebastian Hack's avatar
Sebastian Hack committed
344
345
346
347
348
349
350
351
352
353
354
355
	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
356
	return spill;
Sebastian Hack's avatar
Sebastian Hack committed
357
358
}

Sebastian Hack's avatar
Sebastian Hack committed
359
360
361
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
362
363
364
{
	ir_node *reload;

Christian Würdig's avatar
Christian Würdig committed
365
366
	ir_node *bl   = get_nodes_block(irn);
	ir_graph *irg = get_irn_irg(bl);
Sebastian Hack's avatar
Sebastian Hack committed
367

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

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

Sebastian Hack's avatar
Sebastian Hack committed
372
	set_irn_n(irn, pos, reload);
Christian Würdig's avatar
Christian Würdig committed
373
374
	sched_add_before(irn, reload);
	return reload;
Sebastian Hack's avatar
Sebastian Hack committed
375
}
Sebastian Hack's avatar
Sebastian Hack committed
376

Sebastian Hack's avatar
Sebastian Hack committed
377
static int redir_proj(const ir_node **node, int pos)
Sebastian Hack's avatar
Sebastian Hack committed
378
{
Christian Würdig's avatar
Christian Würdig committed
379
	const ir_node *n = *node;
Sebastian Hack's avatar
Sebastian Hack committed
380

Christian Würdig's avatar
Christian Würdig committed
381
	if(is_Proj(n)) {
Sebastian Hack's avatar
Sebastian Hack committed
382
		assert(pos == -1 && "Illegal pos for a Proj");
Christian Würdig's avatar
Christian Würdig committed
383
		*node = get_Proj_pred(n);
Sebastian Hack's avatar
Sebastian Hack committed
384
		return get_Proj_proj(n);
Christian Würdig's avatar
Christian Würdig committed
385
	}
Sebastian Hack's avatar
Sebastian Hack committed
386

Sebastian Hack's avatar
Sebastian Hack committed
387
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
388
389
}

Sebastian Hack's avatar
Sebastian Hack committed
390
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
391
{
Sebastian Hack's avatar
Sebastian Hack committed
392
	const be_node_attr_t *a = get_irn_attr(irn);
Daniel Grund's avatar
Daniel Grund committed
393

Sebastian Hack's avatar
Sebastian Hack committed
394

Sebastian Hack's avatar
Sebastian Hack committed
395
396
397
398
399
	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
400
	}
Sebastian Hack's avatar
Sebastian Hack committed
401

Sebastian Hack's avatar
Sebastian Hack committed
402
	return req;
Sebastian Hack's avatar
Sebastian Hack committed
403
404
}

Sebastian Hack's avatar
Sebastian Hack committed
405
static void *put_in_reg_req(arch_register_req_t *req, const ir_node *irn, int pos)
406
{
Sebastian Hack's avatar
Sebastian Hack committed
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
	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;
429
430
}

Sebastian Hack's avatar
Sebastian Hack committed
431
static const arch_register_req_t *
432
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
433
{
Sebastian Hack's avatar
Sebastian Hack committed
434
	int out_pos = pos;
Sebastian Hack's avatar
Sebastian Hack committed
435

Sebastian Hack's avatar
Sebastian Hack committed
436
437
438
	if(pos < 0) {
		if(get_irn_mode(irn) == mode_T)
			return NULL;
Daniel Grund's avatar
Daniel Grund committed
439

Sebastian Hack's avatar
Sebastian Hack committed
440
441
442
443
		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
444

Sebastian Hack's avatar
Sebastian Hack committed
445
446
447
	else {
		return is_be_node(irn) ? put_in_reg_req(req, irn, pos) : NULL;
	}
Daniel Grund's avatar
Daniel Grund committed
448

Sebastian Hack's avatar
Sebastian Hack committed
449
	return req;
Sebastian Hack's avatar
Sebastian Hack committed
450
451
}

Sebastian Hack's avatar
Sebastian Hack committed
452
static void
453
be_node_set_irn_reg(const void *_self, ir_node *irn, const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
454
{
Sebastian Hack's avatar
Sebastian Hack committed
455
456
	int out_pos;
	be_node_attr_t *a;
Sebastian Hack's avatar
Sebastian Hack committed
457

Christian Würdig's avatar
Christian Würdig committed
458
	out_pos = redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
459
460
461
462
463
464
	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
465

Sebastian Hack's avatar
Sebastian Hack committed
466
const arch_register_t *
467
be_node_get_irn_reg(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
468
469
470
{
	int out_pos;
	be_node_attr_t *a;
Daniel Grund's avatar
Daniel Grund committed
471

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

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

Sebastian Hack's avatar
Sebastian Hack committed
478
	return a->reg_data[out_pos].reg;
Sebastian Hack's avatar
Sebastian Hack committed
479
480
}

481
arch_irn_class_t be_node_classify(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
482
{
Christian Würdig's avatar
Christian Würdig committed
483
	redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
484

Sebastian Hack's avatar
Sebastian Hack committed
485
486
487
488
489
490
	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
491
#undef XXX
Sebastian Hack's avatar
Sebastian Hack committed
492
493
		default:
		return 0;
Sebastian Hack's avatar
Sebastian Hack committed
494
495
	}

Christian Würdig's avatar
Christian Würdig committed
496
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
497
498
}

499
arch_irn_class_t be_node_get_flags(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
500
501
502
503
{
	return 0;
}

504
static const arch_irn_ops_if_t be_node_irn_ops_if = {
Sebastian Hack's avatar
Sebastian Hack committed
505
506
507
508
509
510
	be_node_get_irn_reg_req,
	be_node_set_irn_reg,
	be_node_get_irn_reg,
	be_node_classify,
	be_node_get_flags,
};
511

512
513
514
515
516
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)
517
{
Sebastian Hack's avatar
Sebastian Hack committed
518
519
	redir_proj((const ir_node **) &irn, -1);
	return is_be_node(irn) ? &be_node_irn_ops : NULL;
Sebastian Hack's avatar
Sebastian Hack committed
520
521
}

Sebastian Hack's avatar
Sebastian Hack committed
522
523
524
const arch_irn_handler_t be_node_irn_handler = {
	be_node_get_arch_ops
};
Sebastian Hack's avatar
Sebastian Hack committed
525

526
527
static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
{
Sebastian Hack's avatar
Sebastian Hack committed
528
	be_node_attr_t *at = get_irn_attr(irn);
529
530
	int i;

531
532
	assert(is_be_node(irn));

533
534
	switch(reason) {
		case dump_node_opcode_txt:
Sebastian Hack's avatar
Sebastian Hack committed
535
			fprintf(f, get_op_name(get_irn_op(irn)));
536
537
538
539
540
541
542
			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:
543
			fprintf(f, "reg class: %s\n", at->cls->name);
Sebastian Hack's avatar
Sebastian Hack committed
544
			for(i = 0; i < at->n_outs; ++i) {
545
				const arch_register_t *reg = at->reg_data[i].reg;
546
547
548
				fprintf(f, "reg #%d: %s\n", i, reg ? reg->name : "n/a");
			}

Sebastian Hack's avatar
Sebastian Hack committed
549
			if(get_irn_be_opcode(irn) == beo_Spill) {
550
				be_spill_attr_t *a = (be_spill_attr_t *) at;
Christian Würdig's avatar
Christian Würdig committed
551

552
				ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
Christian Würdig's avatar
Christian Würdig committed
553
554
555
556
557
558
559
				if (a->ent) {
					unsigned ofs = get_entity_offset_bytes(a->ent);
					ir_fprintf(f, "spill entity: %+F offset %x (%d)\n", a->ent, ofs, ofs);
				}
				else {
					ir_fprintf(f, "spill entity: n/a\n");
				}
560
561
562
563
			}
			break;
	}

564
	return 0;
565
566
}

Sebastian Hack's avatar
Sebastian Hack committed
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
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
583
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
584
{
Sebastian Hack's avatar
Sebastian Hack committed
585
	firm_dbg_module_t *dbg = firm_dbg_register("firm.be.node");
Christian Würdig's avatar
Christian Würdig committed
586
	const ir_node *bl      = is_Block(pos) ? pos : get_nodes_block(pos);
Sebastian Hack's avatar
Sebastian Hack committed
587
	ir_node *irn;
Christian Würdig's avatar
Christian Würdig committed
588
	irn_live_t *li;
Daniel Grund's avatar
Daniel Grund committed
589
590
591

	live_foreach(bl, li) {
		ir_node *irn = (ir_node *) li->irn;
Sebastian Hack's avatar
Sebastian Hack committed
592
		if(live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
Daniel Grund's avatar
Daniel Grund committed
593
594
595
			pset_insert_ptr(live, irn);
	}

Christian Würdig's avatar
Christian Würdig committed
596
	sched_foreach_reverse(bl, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
597
		int i, n;
Christian Würdig's avatar
Christian Würdig committed
598
		ir_node *x;
Sebastian Hack's avatar
Sebastian Hack committed
599

Sebastian Hack's avatar
Sebastian Hack committed
600
601
602
603
		/*
		 * 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
604
		if(irn == pos)
Sebastian Hack's avatar
Sebastian Hack committed
605
			return live;
606

Christian Würdig's avatar
Christian Würdig committed
607
608
609
		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));
610

Christian Würdig's avatar
Christian Würdig committed
611
612
		if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
			pset_remove_ptr(live, irn);
613

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

Sebastian Hack's avatar
Sebastian Hack committed
617
			if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
Christian Würdig's avatar
Christian Würdig committed
618
619
620
				pset_insert_ptr(live, op);
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
621

Christian Würdig's avatar
Christian Würdig committed
622
	return live;
Sebastian Hack's avatar
Sebastian Hack committed
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
}

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

Christian Würdig's avatar
Christian Würdig committed
640
	if(!nodes_live_at(arch_env, cls, pos, live));
Sebastian Hack's avatar
Sebastian Hack committed
641

Christian Würdig's avatar
Christian Würdig committed
642
	n = pset_count(live);
643
644
645
646

	if(n == 0)
		return NULL;

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

Christian Würdig's avatar
Christian Würdig committed
649
650
651
652
653
	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;
	}
654

Sebastian Hack's avatar
Sebastian Hack committed
655
	perm = be_new_Perm(cls, irg, bl, n, nodes);
Christian Würdig's avatar
Christian Würdig committed
656
657
	sched_add_after(pos, perm);
	free(nodes);
658

Christian Würdig's avatar
Christian Würdig committed
659
660
661
662
	curr = perm;
	for(i = 0; i < n; ++i) {
		ir_node *copies[1];
		ir_node *perm_op = get_irn_n(perm, i);
663
		const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
664

Christian Würdig's avatar
Christian Würdig committed
665
666
667
		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);
668

Christian Würdig's avatar
Christian Würdig committed
669
670
		sched_add_after(curr, proj);
		curr = proj;
671

Christian Würdig's avatar
Christian Würdig committed
672
		copies[0] = proj;
Sebastian Hack's avatar
Sebastian Hack committed
673
		be_introduce_copies(dom_front, perm_op, 1, copies);
Christian Würdig's avatar
Christian Würdig committed
674
675
	}
	return perm;
Sebastian Hack's avatar
Sebastian Hack committed
676
}