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         int       **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(int*, 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(int, n_regs);
 100                 for (r = 0; r < n_regs; ++r) {
 101                         rsm->reg_index_map[c][r] = -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] = -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         int        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] == -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, int index)
 194 {
 195         assert(0 <= index && 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         int 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, int index,
 216                           ir_node *value)
 217 {
 218         assert(0 <= index && 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         int input_idx = rsm->reg_index_map[cls_idx][reg_idx];
 231         rsm_set_value(rsm, input_idx, value);
 232 }
 233
 234 /**
 235  * Create a Barrier from the registers stored at a register state map.
 236  *
 237  * @param rsm    the register state map
 238  * @param block  the block to create the Barrier on
 239  */
 240 static ir_node *rsm_create_barrier(register_state_mapping_t *rsm,
 241                                    ir_node *block)
 242 {
 243         size_t    n_barrier_outs = ARR_LEN(rsm->regs);
 244         ir_node **in             = rsm->value_map;
 245         ir_node  *barrier;
 246         size_t    o;
 247
 248         assert(ARR_LEN(rsm->value_map) == n_barrier_outs);
 249
 250         barrier = be_new_Barrier(block, n_barrier_outs, in);
 251
 252         for (o = 0; o < n_barrier_outs; ++o) {
 253                 const reg_flag_t      *regflag = &rsm->regs[o];
 254                 const arch_register_t *reg     = regflag->reg;
 255                 ir_node               *proj;
 256                 if (reg == NULL) {
 257                         arch_set_out_register_req(barrier, o, arch_no_register_req);
 258                         proj = new_r_Proj(barrier, mode_M, o);
 259                 } else {
 260                         be_set_constr_single_reg_in(barrier, o, reg, arch_register_req_type_none);
 261                         be_set_constr_single_reg_out(barrier, o, reg, regflag->flags);
 262                         proj = new_r_Proj(barrier, reg->reg_class->mode, o);
 263                 }
 264                 rsm->value_map[o] = proj;
 265         }
 266
 267         rsm->last_barrier = barrier;
 268
 269         return barrier;
 270 }
 271
 272
 273
 274
 275
 276 beabi_helper_env_t *be_abihelper_prepare(ir_graph *irg)
 277 {
 278         const arch_env_t   *arch_env = be_get_irg_arch_env(irg);
 279         beabi_helper_env_t *env      = XMALLOCZ(beabi_helper_env_t);
 280
 281         env->irg = irg;
 282         prepare_rsm(&env->prolog, arch_env);
 283         prepare_rsm(&env->epilog, arch_env);
 284
 285         return env;
 286 }
 287
 288 void be_abihelper_finish(beabi_helper_env_t *env)
 289 {
 290         const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
 291
 292         free_rsm(&env->prolog, arch_env);
 293         if (env->epilog.reg_index_map != NULL) {
 294                 free_rsm(&env->epilog, arch_env);
 295         }
 296         xfree(env);
 297 }
 298
 299 void be_prolog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
 300                        arch_register_req_type_t flags)
 301 {
 302         rsm_add_reg(&env->prolog, reg, flags);
 303 }
 304
 305 ir_node *be_prolog_create_start(beabi_helper_env_t *env, dbg_info *dbgi,
 306                                 ir_node *block)
 307 {
 308         int      n_start_outs = ARR_LEN(env->prolog.regs);
 309         ir_node *start        = be_new_Start(dbgi, block, n_start_outs);
 310         int      o;
 311
 312         assert(env->prolog.value_map == NULL);
 313         env->prolog.value_map = NEW_ARR_F(ir_node*, n_start_outs);
 314
 315         for (o = 0; o < n_start_outs; ++o) {
 316                 const reg_flag_t      *regflag = &env->prolog.regs[o];
 317                 const arch_register_t *reg     = regflag->reg;
 318                 ir_node               *proj;
 319                 if (reg == NULL) {
 320                         arch_set_out_register_req(start, o, arch_no_register_req);
 321                         proj = new_r_Proj(start, mode_M, o);
 322                 } else {
 323                         be_set_constr_single_reg_out(start, o, regflag->reg,
 324                                                      regflag->flags);
 325                         arch_irn_set_register(start, o, regflag->reg);
 326                         proj = new_r_Proj(start, reg->reg_class->mode, o);
 327                 }
 328                 env->prolog.value_map[o] = proj;
 329         }
 330
 331         /* start node should really be the first thing constructed */
 332         assert(env->prolog.last_barrier == NULL);
 333         env->prolog.last_barrier = start;
 334
 335         return start;
 336 }
 337
 338 ir_node *be_prolog_create_barrier(beabi_helper_env_t *env, ir_node *block)
 339 {
 340         return rsm_create_barrier(&env->prolog, block);
 341 }
 342
 343 ir_node *be_prolog_get_reg_value(beabi_helper_env_t *env,
 344                                  const arch_register_t *reg)
 345 {
 346         return rsm_get_reg_value(&env->prolog, reg);
 347 }
 348
 349 ir_node *be_prolog_get_memory(beabi_helper_env_t *env)
 350 {
 351         return rsm_get_value(&env->prolog, 0);
 352 }
 353
 354 void be_prolog_set_reg_value(beabi_helper_env_t *env,
 355                              const arch_register_t *reg, ir_node *value)
 356 {
 357         rsm_set_reg_value(&env->prolog, reg, value);
 358 }
 359
 360 void be_prolog_set_memory(beabi_helper_env_t *env, ir_node *value)
 361 {
 362         rsm_set_value(&env->prolog, 0, value);
 363 }
 364
 365
 366
 367 void be_epilog_begin(beabi_helper_env_t *env)
 368 {
 369         const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
 370         rsm_clear_regs(&env->epilog, arch_env);
 371         env->epilog.value_map    = NEW_ARR_F(ir_node*, 1);
 372         env->epilog.value_map[0] = NULL;
 373 }
 374
 375 void be_epilog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
 376                        arch_register_req_type_t flags, ir_node *value)
 377 {
 378         int index = rsm_add_reg(&env->epilog, reg, flags);
 379         rsm_set_value(&env->epilog, index, value);
 380 }
 381
 382 void be_epilog_set_reg_value(beabi_helper_env_t *env,
 383                              const arch_register_t *reg, ir_node *value)
 384 {
 385         rsm_set_reg_value(&env->epilog, reg, value);
 386 }
 387
 388 void be_epilog_set_memory(beabi_helper_env_t *env, ir_node *value)
 389 {
 390         rsm_set_value(&env->epilog, 0, value);
 391 }
 392
 393 ir_node *be_epilog_get_reg_value(beabi_helper_env_t *env,
 394                                  const arch_register_t *reg)
 395 {
 396         return rsm_get_reg_value(&env->epilog, reg);
 397 }
 398
 399 ir_node *be_epilog_get_memory(beabi_helper_env_t *env)
 400 {
 401         return rsm_get_value(&env->epilog, 0);
 402 }
 403
 404 ir_node *be_epilog_create_barrier(beabi_helper_env_t *env, ir_node *block)
 405 {
 406         return rsm_create_barrier(&env->epilog, block);
 407 }
 408
 409 ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi,
 410                                  ir_node *block)
 411 {
 412         size_t    n_return_in = ARR_LEN(env->epilog.regs);
 413         ir_node **in          = env->epilog.value_map;
 414         int       n_res       = 1; /* TODO */
 415         unsigned  pop         = 0; /* TODO */
 416         size_t    i;
 417         ir_node  *ret;
 418
 419         assert(ARR_LEN(env->epilog.value_map) == n_return_in);
 420
 421         ret = be_new_Return(dbgi, get_irn_irg(block), block, n_res, pop,
 422                             n_return_in, in);
 423         for (i = 0; i < n_return_in; ++i) {
 424                 const reg_flag_t      *regflag = &env->epilog.regs[i];
 425                 const arch_register_t *reg     = regflag->reg;
 426                 if (reg != NULL) {
 427                         be_set_constr_single_reg_in(ret, i, reg,
 428                                                     arch_register_req_type_none);
 429                 }
 430         }
 431
 432         rsm_clear_regs(&env->epilog, be_get_irg_arch_env(env->irg));
 433         env->epilog.last_barrier = NULL;
 434
 435         return ret;
 436 }
 437
 438 static void add_missing_keep_walker(ir_node *node, void *data)
 439 {
 440         int              n_outs, i;
 441         unsigned        *found_projs;
 442         const ir_edge_t *edge;
 443         ir_mode         *mode = get_irn_mode(node);
 444         ir_node         *last_keep;
 445         (void) data;
 446         if (mode != mode_T)
 447                 return;
 448
 449         n_outs = arch_irn_get_n_outs(node);
 450         if (n_outs <= 0)
 451                 return;
 452
 453         rbitset_alloca(found_projs, n_outs);
 454         foreach_out_edge(node, edge) {
 455                 ir_node *succ = get_edge_src_irn(edge);
 456                 ir_mode *mode = get_irn_mode(succ);
 457                 int      pn;
 458
 459                 /* The node could be kept */
 460                 if (is_End(succ) || is_Anchor(succ))
 461                         continue;
 462
 463                 if (mode == mode_M || mode == mode_X)
 464                         continue;
 465
 466                 pn = get_Proj_proj(succ);
 467                 assert(pn < n_outs);
 468                 rbitset_set(found_projs, pn);
 469         }
 470
 471
 472         /* are keeps missing? */
 473         last_keep = NULL;
 474         for (i = 0; i < n_outs; ++i) {
 475                 ir_node                     *block;
 476                 ir_node                     *in[1];
 477                 const arch_register_req_t   *req;
 478                 const arch_register_class_t *cls;
 479
 480                 if (rbitset_is_set(found_projs, i)) {
 481                         continue;
 482                 }
 483
 484                 req = arch_get_out_register_req(node, i);
 485                 cls = req->cls;
 486                 if (cls == NULL || (cls->flags & arch_register_class_flag_manual_ra)) {
 487                         continue;
 488                 }
 489
 490                 block = get_nodes_block(node);
 491                 in[0] = new_r_Proj(node, arch_register_class_mode(cls), i);
 492                 if (last_keep != NULL) {
 493                         be_Keep_add_node(last_keep, cls, in[0]);
 494                 } else {
 495                         last_keep = be_new_Keep(block, 1, in);
 496                         if (sched_is_scheduled(node)) {
 497                                 sched_add_after(node, last_keep);
 498                         }
 499                 }
 500         }
 501 }
 502
 503 void be_add_missing_keeps(ir_graph *irg)
 504 {
 505         irg_walk_graph(irg, add_missing_keep_walker, NULL, NULL);
 506 }
 507
 508
 509 /**
 510  * Link the node into its block list as a new head.
 511  */
 512 static void collect_node(ir_node *node)
 513 {
 514         ir_node *block = get_nodes_block(node);
 515         ir_node *old   = (ir_node*)get_irn_link(block);
 516
 517         set_irn_link(node, old);
 518         set_irn_link(block, node);
 519 }
 520
 521 /**
 522  * Post-walker: link all nodes that probably access the stack into lists of their block.
 523  */
 524 static void link_ops_in_block_walker(ir_node *node, void *data)
 525 {
 526         (void) data;
 527
 528         switch (get_irn_opcode(node)) {
 529         case iro_Return:
 530         case iro_Call:
 531                 collect_node(node);
 532                 break;
 533         case iro_Alloc:
 534                 /** all non-stack alloc nodes should be lowered before the backend */
 535                 assert(get_Alloc_where(node) == stack_alloc);
 536                 collect_node(node);
 537                 break;
 538         case iro_Free:
 539                 assert(get_Free_where(node) == stack_alloc);
 540                 collect_node(node);
 541                 break;
 542         case iro_Builtin:
 543                 if (get_Builtin_kind(node) == ir_bk_return_address) {
 544                         ir_node   *param = get_Builtin_param(node, 0);
 545                         ir_tarval *tv    = get_Const_tarval(param); /* must be Const */
 546                         long       value = get_tarval_long(tv);
 547                         if (value > 0) {
 548                                 /* not the return address of the current function:
 549                                  * we need the stack pointer for the frame climbing */
 550                                 collect_node(node);
 551                         }
 552                 }
 553                 break;
 554         default:
 555                 break;
 556         }
 557 }
 558
 559 static ir_heights_t *heights;
 560
 561 /**
 562  * Check if a node is somehow data dependent on another one.
 563  * both nodes must be in the same basic block.
 564  * @param n1 The first node.
 565  * @param n2 The second node.
 566  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 567  */
 568 static int dependent_on(const ir_node *n1, const ir_node *n2)
 569 {
 570         assert(get_nodes_block(n1) == get_nodes_block(n2));
 571
 572         return heights_reachable_in_block(heights, n1, n2);
 573 }
 574
 575 /**
 576  * Classical qsort() comparison function behavior:
 577  *
 578  * 0  if both elements are equal, no node depend on the other
 579  * +1 if first depends on second (first is greater)
 580  * -1 if second depends on first (second is greater)
 581 */
 582 static int cmp_call_dependency(const void *c1, const void *c2)
 583 {
 584         const ir_node *n1 = *(const ir_node **) c1;
 585         const ir_node *n2 = *(const ir_node **) c2;
 586
 587         if (dependent_on(n1, n2))
 588                 return 1;
 589
 590         if (dependent_on(n2, n1))
 591                 return -1;
 592
 593         /* The nodes have no depth order, but we need a total order because qsort()
 594          * is not stable. */
 595         return get_irn_idx(n2) - get_irn_idx(n1);
 596 }
 597
 598 /**
 599  * Block-walker: sorts dependencies and remember them into a phase
 600  */
 601 static void process_ops_in_block(ir_node *block, void *data)
 602 {
 603         ir_phase *phase = (ir_phase*)data;
 604         unsigned  n;
 605         unsigned  n_nodes;
 606         ir_node  *node;
 607         ir_node **nodes;
 608
 609         n_nodes = 0;
 610         for (node = (ir_node*)get_irn_link(block); node != NULL;
 611              node = (ir_node*)get_irn_link(node)) {
 612                 ++n_nodes;
 613         }
 614
 615         if (n_nodes == 0)
 616                 return;
 617
 618         nodes = XMALLOCN(ir_node*, n_nodes);
 619         n = 0;
 620         for (node = (ir_node*)get_irn_link(block); node != NULL;
 621              node = (ir_node*)get_irn_link(node)) {
 622                 nodes[n++] = node;
 623         }
 624         assert(n == n_nodes);
 625
 626         /* order nodes according to their data dependencies */
 627         qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
 628
 629         /* remember the calculated dependency into a phase */
 630         for (n = n_nodes-1; n > 0; --n) {
 631                 ir_node *node = nodes[n];
 632                 ir_node *pred = nodes[n-1];
 633
 634                 phase_set_irn_data(phase, node, pred);
 635         }
 636         xfree(nodes);
 637 }
 638
 639 void be_collect_stacknodes(beabi_helper_env_t *env)
 640 {
 641         ir_graph *irg = env->irg;
 642
 643         /* collect all potential^stack accessing nodes */
 644         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, NULL);
 645
 646         assert(env->stack_order == NULL);
 647         env->stack_order = new_phase(irg, phase_irn_init_default);
 648
 649         /* use heights to create a total order for those nodes: this order is stored
 650          * in the created phase */
 651         heights = heights_new(irg);
 652         irg_block_walk_graph(irg, NULL, process_ops_in_block, env->stack_order);
 653         heights_free(heights);
 654 }
 655
 656 ir_node *be_get_stack_pred(const beabi_helper_env_t *env, const ir_node *node)
 657 {
 658         return (ir_node*)phase_get_irn_data(env->stack_order, node);
 659 }