benode.c 16.7 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
49
	node_kind_spill,
	node_kind_reload,
	node_kind_perm,
	node_kind_copy,
	node_kind_last
Sebastian Hack's avatar
Sebastian Hack committed
50
51
52
} node_kind_t;

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

60
typedef struct {
61
62
63
64
65
66
67
68
69
	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];
70
71
72
73
} be_node_attr_t;

typedef struct {
	be_node_attr_t attr;
74
75
76
	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. */
77
78
} be_spill_attr_t;

Sebastian Hack's avatar
Sebastian Hack committed
79
static int templ_pos_Spill[] = {
Sebastian Hack's avatar
Sebastian Hack committed
80
	0
Sebastian Hack's avatar
Sebastian Hack committed
81
82
83
};

static int templ_pos_Reload[] = {
Sebastian Hack's avatar
Sebastian Hack committed
84
	-1
Sebastian Hack's avatar
Sebastian Hack committed
85
86
87
};

static int templ_pos_Copy[] = {
Sebastian Hack's avatar
Sebastian Hack committed
88
	0, -1
Sebastian Hack's avatar
Sebastian Hack committed
89
90
};

91
92
93
94
95
96
97
98
99
100
101
102
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,
103
104
	NULL,
	NULL,
105
106
107
108
	dump_node,
	NULL
};

109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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;
}

127
static be_node_attr_t *init_node_attr(ir_node *irn,
128
129
130
131
									  const be_op_t *op,
									  const arch_register_class_t *cls,
									  int n_regs)

132
133
134
135
{
	be_node_attr_t *attr = (be_node_attr_t *) &irn->attr;
	int i;

136
	attr->magic   = BENODE_MAGIC;
137
	attr->n_regs  = n_regs;
138
	attr->op      = op;
139

140
141
142
143
144
145
146
	for(i = 0; i < n_regs; ++i) {
		be_reg_data_t *rd = attr->reg_data + i;

		rd->reg      = NULL;
		rd->req.cls  = cls;
		rd->req.type = arch_register_req_type_normal;
	}
147
148
149
150

	return attr;
}

Sebastian Hack's avatar
Sebastian Hack committed
151
152
153
154
#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
155
156
	const be_op_t *x = a;
	const be_op_t *y = b;
Sebastian Hack's avatar
Sebastian Hack committed
157

Christian Würdig's avatar
Christian Würdig committed
158
	return !(x->kind == y->kind && x->cls == y->cls);
Sebastian Hack's avatar
Sebastian Hack committed
159
160
161
}

static be_op_t *get_op(const be_node_factory_t *fact,
Christian Würdig's avatar
Christian Würdig committed
162
		const arch_register_class_t *cls, node_kind_t kind)
Sebastian Hack's avatar
Sebastian Hack committed
163
{
Christian Würdig's avatar
Christian Würdig committed
164
	be_op_t templ;
Sebastian Hack's avatar
Sebastian Hack committed
165

Christian Würdig's avatar
Christian Würdig committed
166
167
	templ.kind = kind;
	templ.cls = cls;
Sebastian Hack's avatar
Sebastian Hack committed
168

Christian Würdig's avatar
Christian Würdig committed
169
170
	return set_insert(fact->ops, &templ, sizeof(templ),
		HASH_PTR(cls) + 7 * kind);
Sebastian Hack's avatar
Sebastian Hack committed
171
172
173
}

ir_node *new_Spill(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
174
175
		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
176
{
177
	be_spill_attr_t *a;
178
	ir_node *irn;
Christian Würdig's avatar
Christian Würdig committed
179
	ir_node *in[1];
180
181
	be_op_t *bop = get_op(factory, cls, node_kind_spill);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
182

Christian Würdig's avatar
Christian Würdig committed
183
	assert(op && "Spill opcode must be present for this register class");
184
185
186
187
188
	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
189

Christian Würdig's avatar
Christian Würdig committed
190
	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
191
192
}

193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
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;
}

221
222
223
224
225
226
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;
}

227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
/**
 * 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);
}

243
244

unsigned get_Spill_offset(ir_node *irn)
245
246
247
248
249
250
251
{
	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");
252
		return get_Spill_offset(find_a_spill(irn));
253
254
255
256
257
258
259
260
261
	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
262
ir_node *new_Reload(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
263
264
		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
265
{
Christian Würdig's avatar
Christian Würdig committed
266
	ir_node *irn, *in[1];
267
268
	be_op_t *bop = get_op(factory, cls, node_kind_reload);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
269

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

Christian Würdig's avatar
Christian Würdig committed
273
	irn  = new_ir_node(NULL, irg, bl, op, mode, 1, in);
274
	init_node_attr(irn, bop, cls, 1);
275
276

	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
277
278
279
}

ir_node *new_Perm(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
280
281
		const arch_register_class_t *cls,
		ir_graph *irg, ir_node *bl, int arity, ir_node **in)
Sebastian Hack's avatar
Sebastian Hack committed
282
{
283
	ir_node *irn;
284
285
	be_op_t *bop = get_op(factory, cls, node_kind_perm);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
286

Christian Würdig's avatar
Christian Würdig committed
287
	irn  = new_ir_node(NULL, irg, bl, op, mode_T, arity, in);
288
	init_node_attr(irn, bop, cls, arity);
289
290

	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
291
292
293
}

ir_node *new_Copy(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
294
295
		const arch_register_class_t *cls,
		ir_graph *irg, ir_node *bl, ir_node *in)
Sebastian Hack's avatar
Sebastian Hack committed
296
{
Christian Würdig's avatar
Christian Würdig committed
297
	ir_node *irn, *ins[1];
298
299
	be_op_t *bop = get_op(factory, cls, node_kind_copy);
	ir_op *op    = bop->op;
Sebastian Hack's avatar
Sebastian Hack committed
300

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

Christian Würdig's avatar
Christian Würdig committed
303
	irn  = new_ir_node(NULL, irg, bl, op, get_irn_mode(in), 1, ins);
304
	init_node_attr(irn, bop, cls, 1);
305
306

	return irn;
Sebastian Hack's avatar
Sebastian Hack committed
307
308
}

Sebastian Hack's avatar
Sebastian Hack committed
309
310
311
ir_node *be_spill(
		const be_node_factory_t *factory,
		const arch_env_t *arch_env,
312
		ir_node *irn, ir_node *ctx)
Sebastian Hack's avatar
Sebastian Hack committed
313
{
Christian Würdig's avatar
Christian Würdig committed
314
	const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
315

Christian Würdig's avatar
Christian Würdig committed
316
317
318
	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
319
320
321
322
323
324
325
326
327
328
329
330
	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
331
	return spill;
Sebastian Hack's avatar
Sebastian Hack committed
332
333
}

Sebastian Hack's avatar
Sebastian Hack committed
334
ir_node *be_reload(const be_node_factory_t *factory,
Christian Würdig's avatar
Christian Würdig committed
335
336
337
					 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
338
339
340
{
	ir_node *reload;

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

344
	assert(be_is_Spill(spill)
Sebastian Hack's avatar
Sebastian Hack committed
345
			|| (is_Phi(spill) && get_irn_mode(spill) == mode_M));
Sebastian Hack's avatar
Sebastian Hack committed
346

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

Sebastian Hack's avatar
Sebastian Hack committed
349
	set_irn_n(irn, pos, reload);
Christian Würdig's avatar
Christian Würdig committed
350
351
	sched_add_before(irn, reload);
	return reload;
Sebastian Hack's avatar
Sebastian Hack committed
352
}
Sebastian Hack's avatar
Sebastian Hack committed
353

Sebastian Hack's avatar
Sebastian Hack committed
354
355
356
357
358
359
360
361
362
363
364
/**
 * 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
365
	const ir_node *n = *node;
Sebastian Hack's avatar
Sebastian Hack committed
366

Christian Würdig's avatar
Christian Würdig committed
367
368
369
370
	if(is_Proj(n)) {
		*node = get_Proj_pred(n);
		def = -(get_Proj_proj(n) + 1);
	}
Sebastian Hack's avatar
Sebastian Hack committed
371

Christian Würdig's avatar
Christian Würdig committed
372
	return def;
Sebastian Hack's avatar
Sebastian Hack committed
373
374
375
376
}

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
377
		arch_register_req_t *req, const ir_node *irn, int pos)
Sebastian Hack's avatar
Sebastian Hack committed
378
{
379
	/* We cannot get output requirements for tuple nodes. */
Daniel Grund's avatar
Daniel Grund committed
380
381
382
	if(get_irn_mode(irn) == mode_T && pos < 0)
		return NULL;

Sebastian Hack's avatar
Sebastian Hack committed
383
	/*
384
	 * if we're interested in an output operand (pos < 0), so let's resolve projs.
Sebastian Hack's avatar
Sebastian Hack committed
385
386
387
	 */
	if(pos < 0)
		pos = redir_proj((const ir_node **) &irn, pos);
Sebastian Hack's avatar
Sebastian Hack committed
388

389
390
391
	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
392
		int i;
Sebastian Hack's avatar
Sebastian Hack committed
393

394
395
396
397
398
399
400
401
402
403
404
405
406
407
		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) {
					req->cls = bo->cls;
					req->type = arch_register_req_type_normal;
				}

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

Sebastian Hack's avatar
Sebastian Hack committed
411
				return req;
412
413
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
414
	}
Sebastian Hack's avatar
Sebastian Hack committed
415

Sebastian Hack's avatar
Sebastian Hack committed
416
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
417
418
}

419
420
421
422
423
424
425
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
426
427
void
be_node_set_irn_reg(const arch_irn_ops_t *_self, ir_node *irn,
Christian Würdig's avatar
Christian Würdig committed
428
		const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
429
{
Sebastian Hack's avatar
Sebastian Hack committed
430
431
	int pos;
	be_op_t *bo;
432
	be_node_attr_t *attr;
Sebastian Hack's avatar
Sebastian Hack committed
433
434
	const be_node_factory_t *factory =
		container_of(_self, const be_node_factory_t, irn_ops);
Sebastian Hack's avatar
Sebastian Hack committed
435

436
	if(get_irn_mode(irn) == mode_T)
Sebastian Hack's avatar
Sebastian Hack committed
437
		return;
Daniel Grund's avatar
Daniel Grund committed
438

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

	if(!bo)
		return;

445
	attr = (be_node_attr_t *) &irn->attr;
446
	attr->reg_data[-pos - 1].reg = reg;
Sebastian Hack's avatar
Sebastian Hack committed
447
448
449
}

const arch_register_t *
Sebastian Hack's avatar
Sebastian Hack committed
450
be_node_get_irn_reg(const arch_irn_ops_t *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
451
{
Sebastian Hack's avatar
Sebastian Hack committed
452
453
454
455
	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
456

457
	if(get_irn_mode(irn) == mode_T)
Daniel Grund's avatar
Daniel Grund committed
458
459
		return NULL;

Sebastian Hack's avatar
Sebastian Hack committed
460
461
	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
462

Sebastian Hack's avatar
Sebastian Hack committed
463
464
	if(!bo)
		return NULL;
Daniel Grund's avatar
Daniel Grund committed
465

Sebastian Hack's avatar
Sebastian Hack committed
466
467
	for(i = 0; i < bo->n_pos; ++i) {
		if(bo->pos[i] == pos) {
468
			be_node_attr_t *attr = (be_node_attr_t *) &irn->attr;
469
			return attr->reg_data[-pos - 1].reg;
Sebastian Hack's avatar
Sebastian Hack committed
470
471
		}
	}
Daniel Grund's avatar
Daniel Grund committed
472

Sebastian Hack's avatar
Sebastian Hack committed
473
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
474
475
476
477
}

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
478
	const be_node_factory_t *factory = container_of(_self, const be_node_factory_t, irn_ops);
Sebastian Hack's avatar
Sebastian Hack committed
479

Christian Würdig's avatar
Christian Würdig committed
480
481
	be_op_t *bo;
	int idx;
Sebastian Hack's avatar
Sebastian Hack committed
482

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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
500
501
502
503
504
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
505
506
507
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
508
509
510
	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
511

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

Christian Würdig's avatar
Christian Würdig committed
515
	return bo ? &factory->irn_ops : NULL;
Sebastian Hack's avatar
Sebastian Hack committed
516
517
518
519
}

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
520
	return &f->handler;
Sebastian Hack's avatar
Sebastian Hack committed
521
522
}

523
int be_is_Spill(const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
524
{
525
526
527
	return is_be_kind(irn, node_kind_spill);
}

528
529
530
531
532
533
534
535
536
537
538
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)
539
540
{
	return is_be_kind(irn, node_kind_perm);
Sebastian Hack's avatar
Sebastian Hack committed
541
542
}

Sebastian Hack's avatar
Sebastian Hack committed
543
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
544
{
Christian Würdig's avatar
Christian Würdig committed
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
	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,
587
588
				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
589
590
591
592
593
594
595
596
597
598
599
600
		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
601
602
}

603
604
static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
{
605
606
	be_node_attr_t *at = (be_node_attr_t *) &irn->attr;
	const be_op_t *bo;
607
608
	int i;

609
610
611
	assert(is_be_node(irn));
	bo = at->op;

612
613
614
615
616
617
618
619
	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
620
			fprintf(f, "%s ", bo->cls->name);
621
622
			break;
		case dump_node_info_txt:
623
624
			for(i = 0; i < at->n_regs; ++i) {
				const arch_register_t *reg = at->reg_data[i].reg;
625
626
627
628
				fprintf(f, "reg #%d: %s\n", i, reg ? reg->name : "n/a");
			}

			if(bo->kind == node_kind_spill) {
629
				be_spill_attr_t *a = (be_spill_attr_t *) at;
630
631
632
633
634
				ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
			}
			break;
	}

635
	return 0;
636
637
}

Sebastian Hack's avatar
Sebastian Hack committed
638
ir_node *insert_Perm_after(const be_main_env_t *env,
Christian Würdig's avatar
Christian Würdig committed
639
640
641
							 const arch_register_class_t *cls,
							 dom_front_info_t *dom_front,
							 ir_node *pos)
Sebastian Hack's avatar
Sebastian Hack committed
642
{
Christian Würdig's avatar
Christian Würdig committed
643
644
645
646
	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();
647
	firm_dbg_module_t *dbg      = firm_dbg_register("be.node");
Sebastian Hack's avatar
Sebastian Hack committed
648

Christian Würdig's avatar
Christian Würdig committed
649
650
651
	irn_live_t *li;
	ir_node *curr, *irn, *perm, **nodes;
	int i, n;
652

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

Daniel Grund's avatar
Daniel Grund committed
655
656
657
658
659
660
661

	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
662
663
	sched_foreach_reverse(bl, irn) {
		ir_node *x;
Sebastian Hack's avatar
Sebastian Hack committed
664

665
666
667
668
	/*
	 * 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
669
670
		if(irn == pos)
			break;
671

Christian Würdig's avatar
Christian Würdig committed
672
673
674
		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));
675

Christian Würdig's avatar
Christian Würdig committed
676
677
		if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
			pset_remove_ptr(live, irn);
678

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

Christian Würdig's avatar
Christian Würdig committed
682
683
684
685
			if(arch_irn_has_reg_class(arch_env, op, -1, cls))
				pset_insert_ptr(live, op);
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
686

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

Christian Würdig's avatar
Christian Würdig committed
690
691
692
693
694
	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;
	}
695

Christian Würdig's avatar
Christian Würdig committed
696
697
698
	perm = new_Perm(env->node_factory, cls, irg, bl, n, nodes);
	sched_add_after(pos, perm);
	free(nodes);
699

Christian Würdig's avatar
Christian Würdig committed
700
701
702
703
	curr = perm;
	for(i = 0; i < n; ++i) {
		ir_node *copies[1];
		ir_node *perm_op = get_irn_n(perm, i);
704
		const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
705

Christian Würdig's avatar
Christian Würdig committed
706
707
708
		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);
709

Christian Würdig's avatar
Christian Würdig committed
710
711
		sched_add_after(curr, proj);
		curr = proj;
712

Christian Würdig's avatar
Christian Würdig committed
713
714
715
716
		copies[0] = proj;
		be_introduce_copies(dom_front, perm_op, array_size(copies), copies);
	}
	return perm;
Sebastian Hack's avatar
Sebastian Hack committed
717
}