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 } register_state_mapping_t;
  60
  61 /**
  62  * The environment for all helper functions.
  63  */
  64 struct beabi_helper_env_t {
  65         ir_graph                 *irg;         /**< the graph we operate on */
  66         register_state_mapping_t  prolog;      /**< the register state map for the prolog */
  67         register_state_mapping_t  epilog;      /**< the register state map for the epilog */
  68         ir_phase                 *stack_order; /**< a phase to handle stack dependencies. */
  69 };
  70
  71 /**
  72  * Create a new empty register state map for the given
  73  * architecture.
  74  *
  75  * @param rsm       the register state map to be initialized
  76  * @param arch_env  the architecture environment
  77  *
  78  * After this call, the register map is initialized to empty.
  79  */
  80 static void prepare_rsm(register_state_mapping_t *rsm,
  81                         const arch_env_t *arch_env)
  82 {
  83         unsigned   n_reg_classes = arch_env->n_register_classes;
  84         unsigned   c;
  85         reg_flag_t memory = { NULL, arch_register_req_type_none };
  86
  87         rsm->regs = NEW_ARR_F(reg_flag_t, 0);
  88         /* memory input at 0 */
  89         ARR_APP1(reg_flag_t, rsm->regs, memory);
  90
  91         rsm->value_map     = NULL;
  92         rsm->reg_index_map = XMALLOCN(size_t*, n_reg_classes);
  93         for (c = 0; c < n_reg_classes; ++c) {
  94                 const arch_register_class_t *cls    = &arch_env->register_classes[c];
  95                 unsigned                     n_regs = arch_register_class_n_regs(cls);
  96                 unsigned                     r;
  97
  98                 rsm->reg_index_map[c] = XMALLOCN(size_t, n_regs);
  99                 for (r = 0; r < n_regs; ++r) {
 100                         rsm->reg_index_map[c][r] = (size_t)-1;
 101                 }
 102         }
 103 }
 104
 105 /**
 106  * Destroy a register state map for the given
 107  * architecture.
 108  *
 109  * @param rsm       the register state map to be destroyed
 110  * @param arch_env  the architecture environment
 111  *
 112  * After this call, the register map is initialized to empty.
 113  */
 114 static void free_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env)
 115 {
 116         unsigned n_reg_classes = arch_env->n_register_classes;
 117         unsigned c;
 118
 119         for (c = 0; c < n_reg_classes; ++c) {
 120                 free(rsm->reg_index_map[c]);
 121         }
 122
 123         free(rsm->reg_index_map);
 124         if (rsm->value_map != NULL)
 125                 DEL_ARR_F(rsm->value_map);
 126         DEL_ARR_F(rsm->regs);
 127
 128         rsm->regs          = NULL;
 129         rsm->reg_index_map = NULL;
 130         rsm->value_map     = NULL;
 131 }
 132
 133 /**
 134  * Remove all registers from a register state map.
 135  *
 136  * @param rsm       the register state map to be destroyed
 137  * @param arch_env  the architecture environment
 138  */
 139 static void rsm_clear_regs(register_state_mapping_t *rsm,
 140                            const arch_env_t *arch_env)
 141 {
 142         unsigned   n_reg_classes = arch_env->n_register_classes;
 143         unsigned   c;
 144         reg_flag_t memory = { NULL, arch_register_req_type_none };
 145
 146         for (c = 0; c < n_reg_classes; ++c) {
 147                 const arch_register_class_t *cls    = &arch_env->register_classes[c];
 148                 unsigned                     n_regs = arch_register_class_n_regs(cls);
 149                 unsigned                     r;
 150
 151                 for (r = 0; r < n_regs; ++r) {
 152                         rsm->reg_index_map[c][r] = (size_t)-1;
 153                 }
 154         }
 155         ARR_RESIZE(reg_flag_t, rsm->regs, 0);
 156         ARR_APP1(reg_flag_t, rsm->regs, memory);
 157
 158         if (rsm->value_map != NULL) {
 159                 DEL_ARR_F(rsm->value_map);
 160                 rsm->value_map = NULL;
 161         }
 162 }
 163
 164 /**
 165  * Add a register and its constraint flags to a register state map
 166  * and return its index inside the map.
 167  */
 168 static size_t rsm_add_reg(register_state_mapping_t *rsm,
 169                           const arch_register_t *reg,
 170                            arch_register_req_type_t flags)
 171 {
 172         size_t     input_idx = ARR_LEN(rsm->regs);
 173         int        cls_idx   = reg->reg_class->index;
 174         int        reg_idx   = reg->index;
 175         reg_flag_t regflag   = { reg, flags };
 176
 177         /* we must not have used get_value yet */
 178         assert(rsm->reg_index_map[cls_idx][reg_idx] == (size_t)-1);
 179         rsm->reg_index_map[cls_idx][reg_idx] = input_idx;
 180         ARR_APP1(reg_flag_t, rsm->regs, regflag);
 181
 182         if (rsm->value_map != NULL) {
 183                 ARR_APP1(ir_node*, rsm->value_map, NULL);
 184                 assert(ARR_LEN(rsm->value_map) == ARR_LEN(rsm->regs));
 185         }
 186         return input_idx;
 187 }
 188
 189 /**
 190  * Retrieve the ir_node stored at the given index in the register state map.
 191  */
 192 static ir_node *rsm_get_value(register_state_mapping_t *rsm, size_t index)
 193 {
 194         assert(index < ARR_LEN(rsm->value_map));
 195         return rsm->value_map[index];
 196 }
 197
 198 /**
 199  * Retrieve the ir_node occupying the given register in the register state map.
 200  */
 201 static ir_node *rsm_get_reg_value(register_state_mapping_t *rsm,
 202                                   const arch_register_t *reg)
 203 {
 204         int    cls_idx   = reg->reg_class->index;
 205         int    reg_idx   = reg->index;
 206         size_t input_idx = rsm->reg_index_map[cls_idx][reg_idx];
 207
 208         return rsm_get_value(rsm, input_idx);
 209 }
 210
 211 /**
 212  * Enter a ir_node at the given index in the register state map.
 213  */
 214 static void rsm_set_value(register_state_mapping_t *rsm, size_t index,
 215                           ir_node *value)
 216 {
 217         assert(index < ARR_LEN(rsm->value_map));
 218         rsm->value_map[index] = value;
 219 }
 220
 221 /**
 222  * Enter a ir_node at the given register in the register state map.
 223  */
 224 static void rsm_set_reg_value(register_state_mapping_t *rsm,
 225                               const arch_register_t *reg, ir_node *value)
 226 {
 227         int    cls_idx   = reg->reg_class->index;
 228         int    reg_idx   = reg->index;
 229         size_t input_idx = rsm->reg_index_map[cls_idx][reg_idx];
 230         rsm_set_value(rsm, input_idx, value);
 231 }
 232
 233
 234 beabi_helper_env_t *be_abihelper_prepare(ir_graph *irg)
 235 {
 236         const arch_env_t   *arch_env = be_get_irg_arch_env(irg);
 237         beabi_helper_env_t *env      = XMALLOCZ(beabi_helper_env_t);
 238
 239         env->irg = irg;
 240         prepare_rsm(&env->prolog, arch_env);
 241         prepare_rsm(&env->epilog, arch_env);
 242
 243         return env;
 244 }
 245
 246 void be_abihelper_finish(beabi_helper_env_t *env)
 247 {
 248         const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
 249
 250         free_rsm(&env->prolog, arch_env);
 251         if (env->epilog.reg_index_map != NULL) {
 252                 free_rsm(&env->epilog, arch_env);
 253         }
 254         xfree(env);
 255 }
 256
 257 void be_prolog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
 258                        arch_register_req_type_t flags)
 259 {
 260         rsm_add_reg(&env->prolog, reg, flags);
 261 }
 262
 263 ir_node *be_prolog_create_start(beabi_helper_env_t *env, dbg_info *dbgi,
 264                                 ir_node *block)
 265 {
 266         int      n_start_outs = ARR_LEN(env->prolog.regs);
 267         ir_node *start        = be_new_Start(dbgi, block, n_start_outs);
 268         int      o;
 269
 270         assert(env->prolog.value_map == NULL);
 271         env->prolog.value_map = NEW_ARR_F(ir_node*, n_start_outs);
 272
 273         for (o = 0; o < n_start_outs; ++o) {
 274                 const reg_flag_t      *regflag = &env->prolog.regs[o];
 275                 const arch_register_t *reg     = regflag->reg;
 276                 ir_node               *proj;
 277                 if (reg == NULL) {
 278                         arch_set_out_register_req(start, o, arch_no_register_req);
 279                         proj = new_r_Proj(start, mode_M, o);
 280                 } else {
 281                         be_set_constr_single_reg_out(start, o, regflag->reg,
 282                                                      regflag->flags);
 283                         arch_irn_set_register(start, o, regflag->reg);
 284                         proj = new_r_Proj(start, reg->reg_class->mode, o);
 285                 }
 286                 env->prolog.value_map[o] = proj;
 287         }
 288
 289         return start;
 290 }
 291
 292 ir_node *be_prolog_get_reg_value(beabi_helper_env_t *env,
 293                                  const arch_register_t *reg)
 294 {
 295         return rsm_get_reg_value(&env->prolog, reg);
 296 }
 297
 298 ir_node *be_prolog_get_memory(beabi_helper_env_t *env)
 299 {
 300         return rsm_get_value(&env->prolog, 0);
 301 }
 302
 303 void be_prolog_set_reg_value(beabi_helper_env_t *env,
 304                              const arch_register_t *reg, ir_node *value)
 305 {
 306         rsm_set_reg_value(&env->prolog, reg, value);
 307 }
 308
 309 void be_prolog_set_memory(beabi_helper_env_t *env, ir_node *value)
 310 {
 311         rsm_set_value(&env->prolog, 0, value);
 312 }
 313
 314
 315
 316 void be_epilog_begin(beabi_helper_env_t *env)
 317 {
 318         const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
 319         rsm_clear_regs(&env->epilog, arch_env);
 320         env->epilog.value_map    = NEW_ARR_F(ir_node*, 1);
 321         env->epilog.value_map[0] = NULL;
 322 }
 323
 324 void be_epilog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
 325                        arch_register_req_type_t flags, ir_node *value)
 326 {
 327         size_t index = rsm_add_reg(&env->epilog, reg, flags);
 328         rsm_set_value(&env->epilog, index, value);
 329 }
 330
 331 void be_epilog_set_reg_value(beabi_helper_env_t *env,
 332                              const arch_register_t *reg, ir_node *value)
 333 {
 334         rsm_set_reg_value(&env->epilog, reg, value);
 335 }
 336
 337 void be_epilog_set_memory(beabi_helper_env_t *env, ir_node *value)
 338 {
 339         rsm_set_value(&env->epilog, 0, value);
 340 }
 341
 342 ir_node *be_epilog_get_reg_value(beabi_helper_env_t *env,
 343                                  const arch_register_t *reg)
 344 {
 345         return rsm_get_reg_value(&env->epilog, reg);
 346 }
 347
 348 ir_node *be_epilog_get_memory(beabi_helper_env_t *env)
 349 {
 350         return rsm_get_value(&env->epilog, 0);
 351 }
 352
 353 ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi,
 354                                  ir_node *block)
 355 {
 356         size_t    n_return_in = ARR_LEN(env->epilog.regs);
 357         ir_node **in          = env->epilog.value_map;
 358         int       n_res       = 1; /* TODO */
 359         unsigned  pop         = 0; /* TODO */
 360         size_t    i;
 361         ir_node  *ret;
 362
 363         assert(ARR_LEN(env->epilog.value_map) == n_return_in);
 364
 365         ret = be_new_Return(dbgi, get_irn_irg(block), block, n_res, pop,
 366                             n_return_in, in);
 367         for (i = 0; i < n_return_in; ++i) {
 368                 const reg_flag_t      *regflag = &env->epilog.regs[i];
 369                 const arch_register_t *reg     = regflag->reg;
 370                 if (reg != NULL) {
 371                         be_set_constr_single_reg_in(ret, i, reg,
 372                                                     arch_register_req_type_none);
 373                 }
 374         }
 375
 376         rsm_clear_regs(&env->epilog, be_get_irg_arch_env(env->irg));
 377
 378         return ret;
 379 }
 380
 381 /**
 382  * Tests whether a node has a real user and is not just kept by the End or
 383  * Anchor node
 384  */
 385 static bool has_real_user(const ir_node *node)
 386 {
 387         const ir_edge_t *edge;
 388         foreach_out_edge(node, edge) {
 389                 ir_node *user = get_edge_src_irn(edge);
 390                 if (!is_End(user) && !is_Anchor(user))
 391                         return true;
 392         }
 393         return false;
 394 }
 395
 396 static ir_node *add_to_keep(ir_node *last_keep,
 397                             const arch_register_class_t *cls, ir_node *node)
 398 {
 399         const ir_node *op;
 400         if (last_keep != NULL) {
 401                 be_Keep_add_node(last_keep, cls, node);
 402         } else {
 403                 ir_node *in[1] = { node };
 404                 ir_node *block = get_nodes_block(node);
 405                 ir_node *schedpoint;
 406                 last_keep = be_new_Keep(block, 1, in);
 407
 408                 schedpoint = skip_Proj(node);
 409                 if (sched_is_scheduled(schedpoint)) {
 410                         sched_add_after(schedpoint, last_keep);
 411                 }
 412         }
 413         op = skip_Proj_const(node);
 414         return last_keep;
 415 }
 416
 417 static void add_missing_keep_walker(ir_node *node, void *data)
 418 {
 419         int              n_outs, i;
 420         unsigned        *found_projs;
 421         const ir_edge_t *edge;
 422         ir_mode         *mode = get_irn_mode(node);
 423         ir_node         *last_keep;
 424         ir_node        **existing_projs;
 425         (void) data;
 426         if (mode != mode_T) {
 427                 if (!has_real_user(node)) {
 428                         const arch_register_req_t   *req = arch_get_register_req_out(node);
 429                         const arch_register_class_t *cls = req->cls;
 430                         if (cls == NULL
 431                                         || (cls->flags & arch_register_class_flag_manual_ra)) {
 432                                 return;
 433                         }
 434
 435                         add_to_keep(NULL, cls, node);
 436                 }
 437                 return;
 438         }
 439
 440         n_outs = arch_irn_get_n_outs(node);
 441         if (n_outs <= 0)
 442                 return;
 443
 444         rbitset_alloca(found_projs, n_outs);
 445         existing_projs = ALLOCANZ(ir_node*, n_outs);
 446         foreach_out_edge(node, edge) {
 447                 ir_node *succ = get_edge_src_irn(edge);
 448                 ir_mode *mode = get_irn_mode(succ);
 449                 int      pn;
 450
 451                 /* The node could be kept */
 452                 if (is_End(succ) || is_Anchor(succ))
 453                         continue;
 454                 if (mode == mode_M || mode == mode_X)
 455                         continue;
 456                 pn                 = get_Proj_proj(succ);
 457                 existing_projs[pn] = succ;
 458                 if (!has_real_user(succ))
 459                         continue;
 460
 461                 assert(pn < n_outs);
 462                 rbitset_set(found_projs, pn);
 463         }
 464
 465         /* are keeps missing? */
 466         last_keep = NULL;
 467         for (i = 0; i < n_outs; ++i) {
 468                 ir_node                     *value;
 469                 const arch_register_req_t   *req;
 470                 const arch_register_class_t *cls;
 471
 472                 if (rbitset_is_set(found_projs, i)) {
 473                         continue;
 474                 }
 475
 476                 req = arch_get_out_register_req(node, i);
 477                 cls = req->cls;
 478                 if (cls == NULL || (cls->flags & arch_register_class_flag_manual_ra)) {
 479                         continue;
 480                 }
 481
 482                 value = existing_projs[i];
 483                 if (value == NULL)
 484                         value = new_r_Proj(node, arch_register_class_mode(cls), i);
 485                 last_keep = add_to_keep(last_keep, cls, value);
 486         }
 487 }
 488
 489 void be_add_missing_keeps(ir_graph *irg)
 490 {
 491         irg_walk_graph(irg, add_missing_keep_walker, NULL, NULL);
 492 }
 493
 494
 495 /**
 496  * Link the node into its block list as a new head.
 497  */
 498 static void collect_node(ir_node *node)
 499 {
 500         ir_node *block = get_nodes_block(node);
 501         ir_node *old   = (ir_node*)get_irn_link(block);
 502
 503         set_irn_link(node, old);
 504         set_irn_link(block, node);
 505 }
 506
 507 /**
 508  * Post-walker: link all nodes that probably access the stack into lists of their block.
 509  */
 510 static void link_ops_in_block_walker(ir_node *node, void *data)
 511 {
 512         (void) data;
 513
 514         switch (get_irn_opcode(node)) {
 515         case iro_Return:
 516         case iro_Call:
 517                 collect_node(node);
 518                 break;
 519         case iro_Alloc:
 520                 /** all non-stack alloc nodes should be lowered before the backend */
 521                 assert(get_Alloc_where(node) == stack_alloc);
 522                 collect_node(node);
 523                 break;
 524         case iro_Free:
 525                 assert(get_Free_where(node) == stack_alloc);
 526                 collect_node(node);
 527                 break;
 528         case iro_Builtin:
 529                 if (get_Builtin_kind(node) == ir_bk_return_address) {
 530                         ir_node   *param = get_Builtin_param(node, 0);
 531                         ir_tarval *tv    = get_Const_tarval(param); /* must be Const */
 532                         long       value = get_tarval_long(tv);
 533                         if (value > 0) {
 534                                 /* not the return address of the current function:
 535                                  * we need the stack pointer for the frame climbing */
 536                                 collect_node(node);
 537                         }
 538                 }
 539                 break;
 540         default:
 541                 break;
 542         }
 543 }
 544
 545 static ir_heights_t *heights;
 546
 547 /**
 548  * Check if a node is somehow data dependent on another one.
 549  * both nodes must be in the same basic block.
 550  * @param n1 The first node.
 551  * @param n2 The second node.
 552  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 553  */
 554 static int dependent_on(const ir_node *n1, const ir_node *n2)
 555 {
 556         assert(get_nodes_block(n1) == get_nodes_block(n2));
 557
 558         return heights_reachable_in_block(heights, n1, n2);
 559 }
 560
 561 /**
 562  * Classical qsort() comparison function behavior:
 563  *
 564  * 0  if both elements are equal, no node depend on the other
 565  * +1 if first depends on second (first is greater)
 566  * -1 if second depends on first (second is greater)
 567 */
 568 static int cmp_call_dependency(const void *c1, const void *c2)
 569 {
 570         const ir_node *n1 = *(const ir_node **) c1;
 571         const ir_node *n2 = *(const ir_node **) c2;
 572
 573         if (dependent_on(n1, n2))
 574                 return 1;
 575
 576         if (dependent_on(n2, n1))
 577                 return -1;
 578
 579         /* The nodes have no depth order, but we need a total order because qsort()
 580          * is not stable. */
 581         return get_irn_idx(n2) - get_irn_idx(n1);
 582 }
 583
 584 /**
 585  * Block-walker: sorts dependencies and remember them into a phase
 586  */
 587 static void process_ops_in_block(ir_node *block, void *data)
 588 {
 589         ir_phase *phase = (ir_phase*)data;
 590         unsigned  n;
 591         unsigned  n_nodes;
 592         ir_node  *node;
 593         ir_node **nodes;
 594
 595         n_nodes = 0;
 596         for (node = (ir_node*)get_irn_link(block); node != NULL;
 597              node = (ir_node*)get_irn_link(node)) {
 598                 ++n_nodes;
 599         }
 600
 601         if (n_nodes == 0)
 602                 return;
 603
 604         nodes = XMALLOCN(ir_node*, n_nodes);
 605         n = 0;
 606         for (node = (ir_node*)get_irn_link(block); node != NULL;
 607              node = (ir_node*)get_irn_link(node)) {
 608                 nodes[n++] = node;
 609         }
 610         assert(n == n_nodes);
 611
 612         /* order nodes according to their data dependencies */
 613         qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
 614
 615         /* remember the calculated dependency into a phase */
 616         for (n = n_nodes-1; n > 0; --n) {
 617                 ir_node *node = nodes[n];
 618                 ir_node *pred = nodes[n-1];
 619
 620                 phase_set_irn_data(phase, node, pred);
 621         }
 622         xfree(nodes);
 623 }
 624
 625 void be_collect_stacknodes(beabi_helper_env_t *env)
 626 {
 627         ir_graph *irg = env->irg;
 628
 629         /* collect all potential^stack accessing nodes */
 630         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, NULL);
 631
 632         assert(env->stack_order == NULL);
 633         env->stack_order = new_phase(irg, phase_irn_init_default);
 634
 635         /* use heights to create a total order for those nodes: this order is stored
 636          * in the created phase */
 637         heights = heights_new(irg);
 638         irg_block_walk_graph(irg, NULL, process_ops_in_block, env->stack_order);
 639         heights_free(heights);
 640 }
 641
 642 ir_node *be_get_stack_pred(const beabi_helper_env_t *env, const ir_node *node)
 643 {
 644         return (ir_node*)phase_get_irn_data(env->stack_order, node);
 645 }