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

   1 /*
   2  * Copyright (C) 1995-2007 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 addressmode for x86 commands
  24  * @author      Matthias Braun
  25  * @version     $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include "ia32_address_mode.h"
  32 #include "ia32_transform.h"
  33
  34 #include "irtypes.h"
  35 #include "irnode_t.h"
  36 #include "irprintf.h"
  37 #include "error.h"
  38 #include "iredges_t.h"
  39 #include "irgwalk.h"
  40
  41 #include "../benode_t.h"
  42
  43 #define AGGRESSIVE_AM
  44
  45 /* gas/ld don't support negative symconsts :-( */
  46 #undef SUPPORT_NEGATIVE_SYMCONSTS
  47
  48 static bitset_t *non_address_mode_nodes;
  49
  50 static int do_is_immediate(const ir_node *node, int *symconsts, int negate)
  51 {
  52         ir_node *left;
  53         ir_node *right;
  54
  55         switch(get_irn_opcode(node)) {
  56         case iro_Const:
  57                 if(!tarval_is_long(get_Const_tarval(node))) {
  58 #ifdef DEBUG_libfirm
  59                         ir_fprintf(stderr, "Optimisation warning tarval of %+F(%+F) is not "
  60                                    "a long.\n", node, current_ir_graph);
  61 #endif
  62                         return 0;
  63                 }
  64                 return 1;
  65         case iro_SymConst:
  66 #ifndef SUPPORT_NEGATIVE_SYMCONSTS
  67                 /* unfortunately the assembler/linker doesn't support -symconst */
  68                 if(negate)
  69                         return 0;
  70 #endif
  71
  72                 if(get_SymConst_kind(node) != symconst_addr_ent)
  73                         return 0;
  74                 (*symconsts)++;
  75                 if(*symconsts > 1)
  76                         return 0;
  77
  78                 return 1;
  79         case iro_Add:
  80         case iro_Sub:
  81                 if(bitset_is_set(non_address_mode_nodes, get_irn_idx(node)))
  82                         return 0;
  83
  84                 left  = get_binop_left(node);
  85                 right = get_binop_right(node);
  86                 if(!do_is_immediate(left, symconsts, negate))
  87                         return 0;
  88                 if(!do_is_immediate(right, symconsts, is_Sub(node) ? !negate : negate))
  89                         return 0;
  90
  91                 return 1;
  92         default:
  93                 break;
  94         }
  95
  96         return 0;
  97 }
  98
  99 static int is_immediate_simple(const ir_node *node)
 100 {
 101         int symconsts = 0;
 102         return do_is_immediate(node, &symconsts, 0);
 103 }
 104
 105 static int is_immediate(ia32_address_t *addr, const ir_node *node, int negate)
 106 {
 107         int symconsts = 0;
 108         if(addr->symconst_ent != NULL)
 109                 symconsts = 1;
 110
 111         return do_is_immediate(node, &symconsts, negate);
 112 }
 113
 114 static void eat_immediate(ia32_address_t *addr, ir_node *node, int negate)
 115 {
 116         tarval  *tv;
 117         ir_node *left;
 118         ir_node *right;
 119   long val;
 120
 121         switch(get_irn_opcode(node)) {
 122         case iro_Const:
 123                 tv = get_Const_tarval(node);
 124                 val = get_tarval_long(tv);
 125                 if(negate) {
 126                         addr->offset -= val;
 127                 } else {
 128                         addr->offset += val;
 129                 }
 130                 break;
 131         case iro_SymConst:
 132                 if(addr->symconst_ent != NULL) {
 133                         panic("Internal error: more than 1 symconst in address "
 134                               "calculation");
 135                 }
 136                 addr->symconst_ent  = get_SymConst_entity(node);
 137 #ifndef SUPPORT_NEGATIVE_SYMCONSTS
 138                 assert(!negate);
 139 #endif
 140                 addr->symconst_sign = negate;
 141                 break;
 142         case iro_Add:
 143                 assert(!bitset_is_set(non_address_mode_nodes, get_irn_idx(node)));
 144                 left  = get_Add_left(node);
 145                 right = get_Add_right(node);
 146                 eat_immediate(addr, left, negate);
 147                 eat_immediate(addr, right, negate);
 148                 break;
 149         case iro_Sub:
 150                 assert(!bitset_is_set(non_address_mode_nodes, get_irn_idx(node)));
 151                 left  = get_Sub_left(node);
 152                 right = get_Sub_right(node);
 153                 eat_immediate(addr, left, negate);
 154                 eat_immediate(addr, right, !negate);
 155                 break;
 156         default:
 157                 panic("Internal error in immediate address calculation");
 158         }
 159 }
 160
 161 static ir_node *eat_immediates(ia32_address_t *addr, ir_node *node, int force)
 162 {
 163         if(!force && bitset_is_set(non_address_mode_nodes, get_irn_idx(node)))
 164                 return node;
 165
 166         if(is_Add(node)) {
 167                 ir_node *left  = get_Add_left(node);
 168                 ir_node *right = get_Add_right(node);
 169
 170                 if(is_immediate(addr, left, 0)) {
 171                         eat_immediate(addr, left, 0);
 172                         return eat_immediates(addr, right, 0);
 173                 }
 174                 if(is_immediate(addr, right, 0)) {
 175                         eat_immediate(addr, right, 0);
 176                         return eat_immediates(addr, left, 0);
 177                 }
 178         } else if(is_Sub(node)) {
 179                 ir_node *left  = get_Sub_left(node);
 180                 ir_node *right = get_Sub_right(node);
 181
 182                 if(is_immediate(addr, right, 1)) {
 183                         eat_immediate(addr, right, 1);
 184                         return eat_immediates(addr, left, 0);
 185                 }
 186         }
 187
 188         return node;
 189 }
 190
 191 static int eat_shl(ia32_address_t *addr, ir_node *node)
 192 {
 193         ir_node *right = get_Shl_right(node);
 194         tarval  *tv;
 195         long     val;
 196
 197         /* we can only eat a shl if we don't have a scale or index set */
 198         if(addr->scale != 0 || addr->index != NULL)
 199                 return 0;
 200
 201         /* we can use shl with 1, 2 or 3 shift */
 202         if(!is_Const(right))
 203                 return 0;
 204         tv = get_Const_tarval(right);
 205         if(!tarval_is_long(tv))
 206                 return 0;
 207         val = get_tarval_long(tv);
 208         if(val < 0 || val > 3)
 209                 return 0;
 210         if(val == 0) {
 211                 ir_fprintf(stderr, "Optimisation warning: unoptimized Shl(,0) found\n");
 212         }
 213         if(bitset_is_set(non_address_mode_nodes, get_irn_idx(node)))
 214                 return 0;
 215
 216 #ifndef AGGRESSIVE_AM
 217         if(get_irn_n_edges(node) > 1)
 218                 return 0;
 219 #endif
 220
 221         addr->scale = val;
 222         addr->index = eat_immediates(addr, get_Shl_left(node), 0);
 223         return 1;
 224 }
 225
 226 static INLINE int mode_needs_gp_reg(ir_mode *mode) {
 227         if(mode == mode_fpcw)
 228                 return 0;
 229         if(get_mode_size_bits(mode) > 32)
 230                 return 0;
 231         return mode_is_int(mode) || mode_is_reference(mode) || mode == mode_b;
 232 }
 233
 234 static int is_downconv(const ir_node *node)
 235 {
 236         ir_mode *src_mode;
 237         ir_mode *dest_mode;
 238
 239         if(!is_Conv(node))
 240                 return 0;
 241
 242         /* we only want to skip the conv when we're the only user
 243          * (not optimal but for now...)
 244          */
 245         if(get_irn_n_edges(node) > 1)
 246                 return 0;
 247
 248         src_mode  = get_irn_mode(get_Conv_op(node));
 249         dest_mode = get_irn_mode(node);
 250         return mode_needs_gp_reg(src_mode)
 251                 && mode_needs_gp_reg(dest_mode)
 252                 && get_mode_size_bits(dest_mode) < get_mode_size_bits(src_mode);
 253 }
 254
 255 static ir_node *skip_downconv(ir_node *node)
 256 {
 257 #if 0
 258         while(is_downconv(node))
 259                 node = get_Conv_op(node);
 260 #endif
 261
 262         return node;
 263 }
 264
 265 void ia32_create_address_mode(ia32_address_t *addr, ir_node *node, int force)
 266 {
 267         int      res = 0;
 268         ir_node *eat_imms;
 269
 270         if(is_immediate(addr, node, 0)) {
 271                 eat_immediate(addr, node, 0);
 272                 return;
 273         }
 274
 275 #ifndef AGGRESSIVE_AM
 276         if(!force && get_irn_n_edges(node) > 1) {
 277                 addr->base = node;
 278                 return;
 279         }
 280 #endif
 281
 282         if(!force && bitset_is_set(non_address_mode_nodes, get_irn_idx(node))) {
 283                 addr->base = node;
 284                 return;
 285         }
 286
 287         eat_imms = eat_immediates(addr, node, force);
 288         if(eat_imms != node) {
 289                 if(force) {
 290                         eat_imms = skip_downconv(eat_imms);
 291                 }
 292
 293                 res  = 1;
 294                 node = eat_imms;
 295 #ifndef AGGRESSIVE_AM
 296                 if(get_irn_n_edges(node) > 1) {
 297                         addr->base = node;
 298                         return;
 299                 }
 300 #endif
 301                 if(bitset_is_set(non_address_mode_nodes, get_irn_idx(node))) {
 302                         addr->base = node;
 303                         return;
 304                 }
 305         }
 306
 307         /* starting point Add, Sub or Shl, FrameAddr */
 308         if(is_Shl(node)) {
 309                 if(eat_shl(addr, node))
 310                         return;
 311         } else if(is_immediate(addr, node, 0)) {
 312                 eat_immediate(addr, node, 0);
 313                 return;
 314         } else if(be_is_FrameAddr(node)) {
 315                 assert(addr->base == NULL);
 316                 assert(addr->frame_entity == NULL);
 317                 addr->base         = be_get_FrameAddr_frame(node);
 318                 addr->use_frame    = 1;
 319                 addr->frame_entity = be_get_FrameAddr_entity(node);
 320                 return;
 321         } else if(is_Add(node)) {
 322                 ir_node *left  = get_Add_left(node);
 323                 ir_node *right = get_Add_right(node);
 324
 325                 if(force) {
 326                         left  = skip_downconv(left);
 327                         right = skip_downconv(right);
 328                 }
 329
 330                 assert(force || !is_immediate(addr, left, 0));
 331                 assert(force || !is_immediate(addr, right, 0));
 332
 333                 if(is_Shl(left) && eat_shl(addr, left)) {
 334                         left = NULL;
 335                 } else if(is_Shl(right) && eat_shl(addr, right)) {
 336                         right = NULL;
 337                 }
 338                 if(left != NULL && be_is_FrameAddr(left)
 339                                 && !bitset_is_set(non_address_mode_nodes, get_irn_idx(left))) {
 340                         assert(addr->base == NULL);
 341                         assert(addr->frame_entity == NULL);
 342                         addr->base         = be_get_FrameAddr_frame(left);
 343                         addr->use_frame    = 1;
 344                         addr->frame_entity = be_get_FrameAddr_entity(left);
 345                         left               = NULL;
 346                 } else if(right != NULL && be_is_FrameAddr(right)
 347                                 && !bitset_is_set(non_address_mode_nodes, get_irn_idx(right))) {
 348                         assert(addr->base == NULL);
 349                         assert(addr->frame_entity == NULL);
 350                         addr->base         = be_get_FrameAddr_frame(right);
 351                         addr->use_frame    = 1;
 352                         addr->frame_entity = be_get_FrameAddr_entity(right);
 353                         right              = NULL;
 354                 }
 355
 356                 if(left != NULL) {
 357                         if(addr->base != NULL) {
 358                                 assert(addr->index == NULL && addr->scale == 0);
 359                                 assert(right == NULL);
 360                                 addr->index = left;
 361                         } else {
 362                                 addr->base = left;
 363                         }
 364                 }
 365                 if(right != NULL) {
 366                         if(addr->base == NULL) {
 367                                 addr->base = right;
 368                         } else {
 369                                 assert(addr->index == NULL && addr->scale == 0);
 370                                 addr->index = right;
 371                         }
 372                 }
 373                 return;
 374         }
 375
 376         addr->base = node;
 377 }
 378
 379
 380
 381 static void mark_non_address_nodes(ir_node *node, void *env)
 382 {
 383         int i, arity;
 384         ir_node *ptr;
 385         ir_node *mem;
 386         ir_node *val;
 387         ir_node *left;
 388         ir_node *right;
 389         (void) env;
 390
 391         switch(get_irn_opcode(node)) {
 392         case iro_Load:
 393                 ptr = get_Load_ptr(node);
 394                 mem = get_Load_mem(node);
 395
 396                 bitset_set(non_address_mode_nodes, get_irn_idx(mem));
 397                 break;
 398
 399         case iro_Store:
 400                 val = get_Store_value(node);
 401                 ptr = get_Store_ptr(node);
 402                 mem = get_Store_mem(node);
 403
 404                 bitset_set(non_address_mode_nodes, get_irn_idx(val));
 405                 bitset_set(non_address_mode_nodes, get_irn_idx(mem));
 406                 break;
 407
 408         case iro_Add:
 409                 left  = get_Add_left(node);
 410                 right = get_Add_right(node);
 411                 /* if we can do source address mode then we will never fold the add
 412                  * into address mode */
 413                 if(!mode_is_float(get_irn_mode(node)) && (is_immediate_simple(right) ||
 414                          (!use_source_address_mode(get_nodes_block(node), left, right)
 415                      && !use_source_address_mode(get_nodes_block(node), right, left))))
 416                 {
 417                     break;
 418                 }
 419                 bitset_set(non_address_mode_nodes, get_irn_idx(node));
 420                 /* fallthrough */
 421
 422         default:
 423                 arity = get_irn_arity(node);
 424
 425                 for(i = 0; i < arity; ++i) {
 426                         ir_node *in = get_irn_n(node, i);
 427                         bitset_set(non_address_mode_nodes, get_irn_idx(in));
 428                 }
 429                 break;
 430         }
 431 }
 432
 433 void calculate_non_address_mode_nodes(ir_graph *irg)
 434 {
 435         non_address_mode_nodes = bitset_malloc(get_irg_last_idx(irg));
 436
 437         irg_walk_graph(irg, NULL, mark_non_address_nodes, NULL);
 438 }
 439
 440 void free_non_address_mode_nodes(void)
 441 {
 442         bitset_free(non_address_mode_nodes);
 443 }