benode.c 11.6 KB
Newer Older
Sebastian Hack's avatar
Sebastian Hack committed
1
2
3
4
5
6
7
8
9
10
/**
 * @file   benode.c
 * @date   17.05.2005
 * @author Sebastian Hack
 *
 * Backend node support.
 *
 * Copyright (C) 2005 Universitaet Karlsruhe
 * Released under the GPL
 */
Michael Beck's avatar
Michael Beck committed
11
12
13
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
Sebastian Hack's avatar
Sebastian Hack committed
14
15
16
17
18
19

#include <stdlib.h>

#include "obst.h"
#include "set.h"
#include "pmap.h"
20
#include "util.h"
Sebastian Hack's avatar
Sebastian Hack committed
21
#include "debug.h"
Sebastian Hack's avatar
Sebastian Hack committed
22
23
24
25

#include "irop_t.h"
#include "irmode_t.h"
#include "irnode_t.h"
26
#include "ircons_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
27

28
29
30
#include "be_t.h"
#include "belive_t.h"
#include "besched_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
31
32
#include "benode_t.h"

33
34
#include "beirgmod.h"

Daniel Grund's avatar
Daniel Grund committed
35
36
#define DBG_LEVEL 0

Sebastian Hack's avatar
Sebastian Hack committed
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
typedef enum _node_kind_t {
  node_kind_spill,
  node_kind_reload,
  node_kind_perm,
  node_kind_copy,
  node_kind_last
} node_kind_t;

typedef struct {
  node_kind_t kind;
  const arch_register_class_t *cls;
  ir_op *op;
  int n_pos;
  int *pos;
} be_op_t;

static int templ_pos_Spill[] = {
Sebastian Hack's avatar
Sebastian Hack committed
54
	0
Sebastian Hack's avatar
Sebastian Hack committed
55
56
57
};

static int templ_pos_Reload[] = {
Sebastian Hack's avatar
Sebastian Hack committed
58
	-1
Sebastian Hack's avatar
Sebastian Hack committed
59
60
61
};

static int templ_pos_Copy[] = {
Sebastian Hack's avatar
Sebastian Hack committed
62
	0, -1
Sebastian Hack's avatar
Sebastian Hack committed
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
};

#define ARRSIZE(x) (sizeof(x) / sizeof(x[0]))

static int cmp_op_map(const void *a, const void *b, size_t size)
{
  const be_op_t *x = a;
  const be_op_t *y = b;

  return !(x->kind == y->kind && x->cls == y->cls);
}

static be_op_t *get_op(const be_node_factory_t *fact,
    const arch_register_class_t *cls, node_kind_t kind)
{
  be_op_t templ;

  templ.kind = kind;
  templ.cls = cls;

  return set_insert(fact->ops, &templ, sizeof(templ),
      HASH_PTR(cls) + 7 * kind);
}

ir_node *new_Spill(const be_node_factory_t *factory,
    const arch_register_class_t *cls,
    ir_graph *irg, ir_node *bl, ir_node *node_to_spill)
{
  ir_node *in[1];
  ir_op *op = get_op(factory, cls, node_kind_spill)->op;

  assert(op && "Spill opcode must be present for this register class");
  in[0] = node_to_spill;

  return new_ir_node(NULL, irg, bl, op, mode_M, 1, in);
}

ir_node *new_Reload(const be_node_factory_t *factory,
Sebastian Hack's avatar
Sebastian Hack committed
101
102
    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
103
104
105
106
107
{
  ir_node *in[1];
  ir_op *op = get_op(factory, cls, node_kind_reload)->op;

  assert(op && "Reload opcode must be present for this register class");
Sebastian Hack's avatar
Sebastian Hack committed
108
  // assert(is_Spill(factory, spill_node) && "Operand of Reload must be a Spill");
Sebastian Hack's avatar
Sebastian Hack committed
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
  in[0] = spill_node;

  return new_ir_node(NULL, irg, bl, op, mode, 1, in);
}

ir_node *new_Perm(const be_node_factory_t *factory,
    const arch_register_class_t *cls,
    ir_graph *irg, ir_node *bl, int arity, ir_node **in)
{
  ir_op *op = get_op(factory, cls, node_kind_perm)->op;

  return new_ir_node(NULL, irg, bl, op, mode_T, arity, in);
}

ir_node *new_Copy(const be_node_factory_t *factory,
    const arch_register_class_t *cls,
    ir_graph *irg, ir_node *bl, ir_node *in)
{
  ir_node *ins[1];
128
  ir_op *op = get_op(factory, cls, node_kind_copy)->op;
Sebastian Hack's avatar
Sebastian Hack committed
129
130
131
132
133
134

  ins[0] = in;

  return new_ir_node(NULL, irg, bl, op, get_irn_mode(in), 1, ins);
}

Sebastian Hack's avatar
Sebastian Hack committed
135
136
137
138
ir_node *be_spill(
		const be_node_factory_t *factory,
		const arch_env_t *arch_env,
		ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
139
{
Sebastian Hack's avatar
Sebastian Hack committed
140
  const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
Sebastian Hack's avatar
Sebastian Hack committed
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
  ir_node *bl    = get_nodes_block(irn);
  ir_graph *irg  = get_irn_irg(bl);
  ir_node *spill = new_Spill(factory, cls, irg, bl, irn);

	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);
Sebastian Hack's avatar
Sebastian Hack committed
157
158
159
  return spill;
}

Sebastian Hack's avatar
Sebastian Hack committed
160
161
162
163
ir_node *be_reload(const be_node_factory_t *factory,
				   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
164
165
166
167
168
169
170
171
{
	ir_node *reload;

  ir_node *bl   = get_nodes_block(irn);
  ir_graph *irg = get_irn_irg(bl);

	assert(is_Spill(factory, spill)
			|| (is_Phi(spill) && get_irn_mode(spill) == mode_M));
Sebastian Hack's avatar
Sebastian Hack committed
172

Sebastian Hack's avatar
Sebastian Hack committed
173
  reload = new_Reload(factory, cls, irg, bl, mode, spill);
Sebastian Hack's avatar
Sebastian Hack committed
174

Sebastian Hack's avatar
Sebastian Hack committed
175
176
177
178
	set_irn_n(irn, pos, reload);
  sched_add_before(irn, reload);
  return reload;
}
Sebastian Hack's avatar
Sebastian Hack committed
179

Sebastian Hack's avatar
Sebastian Hack committed
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/**
 * 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)
{
  const ir_node *n = *node;

  if(is_Proj(n)) {
    *node = get_Proj_pred(n);
Sebastian Hack's avatar
Sebastian Hack committed
195
    def = -(get_Proj_proj(n) + 1);
Sebastian Hack's avatar
Sebastian Hack committed
196
197
198
199
200
201
202
203
204
  }

  return def;
}

static const arch_register_req_t *
be_node_get_irn_reg_req(const arch_irn_ops_t *_self,
    arch_register_req_t *req, const ir_node *irn, int pos)
{
Sebastian Hack's avatar
Sebastian Hack committed
205
206
207
	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
208

Sebastian Hack's avatar
Sebastian Hack committed
209
210
211
212
213
214
	/*
	 * were interested in an output operand, so
	 * let's resolve projs.
	 */
	if(pos < 0)
		pos = redir_proj((const ir_node **) &irn, pos);
Sebastian Hack's avatar
Sebastian Hack committed
215

Sebastian Hack's avatar
Sebastian Hack committed
216
	bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
Sebastian Hack's avatar
Sebastian Hack committed
217

Sebastian Hack's avatar
Sebastian Hack committed
218
219
	if(bo) {
		int i;
Sebastian Hack's avatar
Sebastian Hack committed
220

Sebastian Hack's avatar
Sebastian Hack committed
221
222
		req->type = arch_register_req_type_normal;
		req->cls  = bo->cls;
Sebastian Hack's avatar
Sebastian Hack committed
223

Sebastian Hack's avatar
Sebastian Hack committed
224
225
226
227
		for(i = 0; i < bo->n_pos; ++i)
			if(pos == bo->pos[i])
				return req;
	}
Sebastian Hack's avatar
Sebastian Hack committed
228

Sebastian Hack's avatar
Sebastian Hack committed
229
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
230
231
232
233
}

void
be_node_set_irn_reg(const arch_irn_ops_t *_self, ir_node *irn,
Sebastian Hack's avatar
Sebastian Hack committed
234
    const arch_register_t *reg)
Sebastian Hack's avatar
Sebastian Hack committed
235
{
Sebastian Hack's avatar
Sebastian Hack committed
236
237
238
239
240
	int pos;
	const arch_register_t **regs;
	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
241

Sebastian Hack's avatar
Sebastian Hack committed
242
243
	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
244
245
246
247

	if(!bo)
		return;

Sebastian Hack's avatar
Sebastian Hack committed
248
249
	regs = (const arch_register_t **) &irn->attr;
	regs[-pos - 1] = reg;
Sebastian Hack's avatar
Sebastian Hack committed
250
251
252
}

const arch_register_t *
Sebastian Hack's avatar
Sebastian Hack committed
253
be_node_get_irn_reg(const arch_irn_ops_t *_self, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
254
{
Sebastian Hack's avatar
Sebastian Hack committed
255
256
257
258
259
	int i, pos;
	const arch_register_t **regs;
	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
260

Sebastian Hack's avatar
Sebastian Hack committed
261
262
	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
263

Sebastian Hack's avatar
Sebastian Hack committed
264
265
	if(!bo)
		return NULL;
Daniel Grund's avatar
Daniel Grund committed
266

Sebastian Hack's avatar
Sebastian Hack committed
267
268
269
270
271
272
	for(i = 0; i < bo->n_pos; ++i) {
		if(bo->pos[i] == pos) {
			regs = (const arch_register_t **) &irn->attr;
			return regs[-pos - 1];
		}
	}
Daniel Grund's avatar
Daniel Grund committed
273

Sebastian Hack's avatar
Sebastian Hack committed
274
	return NULL;
Sebastian Hack's avatar
Sebastian Hack committed
275
276
277
278
279
280
281
282
283
284
285
286
287
}

arch_irn_class_t be_node_classify(const arch_irn_ops_t *_self, const ir_node *irn)
{
  const be_node_factory_t *factory =
    container_of(_self, const be_node_factory_t, irn_ops);

  be_op_t *bo;
  int idx;

  idx = redir_proj(&irn, 0);
  bo = pmap_get(factory->irn_op_map, get_irn_op(irn));

Sebastian Hack's avatar
Sebastian Hack committed
288
289
290
291
292
293
294
	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
295
296
		default:
		return 0;
Sebastian Hack's avatar
Sebastian Hack committed
297
298
	}

Sebastian Hack's avatar
Sebastian Hack committed
299
300
301
  return 0;
}

Sebastian Hack's avatar
Sebastian Hack committed
302
303
304
305
306
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
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
static const arch_irn_ops_t *
be_node_get_irn_ops(const arch_irn_handler_t *_self, const ir_node *irn)
{
  be_op_t *bo;
  const be_node_factory_t *factory =
    container_of(_self, const be_node_factory_t, handler);

  redir_proj(&irn, 0);
  bo = pmap_get(factory->irn_op_map, get_irn_op(irn));

  return bo ? &factory->irn_ops : NULL;
}

const arch_irn_handler_t *be_node_get_irn_handler(const be_node_factory_t *f)
{
  return &f->handler;
}

int is_Spill(const be_node_factory_t *f, const ir_node *irn)
{
  be_op_t *bo;
  bo = pmap_get(f->irn_op_map, get_irn_op(irn));
Sebastian Hack's avatar
Sebastian Hack committed
329
  return bo != NULL && bo->kind == node_kind_spill;
Sebastian Hack's avatar
Sebastian Hack committed
330
331
}

Sebastian Hack's avatar
Sebastian Hack committed
332
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
333
334
335
336
337
338
339
340
341
342
343
344
345
346
{
  char buf[256];
  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;
Sebastian Hack's avatar
Sebastian Hack committed
347
  factory->irn_ops.get_flags       = be_node_get_flags;
Sebastian Hack's avatar
Sebastian Hack committed
348

Sebastian Hack's avatar
Sebastian Hack committed
349
350
  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);
Sebastian Hack's avatar
Sebastian Hack committed
351
352
353
354
355
    be_op_t *ent;

    ent = get_op(factory, cls, node_kind_spill);
    snprintf(buf, sizeof(buf), "Spill_%s", cls->name);
    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned,
356
        0, oparity_unary, 0, 0, NULL);
Sebastian Hack's avatar
Sebastian Hack committed
357
358
359
360
361
362
    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);
    snprintf(buf, sizeof(buf), "Reload_%s", cls->name);
Sebastian Hack's avatar
Sebastian Hack committed
363
    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0,
364
        oparity_unary, 0, sizeof(const arch_register_t *), NULL);
Sebastian Hack's avatar
Sebastian Hack committed
365
366
367
368
369
370
    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);
    snprintf(buf, sizeof(buf), "Copy_%s", cls->name);
Sebastian Hack's avatar
Sebastian Hack committed
371
    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0,
372
        oparity_unary, 0, sizeof(const arch_register_t *), NULL);
Sebastian Hack's avatar
Sebastian Hack committed
373
374
375
376
377
378
    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);
    snprintf(buf, sizeof(buf), "Perm_%s", cls->name);
Sebastian Hack's avatar
Sebastian Hack committed
379
    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0,
380
        oparity_variable, 0, sizeof(const arch_register_t) * cls->n_regs, NULL);
Sebastian Hack's avatar
Sebastian Hack committed
381
382
383
    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) {
Sebastian Hack's avatar
Sebastian Hack committed
384
385
      ent->pos[j] = j;
      ent->pos[j + 1] = -(j + 1);
Sebastian Hack's avatar
Sebastian Hack committed
386
387
388
389
390
391
392
393
    }
    pmap_insert(factory->irn_op_map, ent->op, ent);

  }

  return factory;
}

Sebastian Hack's avatar
Sebastian Hack committed
394
395
396
397
ir_node *insert_Perm_after(const be_main_env_t *env,
						   const arch_register_class_t *cls,
						   dom_front_info_t *dom_front,
						   ir_node *pos)
Sebastian Hack's avatar
Sebastian Hack committed
398
{
Sebastian Hack's avatar
Sebastian Hack committed
399
400
401
402
403
404
  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                  = put_live_end(bl, pset_new_ptr_default());
  firm_dbg_module_t *dbg      = firm_dbg_register("firm.be.node");

405
406
407
  ir_node *curr, *irn, *perm, **nodes;
  int i, n;

Daniel Grund's avatar
Daniel Grund committed
408
  firm_dbg_set_mask(dbg, DBG_LEVEL);
Sebastian Hack's avatar
Sebastian Hack committed
409
  DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
410
411

  sched_foreach_reverse(bl, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
412
413
    ir_node *x;

414
415
416
417
418
419
420
	/*
	 * If we encounter the node we want to insert the Perm after,
	 * exit immediately, so that this node is still live
	 */
    if(irn == pos)
      break;

Sebastian Hack's avatar
Sebastian Hack committed
421
422
423
    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));
424

Sebastian Hack's avatar
Sebastian Hack committed
425
    if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
426
427
428
429
430
      pset_remove_ptr(live, irn);

    for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
      ir_node *op = get_irn_n(irn, i);

Sebastian Hack's avatar
Sebastian Hack committed
431
      if(arch_irn_has_reg_class(arch_env, op, -1, cls))
432
433
        pset_insert_ptr(live, op);
    }
Sebastian Hack's avatar
Sebastian Hack committed
434
435
  }

436
437
  n = pset_count(live);
  nodes = malloc(n * sizeof(nodes[0]));
Sebastian Hack's avatar
Sebastian Hack committed
438

439
440
441
  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));
442
    nodes[i] = irn;
443
  }
444

Sebastian Hack's avatar
Sebastian Hack committed
445
  perm = new_Perm(env->node_factory, cls, irg, bl, n, nodes);
446
447
448
  sched_add_after(pos, perm);
  free(nodes);

Sebastian Hack's avatar
Sebastian Hack committed
449
  curr = perm;
450
451
452
  for(i = 0; i < n; ++i) {
    ir_node *copies[1];
    ir_node *perm_op = get_irn_n(perm, i);
Sebastian Hack's avatar
Sebastian Hack committed
453
	const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
454
455
456

    ir_mode *mode = get_irn_mode(perm_op);
    ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
Sebastian Hack's avatar
Sebastian Hack committed
457
    arch_set_irn_register(arch_env, proj, reg);
458

459
460
461
462
    sched_add_after(curr, proj);
    curr = proj;

    copies[0] = proj;
Sebastian Hack's avatar
Sebastian Hack committed
463
    be_introduce_copies(dom_front, perm_op, array_size(copies), copies);
464
  }
465
  return perm;
Sebastian Hack's avatar
Sebastian Hack committed
466
}