nsz Git - libfirm/blob - ir/be/ia32/ia32_address_mode.c

   1 /*
   2  * Copyright (C) 1995-2010 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       This file contains functions for matching firm graphs for
  23  *              nodes that can be used as address mode for x86 instructions
  24  * @author      Matthias Braun
  25  */
  26 #include "config.h"
  27
  28 #include "ia32_address_mode.h"
  29 #include "ia32_transform.h"
  30
  31 #include "irtypes.h"
  32 #include "irnode_t.h"
  33 #include "irprintf.h"
  34 #include "error.h"
  35 #include "iredges_t.h"
  36 #include "irgwalk.h"
  37
  38 #include "benode.h"
  39 #include "belive.h"
  40
  41 #define AGGRESSIVE_AM
  42
  43 /* gas/ld don't support negative symconsts :-( */
  44 #undef SUPPORT_NEGATIVE_SYMCONSTS
  45
  46 static bitset_t *non_address_mode_nodes;
  47
  48 /**
  49  * Recursive worker for checking if a DAG with root node can be represented as a simple immediate,
  50  *
  51  * @param node       the node
  52  * @param symconsts  number of symconsts found so far
  53  * @param negate     if set, the immediate must be negated
  54  *
  55  * @return non-zero if the DAG represents an immediate, 0 else
  56  */
  57 static bool do_is_immediate(const ir_node *node, int *symconsts, bool negate)
  58 {
  59         ir_node *left;
  60         ir_node *right;
  61
  62         switch (get_irn_opcode(node)) {
  63         case iro_Const:
  64                 /* Consts are typically immediates */
  65                 if (!tarval_is_long(get_Const_tarval(node))) {
  66 #ifdef DEBUG_libfirm
  67                         ir_fprintf(stderr,
  68                                    "Optimisation warning tarval of %+F(%+F) is not a long.\n",
  69                                    node, get_irn_irg(node));
  70 #endif
  71                         return false;
  72                 }
  73                 return true;
  74         case iro_SymConst:
  75                 /* the first SymConst of a DAG can be fold into an immediate */
  76 #ifndef SUPPORT_NEGATIVE_SYMCONSTS
  77                 /* unfortunately the assembler/linker doesn't support -symconst */
  78                 if (negate)
  79                         return false;
  80 #endif
  81                 if (get_SymConst_kind(node) != symconst_addr_ent)
  82                         return false;
  83                 if (++*symconsts > 1)
  84                         return false;
  85
  86                 return true;
  87         case iro_Unknown:
  88                 /* we can use '0' for Unknowns */
  89                 return true;
  90         case iro_Add:
  91         case iro_Sub:
  92                 /* Add's and Sub's are typically supported as long as both operands are
  93                  * immediates */
  94                 if (ia32_is_non_address_mode_node(node))
  95                         return false;
  96
  97                 left = get_binop_left(node);
  98                 if (!do_is_immediate(left, symconsts, negate))
  99                         return false;
 100                 right = get_binop_right(node);
 101                 if (!do_is_immediate(right, symconsts, is_Sub(node) ? !negate : negate))
 102                         return false;
 103
 104                 return true;
 105         default:
 106                 /* all other nodes are NO immediates */
 107                 return false;
 108         }
 109 }
 110
 111 /**
 112  * Check if a DAG starting with root node can be folded into an address mode
 113  * as an immediate.
 114  *
 115  * @param addr    the address mode data so far
 116  * @param node    the node
 117  * @param negate  if set, the immediate must be negated
 118  */
 119 static int is_immediate(ia32_address_t *addr, const ir_node *node, bool negate)
 120 {
 121         int symconsts = (addr->symconst_ent != NULL);
 122         return do_is_immediate(node, &symconsts, negate);
 123 }
 124
 125 /**
 126  * Place a DAG with root node into an address mode.
 127  *
 128  * @param addr    the address mode data so far
 129  * @param node    the node
 130  * @param negate  if set, the immediate must be negated
 131  */
 132 static void eat_immediate(ia32_address_t *addr, ir_node *node, bool negate)
 133 {
 134         ir_tarval *tv;
 135         ir_node   *left;
 136         ir_node   *right;
 137         long      val;
 138
 139         switch (get_irn_opcode(node)) {
 140         case iro_Const:
 141                 /* simply add the value to the offset */
 142                 tv = get_Const_tarval(node);
 143                 val = get_tarval_long(tv);
 144                 if (negate) {
 145                         addr->offset -= val;
 146                 } else {
 147                         addr->offset += val;
 148                 }
 149                 break;
 150         case iro_SymConst:
 151                 /* place the entity into the symconst */
 152                 if (addr->symconst_ent != NULL) {
 153                         panic("Internal error: more than 1 symconst in address calculation");
 154                 }
 155                 addr->symconst_ent  = get_SymConst_entity(node);
 156                 if (get_entity_owner(addr->symconst_ent) == get_tls_type())
 157                         addr->tls_segment = true;
 158 #ifndef SUPPORT_NEGATIVE_SYMCONSTS
 159                 assert(!negate);
 160 #endif
 161                 addr->symconst_sign = negate;
 162                 break;
 163         case iro_Unknown:
 164                 break;
 165         case iro_Add:
 166                 assert(!ia32_is_non_address_mode_node(node));
 167                 left  = get_Add_left(node);
 168                 eat_immediate(addr, left, negate);
 169                 right = get_Add_right(node);
 170                 eat_immediate(addr, right, negate);
 171                 break;
 172         case iro_Sub:
 173                 assert(!ia32_is_non_address_mode_node(node));
 174                 left  = get_Sub_left(node);
 175                 eat_immediate(addr, left, negate);
 176                 right = get_Sub_right(node);
 177                 eat_immediate(addr, right, !negate);
 178                 break;
 179         default:
 180                 panic("Internal error in immediate address calculation");
 181         }
 182 }
 183
 184 /**
 185  * Place operands of node into an address mode.
 186  *
 187  * @param addr    the address mode data so far
 188  * @param node    the node
 189  * @param flags   the flags
 190  *
 191  * @return the folded node
 192  */
 193 static ir_node *eat_immediates(ia32_address_t *addr, ir_node *node,
 194                                ia32_create_am_flags_t flags)
 195 {
 196         if (!(flags & ia32_create_am_force)     &&
 197                         ia32_is_non_address_mode_node(node) &&
 198                         (!(flags & ia32_create_am_double_use) || get_irn_n_edges(node) > 2))
 199                 return node;
 200
 201         if (is_Add(node)) {
 202                 ir_node *left  = get_Add_left(node);
 203                 ir_node *right = get_Add_right(node);
 204
 205                 if (is_immediate(addr, left, 0)) {
 206                         eat_immediate(addr, left, 0);
 207                         return eat_immediates(addr, right, ia32_create_am_normal);
 208                 }
 209                 if (is_immediate(addr, right, 0)) {
 210                         eat_immediate(addr, right, 0);
 211                         return eat_immediates(addr, left, ia32_create_am_normal);
 212                 }
 213         } else if (is_Sub(node)) {
 214                 ir_node *left  = get_Sub_left(node);
 215                 ir_node *right = get_Sub_right(node);
 216
 217                 if (is_immediate(addr, right, 1)) {
 218                         eat_immediate(addr, right, 1);
 219                         return eat_immediates(addr, left, ia32_create_am_normal);
 220                 }
 221         }
 222
 223         return node;
 224 }
 225
 226 /**
 227  * Try to place a Shl into an address mode.
 228  *
 229  * @param addr    the address mode data so far
 230  * @param node   the node to place
 231  *
 232  * @return non-zero on success
 233  */
 234 static int eat_shl(ia32_address_t *addr, ir_node *node)
 235 {
 236         ir_node *shifted_val;
 237         long     val;
 238
 239         if (is_Shl(node)) {
 240                 ir_node   *right = get_Shl_right(node);
 241                 ir_tarval *tv;
 242
 243                 /* we can use shl with 1, 2 or 3 shift */
 244                 if (!is_Const(right))
 245                         return 0;
 246                 tv = get_Const_tarval(right);
 247                 if (!tarval_is_long(tv))
 248                         return 0;
 249
 250                 val = get_tarval_long(tv);
 251                 if (val < 0 || val > 3)
 252                         return 0;
 253                 if (val == 0) {
 254                         ir_fprintf(stderr, "Optimisation warning: unoptimized Shl(,0) found\n");
 255                 }
 256
 257                 shifted_val = get_Shl_left(node);
 258         } else if (is_Add(node)) {
 259                 /* might be an add x, x */
 260                 ir_node *left  = get_Add_left(node);
 261                 ir_node *right = get_Add_right(node);
 262
 263                 if (left != right)
 264                         return 0;
 265                 if (is_Const(left))
 266                         return 0;
 267
 268                 val         = 1;
 269                 shifted_val = left;
 270         } else {
 271                 return 0;
 272         }
 273
 274         /* we can only eat a shl if we don't have a scale or index set yet */
 275         if (addr->scale != 0 || addr->index != NULL)
 276                 return 0;
 277         if (ia32_is_non_address_mode_node(node))
 278                 return 0;
 279
 280 #ifndef AGGRESSIVE_AM
 281         if (get_irn_n_edges(node) > 1)
 282                 return 0;
 283 #endif
 284
 285         addr->scale = val;
 286         addr->index = shifted_val;
 287         return 1;
 288 }
 289
 290 /* Create an address mode for a given node. */
 291 void ia32_create_address_mode(ia32_address_t *addr, ir_node *node, ia32_create_am_flags_t flags)
 292 {
 293         ir_node *eat_imms;
 294
 295         if (is_immediate(addr, node, 0)) {
 296                 eat_immediate(addr, node, 0);
 297                 return;
 298         }
 299
 300 #ifndef AGGRESSIVE_AM
 301         if (!(flags & ia32_create_am_force) && get_irn_n_edges(node) > 1) {
 302                 addr->base = node;
 303                 return;
 304         }
 305 #endif
 306
 307         if (!(flags & ia32_create_am_force)     &&
 308                         ia32_is_non_address_mode_node(node) &&
 309                         (!(flags & ia32_create_am_double_use) || get_irn_n_edges(node) > 2)) {
 310                 addr->base = node;
 311                 return;
 312         }
 313
 314         eat_imms = eat_immediates(addr, node, flags);
 315         if (eat_imms != node) {
 316                 if (flags & ia32_create_am_force) {
 317                         eat_imms = ia32_skip_downconv(eat_imms);
 318                 }
 319
 320                 node = eat_imms;
 321 #ifndef AGGRESSIVE_AM
 322                 if (get_irn_n_edges(node) > 1) {
 323                         addr->base = node;
 324                         return;
 325                 }
 326 #endif
 327                 if (ia32_is_non_address_mode_node(node)) {
 328                         addr->base = node;
 329                         return;
 330                 }
 331         }
 332
 333         /* starting point Add, Sub or Shl, FrameAddr */
 334         if (is_Shl(node)) {
 335                 /* We don't want to eat add x, x as shl here, so only test for real Shl
 336                  * instructions, because we want the former as Lea x, x, not Shl x, 1 */
 337                 if (eat_shl(addr, node))
 338                         return;
 339         } else if (is_immediate(addr, node, 0)) {
 340                 eat_immediate(addr, node, 0);
 341                 return;
 342         } else if (be_is_FrameAddr(node)) {
 343                 assert(addr->base == NULL);
 344                 assert(addr->frame_entity == NULL);
 345                 addr->base         = be_get_FrameAddr_frame(node);
 346                 addr->use_frame    = 1;
 347                 addr->frame_entity = be_get_FrameAddr_entity(node);
 348                 return;
 349         } else if (is_Add(node)) {
 350                 ir_node *left  = get_Add_left(node);
 351                 ir_node *right = get_Add_right(node);
 352
 353                 if (flags & ia32_create_am_force) {
 354                         left  = ia32_skip_downconv(left);
 355                         right = ia32_skip_downconv(right);
 356                 }
 357
 358                 assert(flags & ia32_create_am_force || !is_immediate(addr, left,  0));
 359                 assert(flags & ia32_create_am_force || !is_immediate(addr, right, 0));
 360
 361                 if (eat_shl(addr, left)) {
 362                         left = NULL;
 363                 } else if (eat_shl(addr, right)) {
 364                         right = NULL;
 365                 }
 366                 if (left != NULL          &&
 367                                 be_is_FrameAddr(left) &&
 368                                 !ia32_is_non_address_mode_node(left)) {
 369                         assert(addr->base == NULL);
 370                         assert(addr->frame_entity == NULL);
 371                         addr->base         = be_get_FrameAddr_frame(left);
 372                         addr->use_frame    = 1;
 373                         addr->frame_entity = be_get_FrameAddr_entity(left);
 374                         left               = NULL;
 375                 } else if (right != NULL   &&
 376                                 be_is_FrameAddr(right) &&
 377                                 !ia32_is_non_address_mode_node(right)) {
 378                         assert(addr->base == NULL);
 379                         assert(addr->frame_entity == NULL);
 380                         addr->base         = be_get_FrameAddr_frame(right);
 381                         addr->use_frame    = 1;
 382                         addr->frame_entity = be_get_FrameAddr_entity(right);
 383                         right              = NULL;
 384                 }
 385
 386                 if (left != NULL) {
 387                         if (addr->base != NULL) {
 388                                 assert(addr->index == NULL && addr->scale == 0);
 389                                 assert(right == NULL);
 390                                 addr->index = left;
 391                         } else {
 392                                 addr->base = left;
 393                         }
 394                 }
 395                 if (right != NULL) {
 396                         if (addr->base == NULL) {
 397                                 addr->base = right;
 398                         } else {
 399                                 assert(addr->index == NULL && addr->scale == 0);
 400                                 addr->index = right;
 401                         }
 402                 }
 403                 return;
 404         }
 405
 406         addr->base = node;
 407 }
 408
 409 void ia32_mark_non_am(ir_node *node)
 410 {
 411         bitset_set(non_address_mode_nodes, get_irn_idx(node));
 412 }
 413
 414 int ia32_is_non_address_mode_node(ir_node const *node)
 415 {
 416         return bitset_is_set(non_address_mode_nodes, get_irn_idx(node));
 417 }
 418
 419 /**
 420  * Check if a given value is last used (i.e. die after) the block of some
 421  * other node.
 422  */
 423 static int value_last_used_here(be_lv_t *lv, ir_node *here, ir_node *value)
 424 {
 425         ir_node *block = get_nodes_block(here);
 426
 427         /* If the value is live end it is for sure it does not die here */
 428         if (be_is_live_end(lv, block, value)) return 0;
 429
 430         /* if multiple nodes in this block use the value, then we cannot decide
 431          * whether the value will die here (because there is no schedule yet).
 432          * Assume it does not die in this case. */
 433         foreach_out_edge(value, edge) {
 434                 ir_node *user = get_edge_src_irn(edge);
 435                 if (user != here && get_nodes_block(user) == block) {
 436                         return 0;
 437                 }
 438         }
 439
 440         return 1;
 441 }
 442
 443 static bool simple_is_immediate(const ir_node *node)
 444 {
 445         int symconsts = 0;
 446         return do_is_immediate(node, &symconsts, false);
 447 }
 448
 449 /**
 450  * Walker: mark those nodes that cannot be part of an address mode because
 451  * their value must be accessed through a register
 452  */
 453 static void mark_non_address_nodes(ir_node *node, void *env)
 454 {
 455         be_lv_t *lv = (be_lv_t*)env;
 456         int      arity;
 457         int      i;
 458         ir_node *val;
 459         ir_node *left;
 460         ir_node *right;
 461         ir_mode *mode;
 462
 463         mode = get_irn_mode(node);
 464         if (!mode_is_int(mode) && !mode_is_reference(mode) && mode != mode_b)
 465                 return;
 466
 467         switch (get_irn_opcode(node)) {
 468         case iro_Load:
 469                 /* Nothing to do. especially do not mark the pointer, because we want to
 470                  * turn it into AM. */
 471                 break;
 472
 473         case iro_Store:
 474                 /* Do not mark the pointer, because we want to turn it into AM. */
 475                 val = get_Store_value(node);
 476                 ia32_mark_non_am(val);
 477                 break;
 478
 479         case iro_Shl:
 480         case iro_Add:
 481                 /* only 1 user: AM folding is always beneficial */
 482                 if (get_irn_n_edges(node) <= 1)
 483                         break;
 484
 485                 /* for adds and shls with multiple users we use this heuristic:
 486                  * we do not fold them into address mode if their operands don't live
 487                  * out of the block, because in this case we will reduce register
 488                  * pressure. Otherwise we fold them in aggressively in the hope, that
 489                  * the node itself doesn't exist anymore and we were able to save the
 490                  * register for the result */
 491                 left  = get_binop_left(node);
 492                 right = get_binop_right(node);
 493
 494                 /* if any of the operands is an immediate then this will not
 495                  * increase register pressure */
 496                 if (simple_is_immediate(left) || simple_is_immediate(right))
 497                         return;
 498
 499                 /* Fold AM if any of the two operands does not die here. This duplicates
 500                  * an addition and has the same register pressure for the case that only
 501                  * one operand dies, but is faster (on Pentium 4).
 502                  * && instead of || only folds AM if both operands do not die here */
 503                 if (!value_last_used_here(lv, node, left) ||
 504                     !value_last_used_here(lv, node, right)) {
 505                         return;
 506                 }
 507
 508                 /* At least one of left and right are not used by anyone else, so it is
 509                  * beneficial for the register pressure (if both are unused otherwise,
 510                  * else neutral) and ALU use to not fold AM. */
 511                 ia32_mark_non_am(node);
 512                 break;
 513
 514         default:
 515                 arity = get_irn_arity(node);
 516
 517                 for (i = 0; i < arity; ++i) {
 518                         ir_node *in = get_irn_n(node, i);
 519                         ia32_mark_non_am(in);
 520                 }
 521                 break;
 522         }
 523 }
 524
 525 void ia32_calculate_non_address_mode_nodes(ir_graph *irg)
 526 {
 527         be_lv_t *lv;
 528
 529         be_assure_live_chk(irg);
 530         lv = be_get_irg_liveness(irg);
 531
 532         non_address_mode_nodes = bitset_malloc(get_irg_last_idx(irg));
 533
 534         irg_walk_graph(irg, NULL, mark_non_address_nodes, lv);
 535 }
 536
 537 void ia32_free_non_address_mode_nodes(void)
 538 {
 539         bitset_free(non_address_mode_nodes);
 540 }