nsz Git - libfirm/blob - ir/be/benode.c

   1 /**
   2  * @file   benode.c
   3  * @date   17.05.2005
   4  * @author Sebastian Hack
   5  *
   6  * Backend node support.
   7  *
   8  * This file provdies Perm, Copy, Spill and Reload nodes.
   9  *
  10  * Copyright (C) 2005 Universitaet Karlsruhe
  11  * Released under the GPL
  12  */
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include "config.h"
  16 #endif
  17
  18 #include <stdlib.h>
  19
  20 #include "obst.h"
  21 #include "set.h"
  22 #include "pmap.h"
  23 #include "util.h"
  24 #include "debug.h"
  25 #include "fourcc.h"
  26 #include "bitfiddle.h"
  27
  28 #include "irop_t.h"
  29 #include "irmode_t.h"
  30 #include "irnode_t.h"
  31 #include "ircons_t.h"
  32 #include "irprintf.h"
  33 #include "irgwalk.h"
  34
  35 #include "be_t.h"
  36 #include "belive_t.h"
  37 #include "besched_t.h"
  38 #include "benode_t.h"
  39
  40 #include "beirgmod.h"
  41
  42 #define OUT_POS(x) (-((x) + 1))
  43
  44 /* Sometimes we want to put const nodes into get_irn_generic_attr ... */
  45 #define get_irn_attr(irn) get_irn_generic_attr((ir_node *) (irn))
  46
  47 static unsigned be_node_tag = FOURCC('B', 'E', 'N', 'O');
  48
  49 #if 0
  50 typedef enum _node_kind_t {
  51         node_kind_spill,
  52         node_kind_reload,
  53         node_kind_perm,
  54         node_kind_copy,
  55         node_kind_kill,
  56         node_kind_last
  57 } node_kind_t;
  58 #endif
  59
  60 typedef enum {
  61         be_req_kind_old_limited,
  62         be_req_kind_negate_old_limited,
  63         be_req_kind_single_reg
  64 } be_req_kind_t;
  65
  66 typedef struct {
  67         arch_register_req_t req;
  68         be_req_kind_t       kind;
  69         arch_irn_flags_t    flags;
  70         union {
  71                 struct {
  72                         void (*old_limited)(void *ptr, bitset_t *bs);
  73                         void *old_limited_env;
  74                 } old_limited;
  75
  76                 const arch_register_t *single_reg;
  77         } x;
  78 } be_req_t;
  79
  80 typedef struct {
  81         const arch_register_t *reg;
  82         be_req_t              req;
  83         be_req_t              in_req;
  84 } be_reg_data_t;
  85
  86 typedef struct {
  87         int                         max_reg_data;
  88         be_reg_data_t               *reg_data;
  89 } be_node_attr_t;
  90
  91 typedef struct {
  92         be_node_attr_t node_attr;
  93         int offset;           /**< The offset by which the stack shall be increased/decreased. */
  94         be_stack_dir_t dir;   /**< The direction in which the stack shall be modified (along or in the other direction). */
  95 } be_stack_attr_t;
  96
  97 typedef struct {
  98         be_node_attr_t node_attr;
  99         entity *ent;
 100         int offset;
 101 } be_frame_attr_t;
 102
 103 typedef struct {
 104         be_node_attr_t node_attr;
 105         entity *ent;
 106 } be_call_attr_t;
 107
 108 typedef struct {
 109         be_frame_attr_t frame_attr;
 110         ir_node *spill_ctx;  /**< The node in whose context this spill was introduced. */
 111 } be_spill_attr_t;
 112
 113 ir_op *op_be_Spill;
 114 ir_op *op_be_Reload;
 115 ir_op *op_be_Perm;
 116 ir_op *op_be_Copy;
 117 ir_op *op_be_Keep;
 118 ir_op *op_be_Call;
 119 ir_op *op_be_Return;
 120 ir_op *op_be_IncSP;
 121 ir_op *op_be_Alloca;
 122 ir_op *op_be_SetSP;
 123 ir_op *op_be_RegParams;
 124 ir_op *op_be_StackParam;
 125 ir_op *op_be_FrameAddr;
 126 ir_op *op_be_FrameLoad;
 127 ir_op *op_be_FrameStore;
 128
 129 static int beo_base = -1;
 130
 131 static const ir_op_ops be_node_op_ops;
 132
 133 #define N   irop_flag_none
 134 #define L   irop_flag_labeled
 135 #define C   irop_flag_commutative
 136 #define X   irop_flag_cfopcode
 137 #define I   irop_flag_ip_cfopcode
 138 #define F   irop_flag_fragile
 139 #define Y   irop_flag_forking
 140 #define H   irop_flag_highlevel
 141 #define c   irop_flag_constlike
 142 #define K   irop_flag_keep
 143
 144 void be_node_init(void) {
 145         static int inited = 0;
 146
 147         if(inited)
 148                 return;
 149
 150         inited = 1;
 151
 152         /* Acquire all needed opcodes. */
 153         beo_base = get_next_ir_opcodes(beo_Last - 1);
 154
 155         op_be_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);
 156         op_be_Reload     = new_ir_op(beo_base + beo_Reload,     "Reload",     op_pin_state_mem_pinned, N, oparity_zero,     0, sizeof(be_frame_attr_t), &be_node_op_ops);
 157         op_be_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);
 158         op_be_Copy       = new_ir_op(beo_base + beo_Copy,       "Copy",       op_pin_state_floats,     N, oparity_unary,    0, sizeof(be_node_attr_t),  &be_node_op_ops);
 159         op_be_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);
 160         op_be_Call       = new_ir_op(beo_base + beo_Call,       "Call",       op_pin_state_pinned,     N, oparity_variable, 0, sizeof(be_call_attr_t),  &be_node_op_ops);
 161         op_be_Return     = new_ir_op(beo_base + beo_Return,     "Return",     op_pin_state_pinned,     X, oparity_variable, 0, sizeof(be_node_attr_t),  &be_node_op_ops);
 162         op_be_Alloca     = new_ir_op(beo_base + beo_Alloca,     "Alloca",     op_pin_state_pinned,     N, oparity_unary,    0, sizeof(be_node_attr_t),  &be_node_op_ops);
 163         op_be_SetSP      = new_ir_op(beo_base + beo_SetSP,      "SetSP",      op_pin_state_pinned,     N, oparity_binary,   0, sizeof(be_stack_attr_t), &be_node_op_ops);
 164         op_be_IncSP      = new_ir_op(beo_base + beo_IncSP,      "IncSP",      op_pin_state_pinned,     N, oparity_binary,   0, sizeof(be_stack_attr_t), &be_node_op_ops);
 165         op_be_RegParams  = new_ir_op(beo_base + beo_RegParams,  "RegParams",  op_pin_state_pinned,     N, oparity_zero,     0, sizeof(be_node_attr_t),  &be_node_op_ops);
 166         op_be_StackParam = new_ir_op(beo_base + beo_StackParam, "StackParam", op_pin_state_pinned,     N, oparity_unary,    0, sizeof(be_frame_attr_t), &be_node_op_ops);
 167         op_be_FrameAddr  = new_ir_op(beo_base + beo_FrameAddr,  "FrameAddr",  op_pin_state_pinned,     N, oparity_binary,   0, sizeof(be_frame_attr_t), &be_node_op_ops);
 168         op_be_FrameLoad  = new_ir_op(beo_base + beo_FrameLoad,  "FrameLoad",  op_pin_state_pinned,     N, oparity_any,      0, sizeof(be_frame_attr_t), &be_node_op_ops);
 169         op_be_FrameStore = new_ir_op(beo_base + beo_FrameStore, "FrameStore", op_pin_state_pinned,     N, oparity_any,      0, sizeof(be_frame_attr_t), &be_node_op_ops);
 170
 171         set_op_tag(op_be_Spill,      &be_node_tag);
 172         set_op_tag(op_be_Reload,     &be_node_tag);
 173         set_op_tag(op_be_Perm,       &be_node_tag);
 174         set_op_tag(op_be_Copy,       &be_node_tag);
 175         set_op_tag(op_be_Keep,       &be_node_tag);
 176         set_op_tag(op_be_Call,       &be_node_tag);
 177         set_op_tag(op_be_Return,     &be_node_tag);
 178         set_op_tag(op_be_Alloca,     &be_node_tag);
 179         set_op_tag(op_be_SetSP,      &be_node_tag);
 180         set_op_tag(op_be_IncSP,      &be_node_tag);
 181         set_op_tag(op_be_RegParams,  &be_node_tag);
 182         set_op_tag(op_be_StackParam, &be_node_tag);
 183         set_op_tag(op_be_FrameLoad,  &be_node_tag);
 184         set_op_tag(op_be_FrameStore, &be_node_tag);
 185         set_op_tag(op_be_FrameAddr,  &be_node_tag);
 186 }
 187
 188 static void *init_node_attr(ir_node* irn, int max_reg_data)
 189 {
 190         ir_graph *irg     = get_irn_irg(irn);
 191         be_node_attr_t *a = get_irn_attr(irn);
 192
 193         memset(a, 0, sizeof(get_op_attr_size(get_irn_op(irn))));
 194         a->max_reg_data = max_reg_data;
 195         a->reg_data     = NULL;
 196
 197         if(max_reg_data > 0) {
 198                 int i;
 199
 200                 a->reg_data = NEW_ARR_D(be_reg_data_t, get_irg_obstack(irg), max_reg_data);
 201                 memset(a->reg_data, 0, max_reg_data * sizeof(a->reg_data[0]));
 202                 for(i = 0; i < max_reg_data; ++i) {
 203                         a->reg_data[i].req.req.cls  = NULL;
 204                         a->reg_data[i].req.req.type = arch_register_req_type_none;
 205                 }
 206         }
 207
 208         return a;
 209 }
 210
 211 static INLINE int is_be_node(const ir_node *irn)
 212 {
 213         return get_op_tag(get_irn_op(irn)) == &be_node_tag;
 214 }
 215
 216 be_opcode_t be_get_irn_opcode(const ir_node *irn)
 217 {
 218         return is_be_node(irn) ? get_irn_opcode(irn) - beo_base : beo_NoBeOp;
 219 }
 220
 221 static int redir_proj(const ir_node **node, int pos)
 222 {
 223         const ir_node *n = *node;
 224
 225         if(is_Proj(n)) {
 226                 ir_node *irn;
 227
 228                 assert(pos == -1 && "Illegal pos for a Proj");
 229                 *node = irn = get_Proj_pred(n);
 230                 if(is_Proj(irn)) {
 231                         assert(get_irn_mode(irn) == mode_T);
 232                         *node = get_Proj_pred(irn);
 233                 }
 234                 return get_Proj_proj(n);
 235         }
 236
 237         return 0;
 238 }
 239
 240 static void
 241 be_node_set_irn_reg(const void *_self, ir_node *irn, const arch_register_t *reg)
 242 {
 243         int out_pos;
 244         be_node_attr_t *a;
 245
 246         out_pos = redir_proj((const ir_node **) &irn, -1);
 247         a       = get_irn_attr(irn);
 248
 249         assert(is_be_node(irn));
 250         assert(out_pos < a->max_reg_data && "position too high");
 251         a->reg_data[out_pos].reg = reg;
 252 }
 253
 254
 255 ir_node *be_new_Spill(const arch_register_class_t *cls, const arch_register_class_t *cls_frame, ir_graph *irg, ir_node *bl, ir_node *frame, ir_node *to_spill, ir_node *ctx)
 256 {
 257         be_spill_attr_t *a;
 258         ir_node *in[2];
 259         ir_node *res;
 260
 261         in[0] = frame;
 262         in[1] = to_spill;
 263         res   = new_ir_node(NULL, irg, bl, op_be_Spill, mode_M, 2, in);
 264         a     = init_node_attr(res, 2);
 265         a->frame_attr.ent = NULL;
 266         a->frame_attr.offset = 0;
 267         a->spill_ctx = ctx;
 268
 269         be_node_set_reg_class(res, 0, cls_frame);
 270         be_node_set_reg_class(res, 1, cls);
 271         return res;
 272 }
 273
 274 ir_node *be_new_Reload(const arch_register_class_t *cls, const arch_register_class_t *cls_frame, ir_graph *irg, ir_node *bl, ir_node *frame, ir_node *mem, ir_mode *mode)
 275 {
 276         ir_node *in[2];
 277         ir_node *res;
 278
 279         in[0] = frame;
 280         in[1] = mem;
 281         res   = new_ir_node(NULL, irg, bl, op_be_Reload, mode, 2, in);
 282         init_node_attr(res, 2);
 283         be_node_set_reg_class(res, 0, cls_frame);
 284         be_node_set_reg_class(res, -1, cls);
 285         return res;
 286 }
 287
 288 ir_node *(be_get_Reload_mem)(const ir_node *irn)
 289 {
 290         assert(be_is_Reload(irn));
 291         return get_irn_n(irn, 1);
 292 }
 293
 294 ir_node *be_new_Perm(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 295 {
 296         int i;
 297         ir_node *irn = new_ir_node(NULL, irg, bl, op_be_Perm, mode_T, n, in);
 298         init_node_attr(irn, n);
 299         for(i = 0; i < n; ++i) {
 300                 be_node_set_reg_class(irn, i, cls);
 301                 be_node_set_reg_class(irn, OUT_POS(i), cls);
 302         }
 303
 304         return irn;
 305 }
 306
 307 ir_node *be_new_Copy(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *op)
 308 {
 309         ir_node *in[1];
 310         ir_node *res;
 311
 312         in[0] = op;
 313         res   = new_ir_node(NULL, irg, bl, op_be_Copy, get_irn_mode(op), 1, in);
 314         init_node_attr(res, 1);
 315         be_node_set_reg_class(res, 0, cls);
 316         be_node_set_reg_class(res, OUT_POS(0), cls);
 317         return res;
 318 }
 319
 320 ir_node *be_new_Keep(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 321 {
 322         int i;
 323         ir_node *irn;
 324
 325         irn = new_ir_node(NULL, irg, bl, op_be_Keep, mode_ANY, n, in);
 326         init_node_attr(irn, n);
 327         for(i = 0; i < n; ++i) {
 328                 be_node_set_reg_class(irn, i, cls);
 329         }
 330         keep_alive(irn);
 331         return irn;
 332 }
 333
 334 ir_node *be_new_Call(ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *sp, ir_node *ptr, int n_outs, int n, ir_node *in[])
 335 {
 336         int real_n = 3 + n;
 337         ir_node *irn;
 338         ir_node **real_in;
 339
 340         real_in = malloc(sizeof(real_in[0]) * (real_n));
 341
 342         real_in[0] = mem;
 343         real_in[1] = sp;
 344         real_in[2] = ptr;
 345         memcpy(&real_in[3], in, n * sizeof(in[0]));
 346
 347         irn = new_ir_node(NULL, irg, bl, op_be_Call, mode_T, real_n, real_in);
 348         init_node_attr(irn, (n_outs > real_n ? n_outs : real_n));
 349         return irn;
 350 }
 351
 352 entity *be_Call_get_entity(const ir_node *call)
 353 {
 354         be_call_attr_t *a = get_irn_attr(call);
 355         assert(be_is_Call(call));
 356         return a->ent;
 357 }
 358
 359 void    be_Call_set_entity(ir_node *call, entity *ent)
 360 {
 361         be_call_attr_t *a = get_irn_attr(call);
 362         assert(be_is_Call(call));
 363         a->ent = ent;
 364 }
 365
 366 ir_node *be_new_Return(ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 367 {
 368         ir_node *irn = new_ir_node(NULL, irg, bl, op_be_Return, mode_X, n, in);
 369         init_node_attr(irn, n);
 370
 371         return irn;
 372 }
 373
 374 ir_node *be_new_IncSP(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *old_sp, ir_node *mem, unsigned offset, be_stack_dir_t dir)
 375 {
 376         be_stack_attr_t *a;
 377         ir_node *irn;
 378         ir_node *in[1];
 379
 380         in[0]     = old_sp;
 381         in[1]     = mem;
 382         irn       = new_ir_node(NULL, irg, bl, op_be_IncSP, sp->reg_class->mode, 2, in);
 383         a         = init_node_attr(irn, 1);
 384         a->dir    = dir;
 385         a->offset = offset;
 386
 387         be_node_set_flags(irn, -1, arch_irn_flags_ignore);
 388
 389         /* Set output constraint to stack register. */
 390         be_node_set_reg_class(irn, 0, sp->reg_class);
 391         be_set_constr_single_reg(irn, -1, sp);
 392         be_node_set_irn_reg(NULL, irn, sp);
 393
 394         return irn;
 395 }
 396
 397 ir_node *be_new_Alloca(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *old_sp, ir_node *sz)
 398 {
 399         be_node_attr_t *a;
 400         ir_node *irn;
 401         ir_node *in[3];
 402
 403         in[0]    = mem;
 404         in[1]    = old_sp;
 405         in[2]    = sz;
 406         irn      = new_ir_node(NULL, irg, bl, op_be_Alloca, mode_T, 3, in);
 407         a        = init_node_attr(irn, 3);
 408
 409         be_node_set_flags(irn, OUT_POS(pn_Alloc_res), arch_irn_flags_ignore);
 410
 411         /* Set output constraint to stack register. */
 412         be_set_constr_single_reg(irn, OUT_POS(pn_Alloc_res), sp);
 413
 414         return irn;
 415 }
 416
 417 ir_node *be_new_SetSP(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *old_sp, ir_node *op, ir_node *mem)
 418 {
 419         be_node_attr_t *a;
 420         ir_node *irn;
 421         ir_node *in[3];
 422
 423         in[0]    = mem;
 424         in[1]    = old_sp;
 425         in[2]    = op;
 426         irn      = new_ir_node(NULL, irg, bl, op_be_SetSP, get_irn_mode(old_sp), 3, in);
 427         a        = init_node_attr(irn, 3);
 428
 429         be_node_set_flags(irn, OUT_POS(0), arch_irn_flags_ignore);
 430
 431         /* Set output constraint to stack register. */
 432         be_set_constr_single_reg(irn, OUT_POS(0), sp);
 433         be_node_set_reg_class(irn, 1, sp->reg_class);
 434         be_node_set_reg_class(irn, 2, sp->reg_class);
 435         be_node_set_irn_reg(NULL, irn, sp);
 436
 437         return irn;
 438 }
 439
 440 ir_node *be_new_StackParam(const arch_register_class_t *cls, const arch_register_class_t *cls_frame, ir_graph *irg, ir_node *bl, ir_mode *mode, ir_node *frame_pointer, entity *ent)
 441 {
 442         be_frame_attr_t *a;
 443         ir_node *irn;
 444         ir_node *in[1];
 445
 446         in[0] = frame_pointer;
 447         irn = new_ir_node(NULL, irg, bl, op_be_StackParam, mode, 1, in);
 448         a = init_node_attr(irn, 1);
 449         a->ent = ent;
 450
 451         be_node_set_reg_class(irn, 0, cls_frame);
 452         be_node_set_reg_class(irn, OUT_POS(0), cls);
 453         return irn;
 454 }
 455
 456 ir_node *be_new_RegParams(ir_graph *irg, ir_node *bl, int n_outs)
 457 {
 458         ir_node *irn;
 459         ir_node *in[1];
 460
 461         irn = new_ir_node(NULL, irg, bl, op_be_RegParams, mode_T, 0, in);
 462         init_node_attr(irn, n_outs);
 463         return irn;
 464 }
 465
 466 ir_node *be_new_FrameLoad(const arch_register_class_t *cls_frame, const arch_register_class_t *cls_data,
 467                                                   ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *frame, entity *ent)
 468 {
 469         be_frame_attr_t *a;
 470         ir_node *irn;
 471         ir_node *in[2];
 472
 473         in[0]  = mem;
 474         in[1]  = frame;
 475         irn    = new_ir_node(NULL, irg, bl, op_be_FrameLoad, mode_T, 2, in);
 476         a      = init_node_attr(irn, 3);
 477         a->ent = ent;
 478         a->offset = 0;
 479         be_node_set_reg_class(irn, 1, cls_frame);
 480         be_node_set_reg_class(irn, OUT_POS(pn_Load_res), cls_data);
 481         return irn;
 482 }
 483
 484 ir_node *be_new_FrameStore(const arch_register_class_t *cls_frame, const arch_register_class_t *cls_data,
 485                                                    ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *frame, ir_node *data, entity *ent)
 486 {
 487         be_frame_attr_t *a;
 488         ir_node *irn;
 489         ir_node *in[3];
 490
 491         in[0]  = mem;
 492         in[1]  = frame;
 493         in[2]  = data;
 494         irn    = new_ir_node(NULL, irg, bl, op_be_FrameStore, mode_T, 3, in);
 495         a      = init_node_attr(irn, 3);
 496         a->ent = ent;
 497         a->offset = 0;
 498         be_node_set_reg_class(irn, 1, cls_frame);
 499         be_node_set_reg_class(irn, 2, cls_data);
 500         return irn;
 501 }
 502
 503 ir_node *be_new_FrameAddr(const arch_register_class_t *cls_frame, ir_graph *irg, ir_node *bl, ir_node *frame, entity *ent)
 504 {
 505         be_frame_attr_t *a;
 506         ir_node *irn;
 507         ir_node *in[1];
 508
 509         in[0]  = frame;
 510         irn    = new_ir_node(NULL, irg, bl, op_be_FrameAddr, get_irn_mode(frame), 1, in);
 511         a      = init_node_attr(irn, 1);
 512         a->ent = ent;
 513         a->offset = 0;
 514         be_node_set_reg_class(irn, 0, cls_frame);
 515         be_node_set_reg_class(irn, OUT_POS(0), cls_frame);
 516         return irn;
 517 }
 518
 519 int be_is_Spill         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Spill          ; }
 520 int be_is_Reload        (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Reload         ; }
 521 int be_is_Copy          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Copy           ; }
 522 int be_is_Perm          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Perm           ; }
 523 int be_is_Keep          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Keep           ; }
 524 int be_is_Call          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Call           ; }
 525 int be_is_Return        (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Return         ; }
 526 int be_is_IncSP         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_IncSP          ; }
 527 int be_is_SetSP         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_SetSP          ; }
 528 int be_is_Alloca        (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Alloca         ; }
 529 int be_is_RegParams     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_RegParams      ; }
 530 int be_is_StackParam    (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_StackParam     ; }
 531 int be_is_FrameAddr     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameAddr      ; }
 532 int be_is_FrameLoad     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameLoad      ; }
 533 int be_is_FrameStore    (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameStore     ; }
 534
 535 int be_has_frame_entity(const ir_node *irn)
 536 {
 537         switch(be_get_irn_opcode(irn)) {
 538         case beo_StackParam:
 539         case beo_Spill:
 540         case beo_Reload:
 541         case beo_FrameStore:
 542         case beo_FrameLoad:
 543         case beo_FrameAddr:
 544                 return 1;
 545         }
 546
 547         return 0;
 548 }
 549
 550 entity *be_get_frame_entity(const ir_node *irn)
 551 {
 552         if(be_has_frame_entity(irn)) {
 553                 be_frame_attr_t *a = get_irn_attr(irn);
 554                 return a->ent;
 555         }
 556         return NULL;
 557 }
 558
 559 static void be_limited(void *data, bitset_t *bs)
 560 {
 561         be_req_t *req = data;
 562
 563         switch(req->kind) {
 564         case be_req_kind_negate_old_limited:
 565         case be_req_kind_old_limited:
 566                 req->x.old_limited.old_limited(req->x.old_limited.old_limited_env, bs);
 567                 if(req->kind == be_req_kind_negate_old_limited)
 568                         bitset_flip_all(bs);
 569                 break;
 570         case be_req_kind_single_reg:
 571                 bitset_clear_all(bs);
 572                 bitset_set(bs, req->x.single_reg->index);
 573                 break;
 574         }
 575 }
 576
 577 static INLINE be_req_t *get_req(ir_node *irn, int pos)
 578 {
 579         int idx           = pos < 0 ? -(pos + 1) : pos;
 580         be_node_attr_t *a = get_irn_attr(irn);
 581         be_reg_data_t *rd = &a->reg_data[idx];
 582         be_req_t       *r = pos < 0 ? &rd->req : &rd->in_req;
 583
 584         assert(is_be_node(irn));
 585         assert(!(pos >= 0) || pos < get_irn_arity(irn));
 586         assert(!(pos < 0)  || -(pos + 1) <= a->max_reg_data);
 587
 588         return r;
 589 }
 590
 591 void be_set_constr_single_reg(ir_node *irn, int pos, const arch_register_t *reg)
 592 {
 593         be_req_t *r = get_req(irn, pos);
 594
 595         r->kind            = be_req_kind_single_reg;
 596         r->x.single_reg    = reg;
 597         r->req.limited     = be_limited;
 598         r->req.limited_env = r;
 599         r->req.type        = arch_register_req_type_limited;
 600         r->req.cls         = reg->reg_class;
 601 }
 602
 603 void be_set_constr_limited(ir_node *irn, int pos, const arch_register_req_t *req)
 604 {
 605         be_req_t *r = get_req(irn, pos);
 606
 607         assert(arch_register_req_is(req, limited));
 608
 609         r->kind            = be_req_kind_old_limited;
 610         r->req.limited     = be_limited;
 611         r->req.limited_env = r;
 612         r->req.type        = arch_register_req_type_limited;
 613         r->req.cls         = req->cls;
 614
 615         r->x.old_limited.old_limited     = req->limited;
 616         r->x.old_limited.old_limited_env = req->limited_env;
 617 }
 618
 619 void be_node_set_flags(ir_node *irn, int pos, arch_irn_flags_t flags)
 620 {
 621         be_req_t *r = get_req(irn, pos);
 622         r->flags = flags;
 623 }
 624
 625 void be_node_set_reg_class(ir_node *irn, int pos, const arch_register_class_t *cls)
 626 {
 627         be_req_t *r = get_req(irn, pos);
 628         r->req.cls = cls;
 629         if(r->req.type == arch_register_req_type_none)
 630                 r->req.type = arch_register_req_type_normal;
 631 }
 632
 633 void be_set_IncSP_offset(ir_node *irn, unsigned offset)
 634 {
 635         be_stack_attr_t *a = get_irn_attr(irn);
 636         assert(be_is_IncSP(irn));
 637         a->offset = offset;
 638 }
 639
 640 unsigned be_get_IncSP_offset(const ir_node *irn)
 641 {
 642         be_stack_attr_t *a = get_irn_attr(irn);
 643         assert(be_is_IncSP(irn));
 644         return a->offset;
 645 }
 646
 647 void be_set_IncSP_direction(ir_node *irn, be_stack_dir_t dir)
 648 {
 649         be_stack_attr_t *a = get_irn_attr(irn);
 650         assert(be_is_IncSP(irn));
 651         a->dir = dir;
 652 }
 653
 654 be_stack_dir_t be_get_IncSP_direction(const ir_node *irn)
 655 {
 656         be_stack_attr_t *a = get_irn_attr(irn);
 657         assert(be_is_IncSP(irn));
 658         return a->dir;
 659 }
 660
 661 void be_set_Spill_entity(ir_node *irn, entity *ent)
 662 {
 663         be_spill_attr_t *a = get_irn_attr(irn);
 664         assert(be_is_Spill(irn));
 665         a->frame_attr.ent = ent;
 666 }
 667
 668 static ir_node *find_a_spill_walker(ir_node *irn, unsigned visited_nr)
 669 {
 670         unsigned nr = get_irn_visited(irn);
 671
 672         set_irn_visited(irn, visited_nr);
 673
 674         if(is_Phi(irn)) {
 675                 int i, n;
 676                 if(nr < visited_nr) {
 677                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 678                                 ir_node *n = find_a_spill_walker(get_irn_n(irn, i), visited_nr);
 679                                 if(n != NULL)
 680                                         return n;
 681                         }
 682                 }
 683         }
 684
 685         else if(be_get_irn_opcode(irn) == beo_Spill)
 686                 return irn;
 687
 688         return NULL;
 689 }
 690
 691 ir_node *be_get_Spill_context(const ir_node *irn) {
 692         const be_spill_attr_t *a = get_irn_attr(irn);
 693         assert(be_is_Spill(irn));
 694         return a->spill_ctx;
 695 }
 696
 697 /**
 698  * Finds a spill for a reload.
 699  * If the reload is directly using the spill, this is simple,
 700  * else we perform DFS from the reload (over all PhiMs) and return
 701  * the first spill node we find.
 702  */
 703 static INLINE ir_node *find_a_spill(const ir_node *irn)
 704 {
 705         ir_graph *irg       = get_irn_irg(irn);
 706         unsigned visited_nr = get_irg_visited(irg) + 1;
 707
 708         assert(be_is_Reload(irn));
 709         set_irg_visited(irg, visited_nr);
 710         return find_a_spill_walker(be_get_Reload_mem(irn), visited_nr);
 711 }
 712
 713 entity *be_get_spill_entity(const ir_node *irn)
 714 {
 715         int opc           = get_irn_opcode(irn);
 716
 717         switch(be_get_irn_opcode(irn)) {
 718         case beo_Reload:
 719                 {
 720                         ir_node *spill = find_a_spill(irn);
 721                         return be_get_spill_entity(spill);
 722                 }
 723         case beo_Spill:
 724                 {
 725                         be_spill_attr_t *a = get_irn_attr(irn);
 726                         return a->frame_attr.ent;
 727                 }
 728         default:
 729                 assert(0 && "Must give spill/reload node");
 730                 break;
 731         }
 732
 733         return NULL;
 734 }
 735
 736 static void link_reload_walker(ir_node *irn, void *data)
 737 {
 738         ir_node **root = (ir_node **) data;
 739         if(be_is_Reload(irn)) {
 740                 set_irn_link(irn, *root);
 741                 *root = irn;
 742         }
 743 }
 744
 745 void be_copy_entities_to_reloads(ir_graph *irg)
 746 {
 747         ir_node *irn = NULL;
 748         irg_walk_graph(irg, link_reload_walker, NULL, (void *) &irn);
 749
 750         while(irn) {
 751                 be_frame_attr_t *a = get_irn_attr(irn);
 752                 entity *ent        = be_get_spill_entity(irn);
 753                 a->ent = ent;
 754                 irn    = get_irn_link(irn);
 755         }
 756 }
 757
 758 ir_node *be_spill(const arch_env_t *arch_env, ir_node *irn, ir_node *ctx)
 759 {
 760         ir_node *bl    = get_nodes_block(irn);
 761         ir_graph *irg  = get_irn_irg(bl);
 762         ir_node *frame = get_irg_frame(irg);
 763         ir_node *spill;
 764         ir_node *insert;
 765
 766         const arch_register_class_t *cls       = arch_get_irn_reg_class(arch_env, irn, -1);
 767         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
 768
 769         spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn, ctx);
 770
 771         /*
 772          * search the right insertion point. a spill of a phi cannot be put
 773          * directly after the phi, if there are some phis behind the one which
 774          * is spilled. Also, a spill of a Proj must be after all Projs of the
 775          * same tuple node.
 776          */
 777         insert = sched_next(irn);
 778         while((is_Phi(insert) || is_Proj(insert)) && !sched_is_end(insert))
 779                 insert = sched_next(insert);
 780
 781         /*
 782          * Here's one special case:
 783          * If the spill is in the start block, the spill must be after the frame
 784          * pointer is set up. This is checked here and fixed.
 785          * If the insertion point is already the block, everything is fine, since
 786          * the Spill gets inserted at the end of the block.
 787          */
 788         if(bl == get_irg_start_block(irg) && insert != bl && sched_comes_after(insert, frame))
 789                 insert = sched_next(frame);
 790
 791         sched_add_before(insert, spill);
 792         return spill;
 793 }
 794
 795 ir_node *be_reload(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_node *reloader, ir_mode *mode, ir_node *spill)
 796 {
 797         ir_node *reload;
 798
 799         ir_node *bl    = is_Block(reloader) ? reloader : get_nodes_block(reloader);
 800         ir_graph *irg  = get_irn_irg(bl);
 801         ir_node *frame = get_irg_frame(irg);
 802         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
 803
 804         assert(be_is_Spill(spill) || (is_Phi(spill) && get_irn_mode(spill) == mode_M));
 805
 806         reload = be_new_Reload(cls, cls_frame, irg, bl, frame, spill, mode);
 807
 808         sched_add_before(reloader, reload);
 809         return reload;
 810 }
 811
 812 static void *put_out_reg_req(arch_register_req_t *req, const ir_node *irn, int out_pos)
 813 {
 814         const be_node_attr_t *a = get_irn_attr(irn);
 815
 816         if(out_pos < a->max_reg_data)
 817                 memcpy(req, &a->reg_data[out_pos].req, sizeof(req[0]));
 818         else {
 819                 req->type = arch_register_req_type_none;
 820                 req->cls  = NULL;
 821         }
 822
 823         return req;
 824 }
 825
 826 static void *put_in_reg_req(arch_register_req_t *req, const ir_node *irn, int pos)
 827 {
 828         const be_node_attr_t *a = get_irn_attr(irn);
 829         int n                   = get_irn_arity(irn);
 830
 831         if(pos < get_irn_arity(irn) && pos < a->max_reg_data)
 832                 memcpy(req, &a->reg_data[pos].in_req, sizeof(req[0]));
 833         else {
 834                 req->type = arch_register_req_type_none;
 835                 req->cls  = NULL;
 836         }
 837
 838         return req;
 839 }
 840
 841 static const arch_register_req_t *
 842 be_node_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos)
 843 {
 844         int out_pos = pos;
 845
 846         if(pos < 0) {
 847                 if(get_irn_mode(irn) == mode_T)
 848                         return NULL;
 849
 850                 out_pos = redir_proj((const ir_node **) &irn, pos);
 851                 assert(is_be_node(irn));
 852                 return put_out_reg_req(req, irn, out_pos);
 853         }
 854
 855         else {
 856                 return is_be_node(irn) ? put_in_reg_req(req, irn, pos) : NULL;
 857         }
 858
 859         return req;
 860 }
 861
 862 const arch_register_t *
 863 be_node_get_irn_reg(const void *_self, const ir_node *irn)
 864 {
 865         int out_pos;
 866         be_node_attr_t *a;
 867
 868         out_pos = redir_proj((const ir_node **) &irn, -1);
 869         a       = get_irn_attr(irn);
 870
 871         assert(is_be_node(irn));
 872         assert(out_pos < a->max_reg_data && "position too high");
 873
 874         return a->reg_data[out_pos].reg;
 875 }
 876
 877 static arch_irn_class_t be_node_classify(const void *_self, const ir_node *irn)
 878 {
 879         redir_proj((const ir_node **) &irn, -1);
 880
 881         switch(be_get_irn_opcode(irn)) {
 882 #define XXX(a,b) case beo_ ## a: return arch_irn_class_ ## b;
 883                 XXX(Spill, spill)
 884                 XXX(Reload, reload)
 885                 XXX(Perm, perm)
 886                 XXX(Copy, copy)
 887 #undef XXX
 888                 default:
 889                 return 0;
 890         }
 891
 892         return 0;
 893 }
 894
 895 static arch_irn_flags_t be_node_get_flags(const void *_self, const ir_node *irn)
 896 {
 897         int out_pos;
 898         be_node_attr_t *a;
 899
 900         out_pos = redir_proj((const ir_node **) &irn, -1);
 901         a       = get_irn_attr(irn);
 902
 903         assert(is_be_node(irn));
 904         assert(out_pos < a->max_reg_data && "position too high");
 905
 906         return a->reg_data[out_pos].req.flags;
 907 }
 908
 909 static entity *be_node_get_frame_entity(const void *self, const ir_node *irn)
 910 {
 911         return be_get_frame_entity(irn);
 912 }
 913
 914 static void be_node_set_frame_offset(const void *self, ir_node *irn, int offset)
 915 {
 916         if(be_has_frame_entity(irn)) {
 917                 be_frame_attr_t *a = get_irn_attr(irn);
 918                 a->offset = offset;
 919         }
 920 }
 921
 922
 923 static const arch_irn_ops_if_t be_node_irn_ops_if = {
 924         be_node_get_irn_reg_req,
 925         be_node_set_irn_reg,
 926         be_node_get_irn_reg,
 927         be_node_classify,
 928         be_node_get_flags,
 929         be_node_get_frame_entity,
 930         be_node_set_frame_offset
 931 };
 932
 933 static const arch_irn_ops_t be_node_irn_ops = {
 934         &be_node_irn_ops_if
 935 };
 936
 937 const void *be_node_get_arch_ops(const arch_irn_handler_t *self, const ir_node *irn)
 938 {
 939         redir_proj((const ir_node **) &irn, -1);
 940         return is_be_node(irn) ? &be_node_irn_ops : NULL;
 941 }
 942
 943 const arch_irn_handler_t be_node_irn_handler = {
 944         be_node_get_arch_ops
 945 };
 946
 947
 948 static void dump_node_req(FILE *f, be_req_t *req)
 949 {
 950         unsigned i;
 951         int did_something = 0;
 952         const char *suffix = "";
 953
 954         if(req->flags != arch_irn_flags_none) {
 955                 fprintf(f, "flags: ");
 956                 for(i = arch_irn_flags_none; i <= log2_ceil(arch_irn_flags_last); ++i) {
 957                         if(req->flags & (1 << i)) {
 958                                 fprintf(f, "%s%s", suffix, arch_irn_flag_str(1 << i));
 959                                 suffix = "|";
 960                         }
 961                 }
 962                 suffix = ", ";
 963                 did_something = 1;
 964         }
 965
 966         if(req->req.cls != 0) {
 967                 char tmp[256];
 968                 fprintf(f, suffix);
 969                 arch_register_req_format(tmp, sizeof(tmp), &req->req);
 970                 fprintf(f, "%s", tmp);
 971                 did_something = 1;
 972         }
 973
 974         if(did_something)
 975                 fprintf(f, "\n");
 976 }
 977
 978 static void dump_node_reqs(FILE *f, ir_node *irn)
 979 {
 980         int i;
 981         be_node_attr_t *a = get_irn_attr(irn);
 982
 983         fprintf(f, "registers: \n");
 984         for(i = 0; i < a->max_reg_data; ++i) {
 985                 be_reg_data_t *rd = &a->reg_data[i];
 986                 if(rd->reg)
 987                         fprintf(f, "#%d: %s\n", i, rd->reg->name);
 988         }
 989
 990         fprintf(f, "in requirements\n");
 991         for(i = 0; i < a->max_reg_data; ++i) {
 992                 dump_node_req(f, &a->reg_data[i].in_req);
 993         }
 994
 995         fprintf(f, "\nout requirements\n");
 996         for(i = 0; i < a->max_reg_data; ++i) {
 997                 dump_node_req(f, &a->reg_data[i].req);
 998         }
 999 }
1000
1001 static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
1002 {
1003         be_node_attr_t *at = get_irn_attr(irn);
1004
1005         assert(is_be_node(irn));
1006
1007         switch(reason) {
1008                 case dump_node_opcode_txt:
1009                         fprintf(f, get_op_name(get_irn_op(irn)));
1010                         break;
1011                 case dump_node_mode_txt:
1012                         fprintf(f, get_mode_name(get_irn_mode(irn)));
1013                         break;
1014                 case dump_node_nodeattr_txt:
1015                         break;
1016                 case dump_node_info_txt:
1017                         dump_node_reqs(f, irn);
1018
1019                         if(be_has_frame_entity(irn)) {
1020                                 be_frame_attr_t *a = (be_frame_attr_t *) at;
1021                                 if (a->ent)
1022                                         ir_fprintf(f, "frame entity: %+F offset %x (%d)\n", a->ent, a->offset, a->offset);
1023
1024                         }
1025
1026                         switch(be_get_irn_opcode(irn)) {
1027                         case beo_Spill:
1028                                 {
1029                                         be_spill_attr_t *a = (be_spill_attr_t *) at;
1030                                         ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
1031                                 }
1032                                 break;
1033
1034                         case beo_IncSP:
1035                                 {
1036                                         be_stack_attr_t *a = (be_stack_attr_t *) at;
1037                                         fprintf(f, "offset: %u\n", a->offset);
1038                                         fprintf(f, "direction: %s\n", a->dir == be_stack_dir_along ? "along" : "against");
1039                                 }
1040                                 break;
1041                         }
1042
1043         }
1044
1045         return 0;
1046 }
1047
1048 /**
1049  * Copies the backend specific attributes from old node to new node.
1050  */
1051 static void copy_attr(const ir_node *old_node, ir_node *new_node)
1052 {
1053         be_node_attr_t *old_attr = get_irn_attr(old_node);
1054         be_node_attr_t *new_attr = get_irn_attr(new_node);
1055         int i;
1056
1057         assert(is_be_node(old_node));
1058         assert(is_be_node(new_node));
1059
1060         memcpy(new_attr, old_attr, get_op_attr_size(get_irn_op(old_node)));
1061         new_attr->reg_data = NULL;
1062
1063         if(new_attr->max_reg_data > 0) {
1064                 new_attr->reg_data = NEW_ARR_D(be_reg_data_t, get_irg_obstack(get_irn_irg(new_node)), new_attr->max_reg_data);
1065                 memcpy(new_attr->reg_data, old_attr->reg_data, new_attr->max_reg_data * sizeof(be_reg_data_t));
1066
1067                 for(i = 0; i < old_attr->max_reg_data; ++i) {
1068                         be_req_t *r;
1069
1070                         r = &new_attr->reg_data[i].req;
1071                         r->req.limited_env = r;
1072
1073                         r = &new_attr->reg_data[i].in_req;
1074                         r->req.limited_env = r;
1075                 }
1076         }
1077 }
1078
1079 static const ir_op_ops be_node_op_ops = {
1080         NULL,
1081         NULL,
1082         NULL,
1083         NULL,
1084         NULL,
1085         copy_attr,
1086         NULL,
1087         NULL,
1088         NULL,
1089         NULL,
1090         NULL,
1091         dump_node,
1092         NULL
1093 };
1094
1095 pset *nodes_live_at(const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live)
1096 {
1097         firm_dbg_module_t *dbg = firm_dbg_register("firm.be.node");
1098         const ir_node *bl      = is_Block(pos) ? pos : get_nodes_block(pos);
1099         ir_node *irn;
1100         irn_live_t *li;
1101
1102         live_foreach(bl, li) {
1103                 ir_node *irn = (ir_node *) li->irn;
1104                 if(live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
1105                         pset_insert_ptr(live, irn);
1106         }
1107
1108         sched_foreach_reverse(bl, irn) {
1109                 int i, n;
1110                 ir_node *x;
1111
1112                 /*
1113                  * If we encounter the node we want to insert the Perm after,
1114                 * exit immediately, so that this node is still live
1115                 */
1116                 if(irn == pos)
1117                         return live;
1118
1119                 DBG((dbg, LEVEL_1, "%+F\n", irn));
1120                 for(x = pset_first(live); x; x = pset_next(live))
1121                         DBG((dbg, LEVEL_1, "\tlive: %+F\n", x));
1122
1123                 if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
1124                         pset_remove_ptr(live, irn);
1125
1126                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
1127                         ir_node *op = get_irn_n(irn, i);
1128
1129                         if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
1130                                 pset_insert_ptr(live, op);
1131                 }
1132         }
1133
1134         return live;
1135 }
1136
1137 ir_node *insert_Perm_after(const arch_env_t *arch_env,
1138                                                    const arch_register_class_t *cls,
1139                                                    dom_front_info_t *dom_front,
1140                                                    ir_node *pos)
1141 {
1142         ir_node *bl                 = is_Block(pos) ? pos : get_nodes_block(pos);
1143         ir_graph *irg               = get_irn_irg(bl);
1144         pset *live                  = pset_new_ptr_default();
1145         firm_dbg_module_t *dbg      = firm_dbg_register("be.node");
1146
1147         ir_node *curr, *irn, *perm, **nodes;
1148         int i, n;
1149
1150         DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
1151
1152         if(!nodes_live_at(arch_env, cls, pos, live));
1153
1154         n = pset_count(live);
1155
1156         if(n == 0)
1157                 return NULL;
1158
1159         nodes = malloc(n * sizeof(nodes[0]));
1160
1161         DBG((dbg, LEVEL_1, "live:\n"));
1162         for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
1163                 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
1164                 nodes[i] = irn;
1165         }
1166
1167         perm = be_new_Perm(cls, irg, bl, n, nodes);
1168         sched_add_after(pos, perm);
1169         free(nodes);
1170
1171         curr = perm;
1172         for(i = 0; i < n; ++i) {
1173                 ir_node *copies[2];
1174                 ir_node *perm_op = get_irn_n(perm, i);
1175                 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
1176
1177                 ir_mode *mode = get_irn_mode(perm_op);
1178                 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
1179                 arch_set_irn_register(arch_env, proj, reg);
1180
1181                 sched_add_after(curr, proj);
1182                 curr = proj;
1183
1184                 copies[0] = perm_op;
1185                 copies[1] = proj;
1186                 be_ssa_constr(dom_front, 2, copies);
1187         }
1188         return perm;
1189 }