benode.c 16.1 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
typedef enum {
	be_req_kind_old_limited,
	be_req_kind_negate_old_limited,
	be_req_kind_single_reg
} be_req_kind_t;

Sebastian Hack's avatar
Sebastian Hack committed
68
69
typedef struct {
	arch_register_req_t req;
Sebastian Hack's avatar
Sebastian Hack committed
70
71
72
73
74
75
76
77
78
	be_req_kind_t       kind;
	union {
		struct {
			void (*old_limited)(void *ptr, bitset_t *bs);
			void *old_limited_env;
		} old_limited;

		const arch_register_t *single_reg;
	} x;
Sebastian Hack's avatar
Sebastian Hack committed
79
80
} be_req_t;

81
typedef struct {
82
	const arch_register_t *reg;
Sebastian Hack's avatar
Sebastian Hack committed
83
	be_req_t              req;
Sebastian Hack's avatar
Sebastian Hack committed
84
	be_req_t              in_req;
85
86
87
} be_reg_data_t;

typedef struct {
Sebastian Hack's avatar
Sebastian Hack committed
88
89
90
	int                         n_outs;
	const arch_register_class_t *cls;
	be_reg_data_t               *reg_data;
91
92
93
} be_node_attr_t;

typedef struct {
Sebastian Hack's avatar
Sebastian Hack committed
94
	be_node_attr_t node_attr;
95
	ir_node *spill_ctx;  /**< The node in whose context this spill was introduced. */
96
	entity *ent;     /**< The entity in the stack frame the spill writes to. */
97
98
} be_spill_attr_t;

Sebastian Hack's avatar
Sebastian Hack committed
99
100
101
102
103
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
104
105
106
static ir_op *op_Call;
static ir_op *op_IncSP;
static ir_op *op_AddSP;
Sebastian Hack's avatar
Sebastian Hack committed
107

Sebastian Hack's avatar
Sebastian Hack committed
108
static int beo_base = -1;
Sebastian Hack's avatar
Sebastian Hack committed
109

Sebastian Hack's avatar
Sebastian Hack committed
110
static const ir_op_ops be_node_op_ops;
Sebastian Hack's avatar
Sebastian Hack committed
111

112
113
114
115
116
117
118
119
120
121
122
#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
123
124
void be_node_init(void) {
	static int inited = 0;
Sebastian Hack's avatar
Sebastian Hack committed
125

Sebastian Hack's avatar
Sebastian Hack committed
126
127
	if(inited)
		return;
Sebastian Hack's avatar
Sebastian Hack committed
128

Sebastian Hack's avatar
Sebastian Hack committed
129
	inited = 1;
Sebastian Hack's avatar
Sebastian Hack committed
130

131
132
	/* Acquire all needed opcodes. */
	beo_base = get_next_ir_opcodes(beo_Last - 1);
Sebastian Hack's avatar
Sebastian Hack committed
133

134
135
136
137
138
	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
139

Sebastian Hack's avatar
Sebastian Hack committed
140
141
142
143
144
145
	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);
}
146

Sebastian Hack's avatar
Sebastian Hack committed
147
148
149
150
151
152
153
154
155
156
157
158
159
160
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
161
162
			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
163
164
165
166
167
		}
	}

	return a;
}
168

169
170
static INLINE int is_be_node(const ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
171
	return get_op_tag(get_irn_op(irn)) == &be_node_tag;
172
173
}

Sebastian Hack's avatar
Sebastian Hack committed
174
be_opcode_t get_irn_be_opcode(const ir_node *irn)
175
{
Sebastian Hack's avatar
Sebastian Hack committed
176
	return is_be_node(irn) ? get_irn_opcode(irn) - beo_base : beo_NoBeOp;
177
178
}

Sebastian Hack's avatar
Sebastian Hack committed
179
ir_node *be_new_Spill(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *to_spill, ir_node *ctx)
180
{
Sebastian Hack's avatar
Sebastian Hack committed
181
182
183
	be_spill_attr_t *a;
	ir_node *in[1];
	ir_node *res;
184

Sebastian Hack's avatar
Sebastian Hack committed
185
186
187
	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
188
	a->ent       = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
189
190
191
	a->spill_ctx = ctx;
	return res;
}
192

Sebastian Hack's avatar
Sebastian Hack committed
193
ir_node *be_new_Reload(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_mode *mode, ir_node *mem)
194
{
Sebastian Hack's avatar
Sebastian Hack committed
195
196
	ir_node *in[1];
	ir_node *res;
197

Sebastian Hack's avatar
Sebastian Hack committed
198
199
200
201
202
	in[0] = mem;
	res   = new_ir_node(NULL, irg, bl, op_Reload, mode, 1, in);
	init_node_attr(res, cls, irg, 1);
	return res;
}
203

Sebastian Hack's avatar
Sebastian Hack committed
204
205
206
207
208
209
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;
}
210

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

Sebastian Hack's avatar
Sebastian Hack committed
216
217
218
219
	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;
220
221
}

Sebastian Hack's avatar
Sebastian Hack committed
222
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
223
{
Sebastian Hack's avatar
Sebastian Hack committed
224
	ir_node *irn;
Sebastian Hack's avatar
Sebastian Hack committed
225

Sebastian Hack's avatar
Sebastian Hack committed
226
227
228
229
	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
230
231
}

Sebastian Hack's avatar
Sebastian Hack committed
232
int be_is_Spill(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
233
{
Sebastian Hack's avatar
Sebastian Hack committed
234
235
	return get_irn_be_opcode(irn) == beo_Spill;
}
Sebastian Hack's avatar
Sebastian Hack committed
236

Sebastian Hack's avatar
Sebastian Hack committed
237
238
239
int be_is_Reload(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Reload;
Sebastian Hack's avatar
Sebastian Hack committed
240
241
}

Sebastian Hack's avatar
Sebastian Hack committed
242
243
244
245
int be_is_Copy(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Copy;
}
Sebastian Hack's avatar
Sebastian Hack committed
246

Sebastian Hack's avatar
Sebastian Hack committed
247
248
249
250
int be_is_Perm(const ir_node *irn)
{
	return get_irn_be_opcode(irn) == beo_Perm;
}
Sebastian Hack's avatar
Sebastian Hack committed
251

Sebastian Hack's avatar
Sebastian Hack committed
252
int be_is_Keep(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
253
{
Sebastian Hack's avatar
Sebastian Hack committed
254
255
	return get_irn_be_opcode(irn) == beo_Keep;
}
Sebastian Hack's avatar
Sebastian Hack committed
256

Sebastian Hack's avatar
Sebastian Hack committed
257
static void be_limited(void *data, bitset_t *bs)
Sebastian Hack's avatar
Sebastian Hack committed
258
{
Sebastian Hack's avatar
Sebastian Hack committed
259
260
	be_req_t *req = data;

Sebastian Hack's avatar
Sebastian Hack committed
261
262
263
264
265
266
267
268
269
270
271
272
	switch(req->kind) {
	case be_req_kind_negate_old_limited:
	case be_req_kind_old_limited:
		req->x.old_limited.old_limited(req->x.old_limited.old_limited_env, bs);
		if(req->kind == be_req_kind_negate_old_limited)
			bitset_flip_all(bs);
		break;
	case be_req_kind_single_reg:
		bitset_clear_all(bs);
		bitset_set(bs, req->x.single_reg->index);
		break;
	}
Sebastian Hack's avatar
Sebastian Hack committed
273
274
}

Sebastian Hack's avatar
Sebastian Hack committed
275
void be_set_constr_single_reg(ir_node *irn, int pos, const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
276
{
Sebastian Hack's avatar
Sebastian Hack committed
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
	int idx           = pos < 0 ? -(pos - 1) : pos;
	be_node_attr_t *a = get_irn_attr(irn);
	be_reg_data_t *rd = &a->reg_data[idx];
	be_req_t       *r = pos < 0 ? &rd->req : &rd->in_req;

	assert(is_be_node(irn));
	assert(!(pos >= 0) || pos < get_irn_arity(irn));
	assert(!(pos < 0)  || -(pos + 1) <= a->n_outs);

	r->kind            = be_req_kind_single_reg;
	r->x.single_reg    = reg;
	r->req.limited     = be_limited;
	r->req.limited_env = r;
	r->req.type        = arch_register_req_type_limited;
	r->req.cls         = reg->reg_class;
}

void be_set_IncSP_offset(ir_node *irn, int offset)
{

}

int be_get_IncSP_offset(ir_node *irn)
{
	return -1;
Sebastian Hack's avatar
Sebastian Hack committed
302
303
}

304
void be_set_Spill_entity(ir_node *irn, entity *ent)
305
{
Sebastian Hack's avatar
Sebastian Hack committed
306
307
	be_spill_attr_t *a = get_irn_attr(irn);
	assert(be_is_Spill(irn));
308
	a->ent = ent;
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
}

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
325
		else if(get_irn_be_opcode(irn) == beo_Spill)
326
327
328
329
330
331
			return irn;
	}

	return NULL;
}

Sebastian Hack's avatar
Sebastian Hack committed
332
333
334
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));
335
336
337
	return a->spill_ctx;
}

338
339
340
341
342
343
344
345
346
347
348
/**
 * 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
349
	assert(be_is_Reload(irn));
350
351
352
353
	set_irg_visited(irg, visited_nr);
	return find_a_spill_walker(irn, visited_nr);
}

354
entity *be_get_spill_entity(ir_node *irn)
355
{
Sebastian Hack's avatar
Sebastian Hack committed
356
	int opc           = get_irn_opcode(irn);
357

Sebastian Hack's avatar
Sebastian Hack committed
358
359
	switch(get_irn_be_opcode(irn)) {
	case beo_Reload:
360
		return be_get_spill_entity(find_a_spill(irn));
Sebastian Hack's avatar
Sebastian Hack committed
361
362
363
	case beo_Spill:
		{
			be_spill_attr_t *a = get_irn_attr(irn);
364
			return a->ent;
Sebastian Hack's avatar
Sebastian Hack committed
365
		}
366
	default:
Sebastian Hack's avatar
Sebastian Hack committed
367
		assert(0 && "Must give spill/reload node");
368
369
	}

370
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
371
372
}

Sebastian Hack's avatar
Sebastian Hack committed
373
ir_node *be_spill(const arch_env_t *arch_env, ir_node *irn, ir_node *ctx)
Sebastian Hack's avatar
Sebastian Hack committed
374
{
Christian Würdig's avatar
Christian Würdig committed
375
	const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
376

Christian Würdig's avatar
Christian Würdig committed
377
378
	ir_node *bl    = get_nodes_block(irn);
	ir_graph *irg  = get_irn_irg(bl);
Sebastian Hack's avatar
Sebastian Hack committed
379
	ir_node *spill = be_new_Spill(cls, irg, bl, irn, ctx);
Sebastian Hack's avatar
Sebastian Hack committed
380
381
382
383
384
385
386
387
388
389
390
391
	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
392
	return spill;
Sebastian Hack's avatar
Sebastian Hack committed
393
394
}

Sebastian Hack's avatar
Sebastian Hack committed
395
396
397
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
398
399
400
{
	ir_node *reload;

Christian Würdig's avatar
Christian Würdig committed
401
402
	ir_node *bl   = get_nodes_block(irn);
	ir_graph *irg = get_irn_irg(bl);
Sebastian Hack's avatar
Sebastian Hack committed
403

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

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

Sebastian Hack's avatar
Sebastian Hack committed
408
	set_irn_n(irn, pos, reload);
Christian Würdig's avatar
Christian Würdig committed
409
410
	sched_add_before(irn, reload);
	return reload;
Sebastian Hack's avatar
Sebastian Hack committed
411
}
Sebastian Hack's avatar
Sebastian Hack committed
412

Sebastian Hack's avatar
Sebastian Hack committed
413
static int redir_proj(const ir_node **node, int pos)
Sebastian Hack's avatar
Sebastian Hack committed
414
{
Christian Würdig's avatar
Christian Würdig committed
415
	const ir_node *n = *node;
Sebastian Hack's avatar
Sebastian Hack committed
416

Christian Würdig's avatar
Christian Würdig committed
417
	if(is_Proj(n)) {
Sebastian Hack's avatar
Sebastian Hack committed
418
		assert(pos == -1 && "Illegal pos for a Proj");
Christian Würdig's avatar
Christian Würdig committed
419
		*node = get_Proj_pred(n);
Sebastian Hack's avatar
Sebastian Hack committed
420
		return get_Proj_proj(n);
Christian Würdig's avatar
Christian Würdig committed
421
	}
Sebastian Hack's avatar
Sebastian Hack committed
422

Sebastian Hack's avatar
Sebastian Hack committed
423
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
424
425
}

Sebastian Hack's avatar
Sebastian Hack committed
426
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
427
{
Sebastian Hack's avatar
Sebastian Hack committed
428
	const be_node_attr_t *a = get_irn_attr(irn);
Daniel Grund's avatar
Daniel Grund committed
429

Sebastian Hack's avatar
Sebastian Hack committed
430
431
432
433
434
	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
435
	}
Sebastian Hack's avatar
Sebastian Hack committed
436

Sebastian Hack's avatar
Sebastian Hack committed
437
	return req;
Sebastian Hack's avatar
Sebastian Hack committed
438
439
}

Sebastian Hack's avatar
Sebastian Hack committed
440
static void *put_in_reg_req(arch_register_req_t *req, const ir_node *irn, int pos)
441
{
Sebastian Hack's avatar
Sebastian Hack committed
442
443
444
	const be_node_attr_t *a = get_irn_attr(irn);
	int n                   = get_irn_arity(irn);

Sebastian Hack's avatar
Sebastian Hack committed
445
446
447
448
449
	if(pos < get_irn_arity(irn))
		memcpy(req, &a->reg_data[pos].in_req, sizeof(req[0]));
	else {
		req->type = arch_register_req_type_none;
		req->cls  = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
450
451
452
	}

	return req;
453
454
}

Sebastian Hack's avatar
Sebastian Hack committed
455
static const arch_register_req_t *
456
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
457
{
Sebastian Hack's avatar
Sebastian Hack committed
458
	int out_pos = pos;
Sebastian Hack's avatar
Sebastian Hack committed
459

Sebastian Hack's avatar
Sebastian Hack committed
460
461
462
	if(pos < 0) {
		if(get_irn_mode(irn) == mode_T)
			return NULL;
Daniel Grund's avatar
Daniel Grund committed
463

Sebastian Hack's avatar
Sebastian Hack committed
464
465
466
467
		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
468

Sebastian Hack's avatar
Sebastian Hack committed
469
470
471
	else {
		return is_be_node(irn) ? put_in_reg_req(req, irn, pos) : NULL;
	}
Daniel Grund's avatar
Daniel Grund committed
472

Sebastian Hack's avatar
Sebastian Hack committed
473
	return req;
Sebastian Hack's avatar
Sebastian Hack committed
474
475
}

Sebastian Hack's avatar
Sebastian Hack committed
476
static void
477
be_node_set_irn_reg(const void *_self, ir_node *irn, const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
478
{
Sebastian Hack's avatar
Sebastian Hack committed
479
480
	int out_pos;
	be_node_attr_t *a;
Sebastian Hack's avatar
Sebastian Hack committed
481

Christian Würdig's avatar
Christian Würdig committed
482
	out_pos = redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
483
484
485
486
487
488
	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
489

Sebastian Hack's avatar
Sebastian Hack committed
490
const arch_register_t *
491
be_node_get_irn_reg(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
492
493
494
{
	int out_pos;
	be_node_attr_t *a;
Daniel Grund's avatar
Daniel Grund committed
495

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

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

Sebastian Hack's avatar
Sebastian Hack committed
502
	return a->reg_data[out_pos].reg;
Sebastian Hack's avatar
Sebastian Hack committed
503
504
}

505
arch_irn_class_t be_node_classify(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
506
{
Christian Würdig's avatar
Christian Würdig committed
507
	redir_proj((const ir_node **) &irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
508

Sebastian Hack's avatar
Sebastian Hack committed
509
510
511
512
513
514
	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
515
#undef XXX
Sebastian Hack's avatar
Sebastian Hack committed
516
517
		default:
		return 0;
Sebastian Hack's avatar
Sebastian Hack committed
518
519
	}

Christian Würdig's avatar
Christian Würdig committed
520
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
521
522
}

523
arch_irn_class_t be_node_get_flags(const void *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
524
525
526
527
{
	return 0;
}

528
static const arch_irn_ops_if_t be_node_irn_ops_if = {
Sebastian Hack's avatar
Sebastian Hack committed
529
530
531
532
533
534
	be_node_get_irn_reg_req,
	be_node_set_irn_reg,
	be_node_get_irn_reg,
	be_node_classify,
	be_node_get_flags,
};
535

536
537
538
539
540
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)
541
{
Sebastian Hack's avatar
Sebastian Hack committed
542
543
	redir_proj((const ir_node **) &irn, -1);
	return is_be_node(irn) ? &be_node_irn_ops : NULL;
Sebastian Hack's avatar
Sebastian Hack committed
544
545
}

Sebastian Hack's avatar
Sebastian Hack committed
546
547
548
const arch_irn_handler_t be_node_irn_handler = {
	be_node_get_arch_ops
};
Sebastian Hack's avatar
Sebastian Hack committed
549

550
551
static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
{
Sebastian Hack's avatar
Sebastian Hack committed
552
	be_node_attr_t *at = get_irn_attr(irn);
553
554
	int i;

555
556
	assert(is_be_node(irn));

557
558
	switch(reason) {
		case dump_node_opcode_txt:
Sebastian Hack's avatar
Sebastian Hack committed
559
			fprintf(f, get_op_name(get_irn_op(irn)));
560
561
562
563
564
565
566
			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:
567
			fprintf(f, "reg class: %s\n", at->cls->name);
Sebastian Hack's avatar
Sebastian Hack committed
568
			for(i = 0; i < at->n_outs; ++i) {
569
				const arch_register_t *reg = at->reg_data[i].reg;
570
571
572
				fprintf(f, "reg #%d: %s\n", i, reg ? reg->name : "n/a");
			}

Sebastian Hack's avatar
Sebastian Hack committed
573
			if(get_irn_be_opcode(irn) == beo_Spill) {
574
				be_spill_attr_t *a = (be_spill_attr_t *) at;
Christian Würdig's avatar
Christian Würdig committed
575

576
				ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
Christian Würdig's avatar
Christian Würdig committed
577
578
579
580
581
582
583
				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");
				}
584
585
586
587
			}
			break;
	}

588
	return 0;
589
590
}

Sebastian Hack's avatar
Sebastian Hack committed
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
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
607
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
608
{
Sebastian Hack's avatar
Sebastian Hack committed
609
	firm_dbg_module_t *dbg = firm_dbg_register("firm.be.node");
Christian Würdig's avatar
Christian Würdig committed
610
	const ir_node *bl      = is_Block(pos) ? pos : get_nodes_block(pos);
Sebastian Hack's avatar
Sebastian Hack committed
611
	ir_node *irn;
Christian Würdig's avatar
Christian Würdig committed
612
	irn_live_t *li;
Daniel Grund's avatar
Daniel Grund committed
613
614
615

	live_foreach(bl, li) {
		ir_node *irn = (ir_node *) li->irn;
Sebastian Hack's avatar
Sebastian Hack committed
616
		if(live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
Daniel Grund's avatar
Daniel Grund committed
617
618
619
			pset_insert_ptr(live, irn);
	}

Christian Würdig's avatar
Christian Würdig committed
620
	sched_foreach_reverse(bl, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
621
		int i, n;
Christian Würdig's avatar
Christian Würdig committed
622
		ir_node *x;
Sebastian Hack's avatar
Sebastian Hack committed
623

Sebastian Hack's avatar
Sebastian Hack committed
624
625
626
627
		/*
		 * 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
628
		if(irn == pos)
Sebastian Hack's avatar
Sebastian Hack committed
629
			return live;
630

Christian Würdig's avatar
Christian Würdig committed
631
632
633
		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));
634

Christian Würdig's avatar
Christian Würdig committed
635
636
		if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
			pset_remove_ptr(live, irn);
637

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

Sebastian Hack's avatar
Sebastian Hack committed
641
			if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
Christian Würdig's avatar
Christian Würdig committed
642
643
644
				pset_insert_ptr(live, op);
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
645

Christian Würdig's avatar
Christian Würdig committed
646
	return live;
Sebastian Hack's avatar
Sebastian Hack committed
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
}

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
664
	if(!nodes_live_at(arch_env, cls, pos, live));
Sebastian Hack's avatar
Sebastian Hack committed
665

Christian Würdig's avatar
Christian Würdig committed
666
	n = pset_count(live);
667
668
669
670

	if(n == 0)
		return NULL;

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

Christian Würdig's avatar
Christian Würdig committed
673
674
675
676
677
	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;
	}
678

Sebastian Hack's avatar
Sebastian Hack committed
679
	perm = be_new_Perm(cls, irg, bl, n, nodes);
Christian Würdig's avatar
Christian Würdig committed
680
681
	sched_add_after(pos, perm);
	free(nodes);
682

Christian Würdig's avatar
Christian Würdig committed
683
684
685
686
	curr = perm;
	for(i = 0; i < n; ++i) {
		ir_node *copies[1];
		ir_node *perm_op = get_irn_n(perm, i);
687
		const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
688

Christian Würdig's avatar
Christian Würdig committed
689
690
691
		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);
692

Christian Würdig's avatar
Christian Würdig committed
693
694
		sched_add_after(curr, proj);
		curr = proj;
695

Christian Würdig's avatar
Christian Würdig committed
696
		copies[0] = proj;
Sebastian Hack's avatar
Sebastian Hack committed
697
		be_introduce_copies(dom_front, perm_op, 1, copies);
Christian Würdig's avatar
Christian Würdig committed
698
699
	}
	return perm;
Sebastian Hack's avatar
Sebastian Hack committed
700
}