benode.c 17.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"

Daniel Grund's avatar
Daniel Grund committed
40
41
#define DBG_LEVEL 0

42
43
#define BENODE_MAGIC FOURCC('B', 'E', 'N', 'O')

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

typedef struct {
Christian Würdig's avatar
Christian Würdig committed
54
55
56
57
58
	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
59
60
} be_op_t;

61
typedef struct {
62
63
64
65
66
67
68
69
70
	const arch_register_t *reg;
	arch_register_req_t   req;
} be_reg_data_t;

typedef struct {
	unsigned      magic;
	const be_op_t *op;
	int           n_regs;
	be_reg_data_t reg_data[1];
71
72
73
74
} be_node_attr_t;

typedef struct {
	be_node_attr_t attr;
75
76
77
	ir_node *spill_ctx;  /**< The node in whose context this spill was introduced. */
	unsigned offset;     /**< The offset of the memory location the spill writes to
						   in the spill area. */
78
79
} be_spill_attr_t;

Sebastian Hack's avatar
Sebastian Hack committed
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

ir_node *new_Keep(ir_graph *irg, ir_node *bl, int n, ir_node *in[])
{
	static ir_op *keep_op = NULL;
	ir_node *irn;

	if(!keep_op)
		keep_op = new_ir_op(get_next_ir_opcode(), "Keep", op_pin_state_pinned,
			irop_flag_keep, oparity_variable, 0, 0, NULL);

	irn = new_ir_node(NULL, irg, bl, keep_op, mode_ANY, n, in);
	keep_alive(irn);

	return irn;
}

Sebastian Hack's avatar
Sebastian Hack committed
96
static int templ_pos_Spill[] = {
Sebastian Hack's avatar
Sebastian Hack committed
97
	0
Sebastian Hack's avatar
Sebastian Hack committed
98
99
100
};

static int templ_pos_Reload[] = {
Sebastian Hack's avatar
Sebastian Hack committed
101
	-1
Sebastian Hack's avatar
Sebastian Hack committed
102
103
104
};

static int templ_pos_Copy[] = {
Sebastian Hack's avatar
Sebastian Hack committed
105
	0, -1
Sebastian Hack's avatar
Sebastian Hack committed
106
107
};

Sebastian Hack's avatar
Sebastian Hack committed
108
109
110
111
static int templ_pos_Kill[] = {
	0
};

112
113
114
115
116
117
118
119
120
121
122
123
static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason);

static const ir_op_ops be_node_ops = {
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
	NULL,
124
125
	NULL,
	NULL,
126
127
128
129
	dump_node,
	NULL
};

130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
static INLINE int is_be_node(const ir_node *irn)
{
	const be_node_attr_t *attr = (const be_node_attr_t *) &irn->attr;
	return attr->magic == BENODE_MAGIC;
}

static INLINE int is_be_kind(const ir_node *irn, node_kind_t kind)
{
	const be_node_attr_t *a = (const be_node_attr_t *) &irn->attr;
	return a->magic == BENODE_MAGIC && a->op && a->op->kind == kind;
}

static INLINE void *get_attr_and_check(ir_node *irn, node_kind_t kind)
{
	is_be_kind(irn, kind);
	return &irn->attr;
}

148
static be_node_attr_t *init_node_attr(ir_node *irn,
149
150
151
152
									  const be_op_t *op,
									  const arch_register_class_t *cls,
									  int n_regs)

153
154
155
156
{
	be_node_attr_t *attr = (be_node_attr_t *) &irn->attr;
	int i;

157
	attr->magic   = BENODE_MAGIC;
158
	attr->n_regs  = n_regs;
159
	attr->op      = op;
160

161
162
163
	for(i = 0; i < n_regs; ++i) {
		be_reg_data_t *rd = attr->reg_data + i;

Sebastian Hack's avatar
Sebastian Hack committed
164
165
166
167
		memset(&rd->req, 0, sizeof(rd->req));
		rd->reg         = NULL;
		rd->req.cls     = cls;
		rd->req.type    = arch_register_req_type_normal;
168
	}
169
170
171
172

	return attr;
}

Sebastian Hack's avatar
Sebastian Hack committed
173
174
175
176
#define ARRSIZE(x) (sizeof(x) / sizeof(x[0]))

static int cmp_op_map(const void *a, const void *b, size_t size)
{
Christian Würdig's avatar
Christian Würdig committed
177
178
	const be_op_t *x = a;
	const be_op_t *y = b;
Sebastian Hack's avatar
Sebastian Hack committed
179

Christian Würdig's avatar
Christian Würdig committed
180
	return !(x->kind == y->kind && x->cls == y->cls);
Sebastian Hack's avatar
Sebastian Hack committed
181
182
183
}

static be_op_t *get_op(const be_node_factory_t *fact,
Christian Würdig's avatar
Christian Würdig committed
184
		const arch_register_class_t *cls, node_kind_t kind)
Sebastian Hack's avatar
Sebastian Hack committed
185
{
Christian Würdig's avatar
Christian Würdig committed
186
	be_op_t templ;
Sebastian Hack's avatar
Sebastian Hack committed
187

Christian Würdig's avatar
Christian Würdig committed
188
189
	templ.kind = kind;
	templ.cls = cls;
Sebastian Hack's avatar
Sebastian Hack committed
190

Christian Würdig's avatar
Christian Würdig committed
191
192
	return set_insert(fact->ops, &templ, sizeof(templ),
		HASH_PTR(cls) + 7 * kind);
Sebastian Hack's avatar
Sebastian Hack committed
193
194
}

Sebastian Hack's avatar
Sebastian Hack committed
195
196


Sebastian Hack's avatar
Sebastian Hack committed
197
ir_node *new_Spill(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
198
199
		const arch_register_class_t *cls,
		ir_graph *irg, ir_node *bl, ir_node *node_to_spill, ir_node *ctx)
Sebastian Hack's avatar
Sebastian Hack committed
200
{
201
	be_spill_attr_t *a;
202
	ir_node *irn;
Christian Würdig's avatar
Christian Würdig committed
203
	ir_node *in[1];
204
205
	be_op_t *bop = get_op(factory, cls, node_kind_spill);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
206

Christian Würdig's avatar
Christian Würdig committed
207
	assert(op && "Spill opcode must be present for this register class");
208
209
210
211
212
	in[0]        = node_to_spill;
	irn          = new_ir_node(NULL, irg, bl, op, mode_M, 1, in);
	a            = (be_spill_attr_t *) init_node_attr(irn, bop, cls, 0);
	a->spill_ctx = ctx;
	a->offset    = 0;
Sebastian Hack's avatar
Sebastian Hack committed
213

Christian Würdig's avatar
Christian Würdig committed
214
	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
215
216
}

217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
void set_Spill_offset(ir_node *irn, unsigned offset)
{
	be_spill_attr_t *a = (be_spill_attr_t *) &irn->attr;
	assert(is_be_kind(irn, node_kind_spill));
	a->offset = offset;
}

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

		else if(is_be_kind(irn, node_kind_spill))
			return irn;
	}

	return NULL;
}

245
246
247
248
249
250
ir_node *get_Spill_context(const ir_node *irn) {
	be_spill_attr_t *a = (be_spill_attr_t *) &irn->attr;
	assert(is_be_kind(irn, node_kind_spill));
	return a->spill_ctx;
}

251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
/**
 * 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;

	assert(is_be_kind(irn, node_kind_reload));
	set_irg_visited(irg, visited_nr);
	return find_a_spill_walker(irn, visited_nr);
}

267
268

unsigned get_Spill_offset(ir_node *irn)
269
270
271
272
273
274
275
{
	be_node_attr_t *a = (be_node_attr_t *) &irn->attr;
	assert(is_be_node(irn));

	switch(a->op->kind) {
	case node_kind_reload:
		assert(0 && "not yet implemented");
276
		return get_Spill_offset(find_a_spill(irn));
277
278
279
280
281
282
283
284
285
	case node_kind_spill:
		return ((be_spill_attr_t *) a)->offset;
	default:
		assert(0 && "Illegal node kind (spill/reload required)");
	}

	return 0;
}

Sebastian Hack's avatar
Sebastian Hack committed
286
ir_node *new_Reload(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
287
288
		const arch_register_class_t *cls, ir_graph *irg,
		ir_node *bl, ir_mode *mode, ir_node *spill_node)
Sebastian Hack's avatar
Sebastian Hack committed
289
{
Christian Würdig's avatar
Christian Würdig committed
290
	ir_node *irn, *in[1];
291
292
	be_op_t *bop = get_op(factory, cls, node_kind_reload);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
293

Christian Würdig's avatar
Christian Würdig committed
294
295
	assert(op && "Reload opcode must be present for this register class");
	in[0] = spill_node;
Sebastian Hack's avatar
Sebastian Hack committed
296

Christian Würdig's avatar
Christian Würdig committed
297
	irn  = new_ir_node(NULL, irg, bl, op, mode, 1, in);
298
	init_node_attr(irn, bop, cls, 1);
299
300

	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
301
302
303
}

ir_node *new_Perm(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
304
305
		const arch_register_class_t *cls,
		ir_graph *irg, ir_node *bl, int arity, ir_node **in)
Sebastian Hack's avatar
Sebastian Hack committed
306
{
307
	ir_node *irn;
308
309
	be_op_t *bop = get_op(factory, cls, node_kind_perm);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
310

Christian Würdig's avatar
Christian Würdig committed
311
	irn  = new_ir_node(NULL, irg, bl, op, mode_T, arity, in);
312
	init_node_attr(irn, bop, cls, arity);
313
314

	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
315
316
317
}

ir_node *new_Copy(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
318
319
		const arch_register_class_t *cls,
		ir_graph *irg, ir_node *bl, ir_node *in)
Sebastian Hack's avatar
Sebastian Hack committed
320
{
Christian Würdig's avatar
Christian Würdig committed
321
	ir_node *irn, *ins[1];
322
323
	be_op_t *bop = get_op(factory, cls, node_kind_copy);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
324

Christian Würdig's avatar
Christian Würdig committed
325
	ins[0] = in;
Sebastian Hack's avatar
Sebastian Hack committed
326

Christian Würdig's avatar
Christian Würdig committed
327
	irn  = new_ir_node(NULL, irg, bl, op, get_irn_mode(in), 1, ins);
328
	init_node_attr(irn, bop, cls, 1);
329
330

	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
331
332
}

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

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

Sebastian Hack's avatar
Sebastian Hack committed
358
ir_node *be_reload(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
359
360
361
					 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

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

Christian Würdig's avatar
Christian Würdig committed
371
	reload = new_Reload(factory, cls, irg, bl, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
372

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

Sebastian Hack's avatar
Sebastian Hack committed
378
379
380
381
382
383
384
385
386
387
388
/**
 * If the node is a proj, reset the node to the proj's target and return
 * the proj number.
 * @param node The address of a node pointer.
 * @param def  A default value.
 * @return     If *node is a Proj, *node is set to the Proj's target and
 *             the Proj number is returned. Else *node remains the same and @p def
 *             is returned.
 */
static int redir_proj(const ir_node **node, int def)
{
Christian Würdig's avatar
Christian Würdig committed
389
	const ir_node *n = *node;
Sebastian Hack's avatar
Sebastian Hack committed
390

Christian Würdig's avatar
Christian Würdig committed
391
392
393
394
	if(is_Proj(n)) {
		*node = get_Proj_pred(n);
		def = -(get_Proj_proj(n) + 1);
	}
Sebastian Hack's avatar
Sebastian Hack committed
395

Christian Würdig's avatar
Christian Würdig committed
396
	return def;
Sebastian Hack's avatar
Sebastian Hack committed
397
398
399
400
}

static const arch_register_req_t *
be_node_get_irn_reg_req(const arch_irn_ops_t *_self,
Sebastian Hack's avatar
Sebastian Hack committed
401
		arch_register_req_t *req, const ir_node *irn, int pos)
Sebastian Hack's avatar
Sebastian Hack committed
402
{
403
	/* We cannot get output requirements for tuple nodes. */
Daniel Grund's avatar
Daniel Grund committed
404
405
406
	if(get_irn_mode(irn) == mode_T && pos < 0)
		return NULL;

Sebastian Hack's avatar
Sebastian Hack committed
407
	/*
408
	 * if we're interested in an output operand (pos < 0), so let's resolve projs.
Sebastian Hack's avatar
Sebastian Hack committed
409
410
411
	 */
	if(pos < 0)
		pos = redir_proj((const ir_node **) &irn, pos);
Sebastian Hack's avatar
Sebastian Hack committed
412

413
414
415
	if(is_be_node(irn)) {
		const be_node_attr_t *a = (const be_node_attr_t *) &irn->attr;
		const be_op_t *bo       = a->op;
Sebastian Hack's avatar
Sebastian Hack committed
416
		int i;
Sebastian Hack's avatar
Sebastian Hack committed
417

418
419
420
421
422
423
		for(i = 0; i < bo->n_pos; ++i) {
			if(pos == bo->pos[i]) {

				/* be nodes have no input constraints.
				   so return normal register requirements. */
				if(pos >= 0) {
Sebastian Hack's avatar
Sebastian Hack committed
424
					memset(req, 0, sizeof(req[0]));
425
426
427
428
429
430
431
432
					req->cls = bo->cls;
					req->type = arch_register_req_type_normal;
				}

				/*
				 * if an output requirement is requested,
				 * return the one stored in the node.
				 */
433
434
				else
					*req = a->reg_data[-pos - 1].req;
Sebastian Hack's avatar
Sebastian Hack committed
435

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

Sebastian Hack's avatar
Sebastian Hack committed
441
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
442
443
}

444
445
446
447
448
449
450
void be_set_Perm_out_req(ir_node *irn, int pos, const arch_register_req_t *req)
{
	be_node_attr_t *a = get_attr_and_check(irn, node_kind_perm);
	assert(pos >= 0 && pos < get_irn_arity(irn) && "position out of range");
	a->reg_data[pos].req = *req;
}

Sebastian Hack's avatar
Sebastian Hack committed
451
452
void
be_node_set_irn_reg(const arch_irn_ops_t *_self, ir_node *irn,
Christian Würdig's avatar
Christian Würdig committed
453
		const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
454
{
Sebastian Hack's avatar
Sebastian Hack committed
455
456
	int pos;
	be_op_t *bo;
457
	be_node_attr_t *attr;
Sebastian Hack's avatar
Sebastian Hack committed
458
459
	const be_node_factory_t *factory =
		container_of(_self, const be_node_factory_t, irn_ops);
Sebastian Hack's avatar
Sebastian Hack committed
460

461
	if(get_irn_mode(irn) == mode_T)
Sebastian Hack's avatar
Sebastian Hack committed
462
		return;
Daniel Grund's avatar
Daniel Grund committed
463

Sebastian Hack's avatar
Sebastian Hack committed
464
465
	pos = redir_proj((const ir_node **) &irn, -1);
	bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
Daniel Grund's avatar
Daniel Grund committed
466
467
468
469

	if(!bo)
		return;

470
	attr = (be_node_attr_t *) &irn->attr;
471
	attr->reg_data[-pos - 1].reg = reg;
Sebastian Hack's avatar
Sebastian Hack committed
472
473
474
}

const arch_register_t *
Sebastian Hack's avatar
Sebastian Hack committed
475
be_node_get_irn_reg(const arch_irn_ops_t *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
476
{
Sebastian Hack's avatar
Sebastian Hack committed
477
478
479
480
	int i, pos;
	be_op_t *bo;
	const be_node_factory_t *factory =
		container_of(_self, const be_node_factory_t, irn_ops);
Sebastian Hack's avatar
Sebastian Hack committed
481

482
	if(get_irn_mode(irn) == mode_T)
Daniel Grund's avatar
Daniel Grund committed
483
484
		return NULL;

Sebastian Hack's avatar
Sebastian Hack committed
485
486
	pos = redir_proj((const ir_node **) &irn, -1);
	bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
Daniel Grund's avatar
Daniel Grund committed
487

Sebastian Hack's avatar
Sebastian Hack committed
488
489
	if(!bo)
		return NULL;
Daniel Grund's avatar
Daniel Grund committed
490

Sebastian Hack's avatar
Sebastian Hack committed
491
492
	for(i = 0; i < bo->n_pos; ++i) {
		if(bo->pos[i] == pos) {
493
			be_node_attr_t *attr = (be_node_attr_t *) &irn->attr;
494
			return attr->reg_data[-pos - 1].reg;
Sebastian Hack's avatar
Sebastian Hack committed
495
496
		}
	}
Daniel Grund's avatar
Daniel Grund committed
497

Sebastian Hack's avatar
Sebastian Hack committed
498
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
499
500
501
502
}

arch_irn_class_t be_node_classify(const arch_irn_ops_t *_self, const ir_node *irn)
{
Christian Würdig's avatar
Christian Würdig committed
503
	const be_node_factory_t *factory = container_of(_self, const be_node_factory_t, irn_ops);
Sebastian Hack's avatar
Sebastian Hack committed
504

Christian Würdig's avatar
Christian Würdig committed
505
506
	be_op_t *bo;
	int idx;
Sebastian Hack's avatar
Sebastian Hack committed
507

Christian Würdig's avatar
Christian Würdig committed
508
509
	idx = redir_proj(&irn, 0);
	bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
Sebastian Hack's avatar
Sebastian Hack committed
510

Sebastian Hack's avatar
Sebastian Hack committed
511
512
513
514
515
516
517
	switch(bo->kind) {
#define XXX(a) case node_kind_ ## a: return arch_irn_class_ ## a;
		XXX(spill)
		XXX(reload)
		XXX(perm)
		XXX(copy)
#undef XXX
Sebastian Hack's avatar
Sebastian Hack committed
518
519
		default:
		return 0;
Sebastian Hack's avatar
Sebastian Hack committed
520
521
	}

Christian Würdig's avatar
Christian Würdig committed
522
	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
523
524
}

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

Sebastian Hack's avatar
Sebastian Hack committed
530
531
532
static const arch_irn_ops_t *
be_node_get_irn_ops(const arch_irn_handler_t *_self, const ir_node *irn)
{
Christian Würdig's avatar
Christian Würdig committed
533
534
535
	be_op_t *bo;
	const be_node_factory_t *factory =
		container_of(_self, const be_node_factory_t, handler);
Sebastian Hack's avatar
Sebastian Hack committed
536

Christian Würdig's avatar
Christian Würdig committed
537
538
	redir_proj(&irn, 0);
	bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
Sebastian Hack's avatar
Sebastian Hack committed
539

Christian Würdig's avatar
Christian Würdig committed
540
	return bo ? &factory->irn_ops : NULL;
Sebastian Hack's avatar
Sebastian Hack committed
541
542
543
544
}

const arch_irn_handler_t *be_node_get_irn_handler(const be_node_factory_t *f)
{
Christian Würdig's avatar
Christian Würdig committed
545
	return &f->handler;
Sebastian Hack's avatar
Sebastian Hack committed
546
547
}

548
int be_is_Spill(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
549
{
550
551
552
	return is_be_kind(irn, node_kind_spill);
}

553
554
555
556
557
558
559
560
561
562
563
int be_is_Reload(const ir_node *irn)
{
	return is_be_kind(irn, node_kind_reload);
}

int be_is_Copy(const ir_node *irn)
{
	return is_be_kind(irn, node_kind_copy);
}

int be_is_Perm(const ir_node *irn)
564
565
{
	return is_be_kind(irn, node_kind_perm);
Sebastian Hack's avatar
Sebastian Hack committed
566
567
}

Sebastian Hack's avatar
Sebastian Hack committed
568

Sebastian Hack's avatar
Sebastian Hack committed
569
be_node_factory_t *be_node_factory_init(be_node_factory_t *factory, const arch_isa_t *isa)
Sebastian Hack's avatar
Sebastian Hack committed
570
{
Christian Würdig's avatar
Christian Würdig committed
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
	int i, j, n;

	factory->ops = new_set(cmp_op_map, 64);
	factory->irn_op_map = pmap_create();
	obstack_init(&factory->obst);

	factory->handler.get_irn_ops = be_node_get_irn_ops;

	factory->irn_ops.get_irn_reg_req = be_node_get_irn_reg_req;
	factory->irn_ops.set_irn_reg     = be_node_set_irn_reg;
	factory->irn_ops.get_irn_reg     = be_node_get_irn_reg;
	factory->irn_ops.classify        = be_node_classify;
	factory->irn_ops.get_flags       = be_node_get_flags;

	for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
		const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
		be_op_t *ent;

		ent = get_op(factory, cls, node_kind_spill);
		ent->op = new_ir_op(get_next_ir_opcode(), "Spill", op_pin_state_pinned,
				0, oparity_unary, 0, sizeof(be_spill_attr_t), &be_node_ops);
		ent->n_pos = ARRSIZE(templ_pos_Spill);
		ent->pos = templ_pos_Spill;
		pmap_insert(factory->irn_op_map, ent->op, ent);

		ent = get_op(factory, cls, node_kind_reload);
		ent->op = new_ir_op(get_next_ir_opcode(), "Reload", op_pin_state_pinned, 0,
				oparity_unary, 0, sizeof(be_node_attr_t), &be_node_ops);
		ent->n_pos = ARRSIZE(templ_pos_Reload);
		ent->pos = templ_pos_Reload;
		pmap_insert(factory->irn_op_map, ent->op, ent);

		ent = get_op(factory, cls, node_kind_copy);
		ent->op = new_ir_op(get_next_ir_opcode(), "Copy", op_pin_state_pinned, 0,
				oparity_unary, 0, sizeof(be_node_attr_t), &be_node_ops);
		ent->n_pos = ARRSIZE(templ_pos_Copy);
		ent->pos = templ_pos_Copy;
		pmap_insert(factory->irn_op_map, ent->op, ent);

		ent = get_op(factory, cls, node_kind_perm);
		ent->op = new_ir_op(get_next_ir_opcode(), "Perm", op_pin_state_pinned, 0,
				oparity_variable, 0,
613
614
				sizeof(be_node_attr_t)
				+ sizeof(be_reg_data_t) * cls->n_regs, &be_node_ops);
Christian Würdig's avatar
Christian Würdig committed
615
616
617
618
619
620
621
622
623
624
625
626
		ent->n_pos = 2 * cls->n_regs;
		ent->pos = obstack_alloc(&factory->obst, sizeof(ent->pos[0]) * ent->n_pos);
		for(j = 0; j < ent->n_pos; j += 2) {
			int k = j / 2;
			ent->pos[j] = k;
			ent->pos[j + 1] = -(k + 1);
		}
		pmap_insert(factory->irn_op_map, ent->op, ent);

	}

	return factory;
Sebastian Hack's avatar
Sebastian Hack committed
627
628
}

629
630
static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
{
631
632
	be_node_attr_t *at = (be_node_attr_t *) &irn->attr;
	const be_op_t *bo;
633
634
	int i;

635
636
637
	assert(is_be_node(irn));
	bo = at->op;

638
639
640
641
642
643
644
645
	switch(reason) {
		case dump_node_opcode_txt:
			fprintf(f, get_op_name(bo->op));
			break;
		case dump_node_mode_txt:
			fprintf(f, get_mode_name(get_irn_mode(irn)));
			break;
		case dump_node_nodeattr_txt:
Daniel Grund's avatar
Daniel Grund committed
646
			fprintf(f, "%s ", bo->cls->name);
647
648
			break;
		case dump_node_info_txt:
649
650
			for(i = 0; i < at->n_regs; ++i) {
				const arch_register_t *reg = at->reg_data[i].reg;
651
652
653
654
				fprintf(f, "reg #%d: %s\n", i, reg ? reg->name : "n/a");
			}

			if(bo->kind == node_kind_spill) {
655
				be_spill_attr_t *a = (be_spill_attr_t *) at;
656
				ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
Sebastian Hack's avatar
Sebastian Hack committed
657
				ir_fprintf(f, "spill offset: %u\n", a->offset);
658
659
660
661
			}
			break;
	}

662
	return 0;
663
664
}

Sebastian Hack's avatar
Sebastian Hack committed
665
ir_node *insert_Perm_after(const be_main_env_t *env,
Christian Würdig's avatar
Christian Würdig committed
666
667
668
							 const arch_register_class_t *cls,
							 dom_front_info_t *dom_front,
							 ir_node *pos)
Sebastian Hack's avatar
Sebastian Hack committed
669
{
Christian Würdig's avatar
Christian Würdig committed
670
671
672
673
	const arch_env_t *arch_env  = env->arch_env;
	ir_node *bl                 = is_Block(pos) ? pos : get_nodes_block(pos);
	ir_graph *irg               = get_irn_irg(bl);
	pset *live                  = pset_new_ptr_default();
674
	firm_dbg_module_t *dbg      = firm_dbg_register("be.node");
Sebastian Hack's avatar
Sebastian Hack committed
675

Christian Würdig's avatar
Christian Würdig committed
676
677
678
	irn_live_t *li;
	ir_node *curr, *irn, *perm, **nodes;
	int i, n;
679

Christian Würdig's avatar
Christian Würdig committed
680
	DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
681

Daniel Grund's avatar
Daniel Grund committed
682
683
684
685
686
687
688

	live_foreach(bl, li) {
		ir_node *irn = (ir_node *) li->irn;
		if(live_is_end(li) && arch_irn_has_reg_class(arch_env, irn, -1, cls))
			pset_insert_ptr(live, irn);
	}

Christian Würdig's avatar
Christian Würdig committed
689
690
	sched_foreach_reverse(bl, irn) {
		ir_node *x;
Sebastian Hack's avatar
Sebastian Hack committed
691

692
693
694
695
	/*
	 * 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
696
697
		if(irn == pos)
			break;
698

Christian Würdig's avatar
Christian Würdig committed
699
700
701
		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));
702

Christian Würdig's avatar
Christian Würdig committed
703
704
		if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
			pset_remove_ptr(live, irn);
705

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

Christian Würdig's avatar
Christian Würdig committed
709
710
711
712
			if(arch_irn_has_reg_class(arch_env, op, -1, cls))
				pset_insert_ptr(live, op);
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
713

Christian Würdig's avatar
Christian Würdig committed
714
715
	n = pset_count(live);
	nodes = malloc(n * sizeof(nodes[0]));
Sebastian Hack's avatar
Sebastian Hack committed
716

Christian Würdig's avatar
Christian Würdig committed
717
718
719
720
721
	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;
	}
722

Christian Würdig's avatar
Christian Würdig committed
723
724
725
	perm = new_Perm(env->node_factory, cls, irg, bl, n, nodes);
	sched_add_after(pos, perm);
	free(nodes);
726

Christian Würdig's avatar
Christian Würdig committed
727
728
729
730
	curr = perm;
	for(i = 0; i < n; ++i) {
		ir_node *copies[1];
		ir_node *perm_op = get_irn_n(perm, i);
731
		const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
732

Christian Würdig's avatar
Christian Würdig committed
733
734
735
		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);
736

Christian Würdig's avatar
Christian Würdig committed
737
738
		sched_add_after(curr, proj);
		curr = proj;
739

Christian Würdig's avatar
Christian Würdig committed
740
741
742
743
		copies[0] = proj;
		be_introduce_copies(dom_front, perm_op, array_size(copies), copies);
	}
	return perm;
Sebastian Hack's avatar
Sebastian Hack committed
744
}