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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Helper functions for handling ABI constraints in the code
  23  *              selection phase.
  24  * @author      Matthias Braun
  25  * @version     $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "beabihelper.h"
  30 #include "bearch.h"
  31 #include "benode.h"
  32 #include "besched.h"
  33 #include "ircons.h"
  34 #include "iredges.h"
  35 #include "irgwalk.h"
  36 #include "irphase_t.h"
  37 #include "heights.h"
  38
  39 /**
  40  * An entry in the register state map.
  41  */
  42 typedef struct reg_flag_t {
  43         const arch_register_t *reg;     /**< register at an input position.
  44                                              may be NULL in case of memory input */
  45         arch_register_req_type_t flags; /**< requirement flags for this register. */
  46 } reg_flag_t;
  47
  48 /**
  49  * A register state mapping keeps track of the symbol values (=firm nodes)
  50  * to registers. This is useful when constructing straight line code
  51  * like the function prolog or epilog in some architectures.
  52  */
  53 typedef struct register_state_mapping_t {
  54         ir_node   **value_map;     /**< mapping of state indices to values */
  55         size_t    **reg_index_map; /**< mapping of regclass,regnum to an index
  56                                         into the value_map */
  57         reg_flag_t *regs;          /**< registers (and memory values) that form a
  58                                         state */
  59         ir_node    *last_barrier;
  60 } register_state_mapping_t;
  61
  62 /**
  63  * The environment for all helper functions.
  64  */
  65 struct beabi_helper_env_t {
  66         ir_graph                 *irg;         /**< the graph we operate on */
  67         register_state_mapping_t  prolog;      /**< the register state map for the prolog */
  68         register_state_mapping_t  epilog;      /**< the register state map for the epilog */
  69         ir_phase                 *stack_order; /**< a phase to handle stack dependencies. */
  70 };
  71
  72 /**
  73  * Create a new empty register state map for the given
  74  * architecture.
  75  *
  76  * @param rsm       the register state map to be initialized
  77  * @param arch_env  the architecture environment
  78  *
  79  * After this call, the register map is initialized to empty.
  80  */
  81 static void prepare_rsm(register_state_mapping_t *rsm,
  82                         const arch_env_t *arch_env)
  83 {
  84         unsigned   n_reg_classes = arch_env->n_register_classes;
  85         unsigned   c;
  86         reg_flag_t memory = { NULL, arch_register_req_type_none };
  87
  88         rsm->regs = NEW_ARR_F(reg_flag_t, 0);
  89         /* memory input at 0 */
  90         ARR_APP1(reg_flag_t, rsm->regs, memory);
  91
  92         rsm->value_map     = NULL;
  93         rsm->reg_index_map = XMALLOCN(size_t*, n_reg_classes);
  94         for (c = 0; c < n_reg_classes; ++c) {
  95                 const arch_register_class_t *cls    = &arch_env->register_classes[c];
  96                 unsigned                     n_regs = arch_register_class_n_regs(cls);
  97                 unsigned                     r;
  98
  99                 rsm->reg_index_map[c] = XMALLOCN(size_t, n_regs);
 100                 for (r = 0; r < n_regs; ++r) {
 101                         rsm->reg_index_map[c][r] = (size_t)-1;
 102                 }
 103         }
 104 }
 105
 106 /**
 107  * Destroy a register state map for the given
 108  * architecture.
 109  *
 110  * @param rsm       the register state map to be destroyed
 111  * @param arch_env  the architecture environment
 112  *
 113  * After this call, the register map is initialized to empty.
 114  */
 115 static void free_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env)
 116 {
 117         unsigned n_reg_classes = arch_env->n_register_classes;
 118         unsigned c;
 119
 120         for (c = 0; c < n_reg_classes; ++c) {
 121                 free(rsm->reg_index_map[c]);
 122         }
 123
 124         free(rsm->reg_index_map);
 125         if (rsm->value_map != NULL)
 126                 DEL_ARR_F(rsm->value_map);
 127         DEL_ARR_F(rsm->regs);
 128
 129         rsm->regs          = NULL;
 130         rsm->reg_index_map = NULL;
 131         rsm->value_map     = NULL;
 132 }
 133
 134 /**
 135  * Remove all registers from a register state map.
 136  *
 137  * @param rsm       the register state map to be destroyed
 138  * @param arch_env  the architecture environment
 139  */
 140 static void rsm_clear_regs(register_state_mapping_t *rsm,
 141                            const arch_env_t *arch_env)
 142 {
 143         unsigned   n_reg_classes = arch_env->n_register_classes;
 144         unsigned   c;
 145         reg_flag_t memory = { NULL, arch_register_req_type_none };
 146
 147         for (c = 0; c < n_reg_classes; ++c) {
 148                 const arch_register_class_t *cls    = &arch_env->register_classes[c];
 149                 unsigned                     n_regs = arch_register_class_n_regs(cls);
 150                 unsigned                     r;
 151
 152                 for (r = 0; r < n_regs; ++r) {
 153                         rsm->reg_index_map[c][r] = (size_t)-1;
 154                 }
 155         }
 156         ARR_RESIZE(reg_flag_t, rsm->regs, 0);
 157         ARR_APP1(reg_flag_t, rsm->regs, memory);
 158
 159         if (rsm->value_map != NULL) {
 160                 DEL_ARR_F(rsm->value_map);
 161                 rsm->value_map = NULL;
 162         }
 163 }
 164
 165 /**
 166  * Add a register and its constraint flags to a register state map
 167  * and return its index inside the map.
 168  */
 169 static int rsm_add_reg(register_state_mapping_t *rsm,
 170                        const arch_register_t *reg,
 171                        arch_register_req_type_t flags)
 172 {
 173         size_t     input_idx = ARR_LEN(rsm->regs);
 174         int        cls_idx   = reg->reg_class->index;
 175         int        reg_idx   = reg->index;
 176         reg_flag_t regflag   = { reg, flags };
 177
 178         /* we must not have used get_value yet */
 179         assert(rsm->reg_index_map[cls_idx][reg_idx] == (size_t)-1);
 180         rsm->reg_index_map[cls_idx][reg_idx] = input_idx;
 181         ARR_APP1(reg_flag_t, rsm->regs, regflag);
 182
 183         if (rsm->value_map != NULL) {
 184                 ARR_APP1(ir_node*, rsm->value_map, NULL);
 185                 assert(ARR_LEN(rsm->value_map) == ARR_LEN(rsm->regs));
 186         }
 187         return input_idx;
 188 }
 189
 190 /**
 191  * Retrieve the ir_node stored at the given index in the register state map.
 192  */
 193 static ir_node *rsm_get_value(register_state_mapping_t *rsm, size_t index)
 194 {
 195         assert(index < ARR_LEN(rsm->value_map));
 196         return rsm->value_map[index];
 197 }
 198
 199 /**
 200  * Retrieve the ir_node occupying the given register in the register state map.
 201  */
 202 static ir_node *rsm_get_reg_value(register_state_mapping_t *rsm,
 203                                   const arch_register_t *reg)
 204 {
 205         int    cls_idx   = reg->reg_class->index;
 206         int    reg_idx   = reg->index;
 207         size_t input_idx = rsm->reg_index_map[cls_idx][reg_idx];
 208
 209         return rsm_get_value(rsm, input_idx);
 210 }
 211
 212 /**
 213  * Enter a ir_node at the given index in the register state map.
 214  */
 215 static void rsm_set_value(register_state_mapping_t *rsm, size_t index,
 216                           ir_node *value)
 217 {
 218         assert(index < ARR_LEN(rsm->value_map));
 219         rsm->value_map[index] = value;
 220 }
 221
 222 /**
 223  * Enter a ir_node at the given register in the register state map.
 224  */
 225 static void rsm_set_reg_value(register_state_mapping_t *rsm,
 226                               const arch_register_t *reg, ir_node *value)
 227 {
 228         int    cls_idx   = reg->reg_class->index;
 229         int    reg_idx   = reg->index;
 230         size_t input_idx = rsm->reg_index_map[cls_idx][reg_idx];
 231         rsm_set_value(rsm, input_idx, value);
 232 }
 233
 234
 235 beabi_helper_env_t *be_abihelper_prepare(ir_graph *irg)
 236 {
 237         const arch_env_t   *arch_env = be_get_irg_arch_env(irg);
 238         beabi_helper_env_t *env      = XMALLOCZ(beabi_helper_env_t);
 239
 240         env->irg = irg;
 241         prepare_rsm(&env->prolog, arch_env);
 242         prepare_rsm(&env->epilog, arch_env);
 243
 244         return env;
 245 }
 246
 247 void be_abihelper_finish(beabi_helper_env_t *env)
 248 {
 249         const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
 250
 251         free_rsm(&env->prolog, arch_env);
 252         if (env->epilog.reg_index_map != NULL) {
 253                 free_rsm(&env->epilog, arch_env);
 254         }
 255         xfree(env);
 256 }
 257
 258 void be_prolog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
 259                        arch_register_req_type_t flags)
 260 {
 261         rsm_add_reg(&env->prolog, reg, flags);
 262 }
 263
 264 ir_node *be_prolog_create_start(beabi_helper_env_t *env, dbg_info *dbgi,
 265                                 ir_node *block)
 266 {
 267         int      n_start_outs = ARR_LEN(env->prolog.regs);
 268         ir_node *start        = be_new_Start(dbgi, block, n_start_outs);
 269         int      o;
 270
 271         arch_irn_add_flags(start, arch_irn_flags_prolog);
 272
 273         assert(env->prolog.value_map == NULL);
 274         env->prolog.value_map = NEW_ARR_F(ir_node*, n_start_outs);
 275
 276         for (o = 0; o < n_start_outs; ++o) {
 277                 const reg_flag_t      *regflag = &env->prolog.regs[o];
 278                 const arch_register_t *reg     = regflag->reg;
 279                 ir_node               *proj;
 280                 if (reg == NULL) {
 281                         arch_set_out_register_req(start, o, arch_no_register_req);
 282                         proj = new_r_Proj(start, mode_M, o);
 283                 } else {
 284                         be_set_constr_single_reg_out(start, o, regflag->reg,
 285                                                      regflag->flags);
 286                         arch_irn_set_register(start, o, regflag->reg);
 287                         proj = new_r_Proj(start, reg->reg_class->mode, o);
 288                 }
 289                 env->prolog.value_map[o] = proj;
 290         }
 291
 292         /* start node should really be the first thing constructed */
 293         env->prolog.last_barrier = start;
 294
 295         return start;
 296 }
 297
 298 ir_node *be_prolog_get_reg_value(beabi_helper_env_t *env,
 299                                  const arch_register_t *reg)
 300 {
 301         return rsm_get_reg_value(&env->prolog, reg);
 302 }
 303
 304 ir_node *be_prolog_get_memory(beabi_helper_env_t *env)
 305 {
 306         return rsm_get_value(&env->prolog, 0);
 307 }
 308
 309 void be_prolog_set_reg_value(beabi_helper_env_t *env,
 310                              const arch_register_t *reg, ir_node *value)
 311 {
 312         rsm_set_reg_value(&env->prolog, reg, value);
 313 }
 314
 315 void be_prolog_set_memory(beabi_helper_env_t *env, ir_node *value)
 316 {
 317         rsm_set_value(&env->prolog, 0, value);
 318 }
 319
 320
 321
 322 void be_epilog_begin(beabi_helper_env_t *env)
 323 {
 324         const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
 325         rsm_clear_regs(&env->epilog, arch_env);
 326         env->epilog.value_map    = NEW_ARR_F(ir_node*, 1);
 327         env->epilog.value_map[0] = NULL;
 328 }
 329
 330 void be_epilog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
 331                        arch_register_req_type_t flags, ir_node *value)
 332 {
 333         int index = rsm_add_reg(&env->epilog, reg, flags);
 334         rsm_set_value(&env->epilog, index, value);
 335 }
 336
 337 void be_epilog_set_reg_value(beabi_helper_env_t *env,
 338                              const arch_register_t *reg, ir_node *value)
 339 {
 340         rsm_set_reg_value(&env->epilog, reg, value);
 341 }
 342
 343 void be_epilog_set_memory(beabi_helper_env_t *env, ir_node *value)
 344 {
 345         rsm_set_value(&env->epilog, 0, value);
 346 }
 347
 348 ir_node *be_epilog_get_reg_value(beabi_helper_env_t *env,
 349                                  const arch_register_t *reg)
 350 {
 351         return rsm_get_reg_value(&env->epilog, reg);
 352 }
 353
 354 ir_node *be_epilog_get_memory(beabi_helper_env_t *env)
 355 {
 356         return rsm_get_value(&env->epilog, 0);
 357 }
 358
 359 ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi,
 360                                  ir_node *block)
 361 {
 362         size_t    n_return_in = ARR_LEN(env->epilog.regs);
 363         ir_node **in          = env->epilog.value_map;
 364         int       n_res       = 1; /* TODO */
 365         unsigned  pop         = 0; /* TODO */
 366         size_t    i;
 367         ir_node  *ret;
 368
 369         assert(ARR_LEN(env->epilog.value_map) == n_return_in);
 370
 371         ret = be_new_Return(dbgi, get_irn_irg(block), block, n_res, pop,
 372                             n_return_in, in);
 373         arch_irn_add_flags(ret, arch_irn_flags_epilog);
 374         for (i = 0; i < n_return_in; ++i) {
 375                 const reg_flag_t      *regflag = &env->epilog.regs[i];
 376                 const arch_register_t *reg     = regflag->reg;
 377                 if (reg != NULL) {
 378                         be_set_constr_single_reg_in(ret, i, reg,
 379                                                     arch_register_req_type_none);
 380                 }
 381         }
 382
 383         rsm_clear_regs(&env->epilog, be_get_irg_arch_env(env->irg));
 384         env->epilog.last_barrier = NULL;
 385
 386         return ret;
 387 }
 388
 389 static void add_missing_keep_walker(ir_node *node, void *data)
 390 {
 391         int              n_outs, i;
 392         unsigned        *found_projs;
 393         const ir_edge_t *edge;
 394         ir_mode         *mode = get_irn_mode(node);
 395         ir_node         *last_keep;
 396         (void) data;
 397         if (mode != mode_T)
 398                 return;
 399
 400         n_outs = arch_irn_get_n_outs(node);
 401         if (n_outs <= 0)
 402                 return;
 403
 404         rbitset_alloca(found_projs, n_outs);
 405         foreach_out_edge(node, edge) {
 406                 ir_node *succ = get_edge_src_irn(edge);
 407                 ir_mode *mode = get_irn_mode(succ);
 408                 int      pn;
 409
 410                 /* The node could be kept */
 411                 if (is_End(succ) || is_Anchor(succ))
 412                         continue;
 413
 414                 if (mode == mode_M || mode == mode_X)
 415                         continue;
 416
 417                 pn = get_Proj_proj(succ);
 418                 assert(pn < n_outs);
 419                 rbitset_set(found_projs, pn);
 420         }
 421
 422
 423         /* are keeps missing? */
 424         last_keep = NULL;
 425         for (i = 0; i < n_outs; ++i) {
 426                 ir_node                     *block;
 427                 ir_node                     *in[1];
 428                 const arch_register_req_t   *req;
 429                 const arch_register_class_t *cls;
 430
 431                 if (rbitset_is_set(found_projs, i)) {
 432                         continue;
 433                 }
 434
 435                 req = arch_get_out_register_req(node, i);
 436                 cls = req->cls;
 437                 if (cls == NULL || (cls->flags & arch_register_class_flag_manual_ra)) {
 438                         continue;
 439                 }
 440
 441                 block = get_nodes_block(node);
 442                 in[0] = new_r_Proj(node, arch_register_class_mode(cls), i);
 443                 if (last_keep != NULL) {
 444                         be_Keep_add_node(last_keep, cls, in[0]);
 445                 } else {
 446                         last_keep = be_new_Keep(block, 1, in);
 447                         if (sched_is_scheduled(node)) {
 448                                 sched_add_after(node, last_keep);
 449                         }
 450                 }
 451         }
 452 }
 453
 454 void be_add_missing_keeps(ir_graph *irg)
 455 {
 456         irg_walk_graph(irg, add_missing_keep_walker, NULL, NULL);
 457 }
 458
 459
 460 /**
 461  * Link the node into its block list as a new head.
 462  */
 463 static void collect_node(ir_node *node)
 464 {
 465         ir_node *block = get_nodes_block(node);
 466         ir_node *old   = (ir_node*)get_irn_link(block);
 467
 468         set_irn_link(node, old);
 469         set_irn_link(block, node);
 470 }
 471
 472 /**
 473  * Post-walker: link all nodes that probably access the stack into lists of their block.
 474  */
 475 static void link_ops_in_block_walker(ir_node *node, void *data)
 476 {
 477         (void) data;
 478
 479         switch (get_irn_opcode(node)) {
 480         case iro_Return:
 481         case iro_Call:
 482                 collect_node(node);
 483                 break;
 484         case iro_Alloc:
 485                 /** all non-stack alloc nodes should be lowered before the backend */
 486                 assert(get_Alloc_where(node) == stack_alloc);
 487                 collect_node(node);
 488                 break;
 489         case iro_Free:
 490                 assert(get_Free_where(node) == stack_alloc);
 491                 collect_node(node);
 492                 break;
 493         case iro_Builtin:
 494                 if (get_Builtin_kind(node) == ir_bk_return_address) {
 495                         ir_node   *param = get_Builtin_param(node, 0);
 496                         ir_tarval *tv    = get_Const_tarval(param); /* must be Const */
 497                         long       value = get_tarval_long(tv);
 498                         if (value > 0) {
 499                                 /* not the return address of the current function:
 500                                  * we need the stack pointer for the frame climbing */
 501                                 collect_node(node);
 502                         }
 503                 }
 504                 break;
 505         default:
 506                 break;
 507         }
 508 }
 509
 510 static ir_heights_t *heights;
 511
 512 /**
 513  * Check if a node is somehow data dependent on another one.
 514  * both nodes must be in the same basic block.
 515  * @param n1 The first node.
 516  * @param n2 The second node.
 517  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 518  */
 519 static int dependent_on(const ir_node *n1, const ir_node *n2)
 520 {
 521         assert(get_nodes_block(n1) == get_nodes_block(n2));
 522
 523         return heights_reachable_in_block(heights, n1, n2);
 524 }
 525
 526 /**
 527  * Classical qsort() comparison function behavior:
 528  *
 529  * 0  if both elements are equal, no node depend on the other
 530  * +1 if first depends on second (first is greater)
 531  * -1 if second depends on first (second is greater)
 532 */
 533 static int cmp_call_dependency(const void *c1, const void *c2)
 534 {
 535         const ir_node *n1 = *(const ir_node **) c1;
 536         const ir_node *n2 = *(const ir_node **) c2;
 537
 538         if (dependent_on(n1, n2))
 539                 return 1;
 540
 541         if (dependent_on(n2, n1))
 542                 return -1;
 543
 544         /* The nodes have no depth order, but we need a total order because qsort()
 545          * is not stable. */
 546         return get_irn_idx(n2) - get_irn_idx(n1);
 547 }
 548
 549 /**
 550  * Block-walker: sorts dependencies and remember them into a phase
 551  */
 552 static void process_ops_in_block(ir_node *block, void *data)
 553 {
 554         ir_phase *phase = (ir_phase*)data;
 555         unsigned  n;
 556         unsigned  n_nodes;
 557         ir_node  *node;
 558         ir_node **nodes;
 559
 560         n_nodes = 0;
 561         for (node = (ir_node*)get_irn_link(block); node != NULL;
 562              node = (ir_node*)get_irn_link(node)) {
 563                 ++n_nodes;
 564         }
 565
 566         if (n_nodes == 0)
 567                 return;
 568
 569         nodes = XMALLOCN(ir_node*, n_nodes);
 570         n = 0;
 571         for (node = (ir_node*)get_irn_link(block); node != NULL;
 572              node = (ir_node*)get_irn_link(node)) {
 573                 nodes[n++] = node;
 574         }
 575         assert(n == n_nodes);
 576
 577         /* order nodes according to their data dependencies */
 578         qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
 579
 580         /* remember the calculated dependency into a phase */
 581         for (n = n_nodes-1; n > 0; --n) {
 582                 ir_node *node = nodes[n];
 583                 ir_node *pred = nodes[n-1];
 584
 585                 phase_set_irn_data(phase, node, pred);
 586         }
 587         xfree(nodes);
 588 }
 589
 590 void be_collect_stacknodes(beabi_helper_env_t *env)
 591 {
 592         ir_graph *irg = env->irg;
 593
 594         /* collect all potential^stack accessing nodes */
 595         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, NULL);
 596
 597         assert(env->stack_order == NULL);
 598         env->stack_order = new_phase(irg, phase_irn_init_default);
 599
 600         /* use heights to create a total order for those nodes: this order is stored
 601          * in the created phase */
 602         heights = heights_new(irg);
 603         irg_block_walk_graph(irg, NULL, process_ops_in_block, env->stack_order);
 604         heights_free(heights);
 605 }
 606
 607 ir_node *be_get_stack_pred(const beabi_helper_env_t *env, const ir_node *node)
 608 {
 609         return (ir_node*)phase_get_irn_data(env->stack_order, node);
 610 }