nsz Git - libfirm/blob - ir/lower/lower_hl.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   Lower some High-level constructs, moved from the firmlower.
  23  * @author  Boris Boesler, Goetz Lindenmaier, Michael Beck
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "lowering.h"
  29 #include "irmode_t.h"
  30 #include "irnode_t.h"
  31 #include "entity_t.h"
  32 #include "typerep.h"
  33 #include "irprog_t.h"
  34 #include "ircons.h"
  35 #include "irhooks.h"
  36 #include "irgmod.h"
  37 #include "irgwalk.h"
  38 #include "irtools.h"
  39 #include "irpass_t.h"
  40
  41 /**
  42  * Lower a Sel node. Do not touch Sels accessing entities on the frame type.
  43  */
  44 static void lower_sel(ir_node *sel)
  45 {
  46         ir_graph  *irg   = get_irn_irg(sel);
  47         ir_entity *ent   = get_Sel_entity(sel);
  48         ir_type   *owner = get_entity_owner(ent);
  49         dbg_info  *dbg   = get_irn_dbg_info(sel);
  50         ir_mode   *mode  = get_irn_mode(sel);
  51         ir_node   *bl    = get_nodes_block(sel);
  52         ir_node   *newn;
  53
  54         /* we can only replace Sels when the layout of the owner type is decided. */
  55         if (get_type_state(owner) != layout_fixed)
  56                 return;
  57
  58         if (0 < get_Sel_n_indexs(sel)) {
  59                 /* an Array access */
  60                 ir_type *basetyp = get_entity_type(ent);
  61                 ir_mode *basemode;
  62                 ir_node *index;
  63                 if (is_Primitive_type(basetyp))
  64                         basemode = get_type_mode(basetyp);
  65                 else
  66                         basemode = mode_P_data;
  67
  68                 assert(basemode && "no mode for lowering Sel");
  69                 assert((get_mode_size_bits(basemode) % 8 == 0) && "can not deal with unorthodox modes");
  70                 index = get_Sel_index(sel, 0);
  71
  72                 if (is_Array_type(owner)) {
  73                         ir_type *arr_ty = owner;
  74                         size_t   dims   = get_array_n_dimensions(arr_ty);
  75                         size_t  *map    = ALLOCAN(size_t, dims);
  76                         ir_mode *mode_Int = get_reference_mode_signed_eq(mode);
  77                         ir_tarval *tv;
  78                         ir_node *last_size;
  79                         size_t   i;
  80
  81                         assert(dims == (size_t)get_Sel_n_indexs(sel)
  82                                 && "array dimension must match number of indices of Sel node");
  83
  84                         for (i = 0; i < dims; i++) {
  85                                 size_t order = get_array_order(arr_ty, i);
  86
  87                                 assert(order < dims &&
  88                                         "order of a dimension must be smaller than the arrays dim");
  89                                 map[order] = i;
  90                         }
  91                         newn = get_Sel_ptr(sel);
  92
  93                         /* Size of the array element */
  94                         tv = new_tarval_from_long(get_type_size_bytes(basetyp), mode_Int);
  95                         last_size = new_rd_Const(dbg, irg, tv);
  96
  97                         /*
  98                          * We compute the offset part of dimension d_i recursively
  99                          * with the the offset part of dimension d_{i-1}
 100                          *
 101                          *     off_0 = sizeof(array_element_type);
 102                          *     off_i = (u_i - l_i) * off_{i-1}  ; i >= 1
 103                          *
 104                          * whereas u_i is the upper bound of the current dimension
 105                          * and l_i the lower bound of the current dimension.
 106                          */
 107                         for (i = dims; i > 0;) {
 108                                 size_t dim = map[--i];
 109                                 ir_node *lb, *ub, *elms, *n, *ind;
 110
 111                                 elms = NULL;
 112                                 lb = get_array_lower_bound(arr_ty, dim);
 113                                 ub = get_array_upper_bound(arr_ty, dim);
 114
 115                                 assert(irg == current_ir_graph);
 116                                 if (! is_Unknown(lb))
 117                                         lb = new_rd_Conv(dbg, bl, copy_const_value(get_irn_dbg_info(sel), lb, bl), mode_Int);
 118                                 else
 119                                         lb = NULL;
 120
 121                                 if (! is_Unknown(ub))
 122                                         ub = new_rd_Conv(dbg, bl, copy_const_value(get_irn_dbg_info(sel), ub, bl), mode_Int);
 123                                 else
 124                                         ub = NULL;
 125
 126                                 /*
 127                                  * If the array has more than one dimension, lower and upper
 128                                  * bounds have to be set in the non-last dimension.
 129                                  */
 130                                 if (i > 0) {
 131                                         assert(lb != NULL && "lower bound has to be set in multi-dim array");
 132                                         assert(ub != NULL && "upper bound has to be set in multi-dim array");
 133
 134                                         /* Elements in one Dimension */
 135                                         elms = new_rd_Sub(dbg, bl, ub, lb, mode_Int);
 136                                 }
 137
 138                                 ind = new_rd_Conv(dbg, bl, get_Sel_index(sel, dim), mode_Int);
 139
 140                                 /*
 141                                  * Normalize index, id lower bound is set, also assume
 142                                  * lower bound == 0
 143                          */
 144                                 if (lb != NULL)
 145                                         ind = new_rd_Sub(dbg, bl, ind, lb, mode_Int);
 146
 147                                 n = new_rd_Mul(dbg, bl, ind, last_size, mode_Int);
 148
 149                                 /*
 150                                  * see comment above.
 151                                  */
 152                                 if (i > 0)
 153                                         last_size = new_rd_Mul(dbg, bl, last_size, elms, mode_Int);
 154
 155                                 newn = new_rd_Add(dbg, bl, newn, n, mode);
 156                         }
 157                 } else {
 158                         /* no array type */
 159                         ir_mode   *idx_mode = get_irn_mode(index);
 160                         ir_tarval *tv       = new_tarval_from_long(get_mode_size_bytes(basemode), idx_mode);
 161
 162                         newn = new_rd_Add(dbg, bl, get_Sel_ptr(sel),
 163                                 new_rd_Mul(dbg, bl, index,
 164                                 new_r_Const(irg, tv),
 165                                 idx_mode),
 166                                 mode);
 167                 }
 168         } else if (is_Method_type(get_entity_type(ent)) && is_Class_type(owner)) {
 169                 /* We need an additional load when accessing methods from a dispatch
 170                  * table.
 171                  * Matze TODO: Is this really still used? At least liboo does its own
 172                  * lowering of Method-Sels...
 173                  */
 174                 ir_mode   *ent_mode = get_type_mode(get_entity_type(ent));
 175                 int        offset   = get_entity_offset(ent);
 176                 ir_mode   *mode_Int = get_reference_mode_signed_eq(mode);
 177                 ir_tarval *tv       = new_tarval_from_long(offset, mode_Int);
 178                 ir_node   *cnst     = new_rd_Const(dbg, irg, tv);
 179                 ir_node   *add      = new_rd_Add(dbg, bl, get_Sel_ptr(sel), cnst, mode);
 180                 ir_node   *mem      = get_Sel_mem(sel);
 181                 newn = new_rd_Load(dbg, bl, mem, add, ent_mode, cons_none);
 182                 newn = new_r_Proj(newn, ent_mode, pn_Load_res);
 183         } else {
 184                 int offset = get_entity_offset(ent);
 185
 186                 /* replace Sel by add(obj, const(ent.offset)) */
 187                 newn = get_Sel_ptr(sel);
 188                 if (offset != 0) {
 189                         ir_mode   *mode_UInt = get_reference_mode_unsigned_eq(mode);
 190                         ir_tarval *tv        = new_tarval_from_long(offset, mode_UInt);
 191                         ir_node   *cnst      = new_r_Const(irg, tv);
 192                         newn = new_rd_Add(dbg, bl, newn, cnst, mode);
 193                 }
 194         }
 195
 196         /* run the hooks */
 197         hook_lower(sel);
 198
 199         exchange(sel, newn);
 200 }
 201
 202 /**
 203  * Lower a all possible SymConst nodes.
 204  */
 205 static void lower_symconst(ir_node *symc)
 206 {
 207         ir_node       *newn;
 208         ir_type       *tp;
 209         ir_entity     *ent;
 210         ir_tarval     *tv;
 211         ir_enum_const *ec;
 212         ir_mode       *mode;
 213         ir_graph      *irg;
 214
 215         switch (get_SymConst_kind(symc)) {
 216         case symconst_type_tag:
 217                 assert(!"SymConst kind symconst_type_tag not implemented");
 218                 break;
 219         case symconst_type_size:
 220                 /* rewrite the SymConst node by a Const node */
 221                 irg  = get_irn_irg(symc);
 222                 tp   = get_SymConst_type(symc);
 223                 assert(get_type_state(tp) == layout_fixed);
 224                 mode = get_irn_mode(symc);
 225                 newn = new_r_Const_long(irg, mode, get_type_size_bytes(tp));
 226                 assert(newn);
 227                 /* run the hooks */
 228                 hook_lower(symc);
 229                 exchange(symc, newn);
 230                 break;
 231         case symconst_type_align:
 232                 /* rewrite the SymConst node by a Const node */
 233                 irg  = get_irn_irg(symc);
 234                 tp   = get_SymConst_type(symc);
 235                 assert(get_type_state(tp) == layout_fixed);
 236                 mode = get_irn_mode(symc);
 237                 newn = new_r_Const_long(irg, mode, get_type_alignment_bytes(tp));
 238                 assert(newn);
 239                 /* run the hooks */
 240                 hook_lower(symc);
 241                 exchange(symc, newn);
 242                 break;
 243         case symconst_addr_ent:
 244                 /* leave */
 245                 break;
 246         case symconst_ofs_ent:
 247                 /* rewrite the SymConst node by a Const node */
 248                 irg  = get_irn_irg(symc);
 249                 ent  = get_SymConst_entity(symc);
 250                 assert(get_type_state(get_entity_type(ent)) == layout_fixed);
 251                 mode = get_irn_mode(symc);
 252                 newn = new_r_Const_long(irg, mode, get_entity_offset(ent));
 253                 assert(newn);
 254                 /* run the hooks */
 255                 hook_lower(symc);
 256                 exchange(symc, newn);
 257                 break;
 258         case symconst_enum_const:
 259                 /* rewrite the SymConst node by a Const node */
 260                 irg  = get_irn_irg(symc);
 261                 ec   = get_SymConst_enum(symc);
 262                 assert(get_type_state(get_enumeration_owner(ec)) == layout_fixed);
 263                 tv   = get_enumeration_value(ec);
 264                 newn = new_r_Const(irg, tv);
 265                 assert(newn);
 266                 /* run the hooks */
 267                 hook_lower(symc);
 268                 exchange(symc, newn);
 269                 break;
 270
 271         default:
 272                 assert(!"unknown SymConst kind");
 273                 break;
 274         }
 275 }  /* lower_symconst */
 276
 277 /**
 278  * Checks, whether a size is an integral size
 279  *
 280  * @param size  the size on bits
 281  */
 282 static int is_integral_size(int size)
 283 {
 284         /* must be a 2^n */
 285         if (size & (size-1))
 286                 return 0;
 287         /* must be at least byte size */
 288         return size >= 8;
 289 }  /* is_integral_size */
 290
 291 /**
 292  * lower bitfield load access.
 293  *
 294  * @param proj  the Proj(result) node
 295  * @param load  the Load node
 296  */
 297 static void lower_bitfields_loads(ir_node *proj, ir_node *load)
 298 {
 299         ir_node *sel = get_Load_ptr(load);
 300         ir_node *block, *res, *ptr;
 301         ir_graph *irg;
 302         ir_entity *ent;
 303         ir_type *bf_type;
 304         ir_mode *bf_mode, *mode;
 305         int offset, bit_offset, bits, bf_bits, old_cse;
 306         dbg_info *db;
 307
 308         if (!is_Sel(sel))
 309                 return;
 310
 311         ent     = get_Sel_entity(sel);
 312         bf_type = get_entity_type(ent);
 313
 314         /* must be a bitfield type */
 315         if (!is_Primitive_type(bf_type) || get_primitive_base_type(bf_type) == NULL)
 316                 return;
 317
 318         /* We have a bitfield access, if either a bit offset is given, or
 319            the size is not integral. */
 320         bf_mode = get_type_mode(bf_type);
 321         if (! bf_mode)
 322                 return;
 323
 324         mode       = get_irn_mode(proj);
 325         block      = get_nodes_block(proj);
 326         bf_bits    = get_mode_size_bits(bf_mode);
 327         bit_offset = get_entity_offset_bits_remainder(ent);
 328
 329         if (bit_offset == 0 && is_integral_size(bf_bits) && bf_mode == get_Load_mode(load))
 330                 return;
 331
 332         bits   = get_mode_size_bits(mode);
 333         offset = get_entity_offset(ent);
 334
 335         /*
 336          * ok, here we are: now convert the Proj_mode_bf(Load) into And(Shr(Proj_mode(Load)) for unsigned
 337          * and Shr(Shl(Proj_mode(load)) for signed
 338          */
 339
 340         /* abandon bitfield sel */
 341         irg = get_irn_irg(sel);
 342         ptr = get_Sel_ptr(sel);
 343         db  = get_irn_dbg_info(sel);
 344         ptr = new_rd_Add(db, block, ptr, new_r_Const_long(irg, mode_Is, offset), get_irn_mode(ptr));
 345
 346         set_Load_ptr(load, ptr);
 347         set_Load_mode(load, mode);
 348
 349
 350         /* create new proj, switch off CSE or we may get the old one back */
 351         old_cse = get_opt_cse();
 352         set_opt_cse(0);
 353         res = new_r_Proj(load, mode, pn_Load_res);
 354         set_opt_cse(old_cse);
 355
 356         if (mode_is_signed(mode)) { /* signed */
 357                 int shift_count_up    = bits - (bf_bits + bit_offset);
 358                 int shift_count_down  = bits - bf_bits;
 359
 360                 if (shift_count_up) {
 361                         res = new_r_Shl(block, res, new_r_Const_long(irg, mode_Iu, shift_count_up), mode);
 362                 }
 363                 if (shift_count_down) {
 364                         res = new_r_Shrs(block, res, new_r_Const_long(irg, mode_Iu, shift_count_down), mode);
 365                 }
 366         } else { /* unsigned */
 367                 int shift_count_down  = bit_offset;
 368                 unsigned mask = ((unsigned)-1) >> (bits - bf_bits);
 369
 370                 if (shift_count_down) {
 371                         res = new_r_Shr(block, res, new_r_Const_long(irg, mode_Iu, shift_count_down), mode);
 372                 }
 373                 if (bits != bf_bits) {
 374                         res = new_r_And(block, res, new_r_Const_long(irg, mode, mask), mode);
 375                 }
 376         }
 377
 378         exchange(proj, res);
 379 }  /* lower_bitfields_loads */
 380
 381 /**
 382  * lower bitfield store access.
 383  *
 384  * @todo: It adds a load which may produce an exception!
 385  */
 386 static void lower_bitfields_stores(ir_node *store)
 387 {
 388         ir_node   *sel = get_Store_ptr(store);
 389         ir_node   *ptr, *value;
 390         ir_entity *ent;
 391         ir_type *bf_type;
 392         ir_mode *bf_mode, *mode;
 393         ir_node *mem, *irn, *block;
 394         ir_graph *irg;
 395         unsigned mask, neg_mask;
 396         int bf_bits, bits_mask, offset, bit_offset;
 397         dbg_info *db;
 398
 399         /* check bitfield access */
 400         if (!is_Sel(sel))
 401                 return;
 402
 403         ent     = get_Sel_entity(sel);
 404         bf_type = get_entity_type(ent);
 405
 406         /* must be a bitfield type */
 407         if (!is_Primitive_type(bf_type) || get_primitive_base_type(bf_type) == NULL)
 408                 return;
 409
 410         /* We have a bitfield access, if either a bit offset is given, or
 411            the size is not integral. */
 412         bf_mode = get_type_mode(bf_type);
 413         if (! bf_mode)
 414                 return;
 415
 416         value      = get_Store_value(store);
 417         mode       = get_irn_mode(value);
 418         block      = get_nodes_block(store);
 419
 420         bf_bits    = get_mode_size_bits(bf_mode);
 421         bit_offset = get_entity_offset_bits_remainder(ent);
 422
 423         if (bit_offset == 0 && is_integral_size(bf_bits) && bf_mode == get_irn_mode(value))
 424                 return;
 425
 426         /*
 427          * ok, here we are: now convert the Store(Sel(), value) into Or(And(Load(Sel),c), And(Value,c))
 428          */
 429         mem        = get_Store_mem(store);
 430         offset     = get_entity_offset(ent);
 431
 432         bits_mask = get_mode_size_bits(mode) - bf_bits;
 433         mask = ((unsigned)-1) >> bits_mask;
 434         mask <<= bit_offset;
 435         neg_mask = ~mask;
 436
 437         /* abandon bitfield sel */
 438         irg = get_irn_irg(sel);
 439         ptr = get_Sel_ptr(sel);
 440         db  = get_irn_dbg_info(sel);
 441         ptr = new_rd_Add(db, block, ptr, new_r_Const_long(irg, mode_Is, offset), get_irn_mode(ptr));
 442
 443         if (neg_mask) {
 444                 /* there are some bits, normal case */
 445                 irn  = new_r_Load(block, mem, ptr, mode, cons_none);
 446                 mem  = new_r_Proj(irn, mode_M, pn_Load_M);
 447                 irn  = new_r_Proj(irn, mode, pn_Load_res);
 448
 449                 irn = new_r_And(block, irn, new_r_Const_long(irg, mode, neg_mask), mode);
 450
 451                 if (bit_offset > 0) {
 452                         value = new_r_Shl(block, value, new_r_Const_long(irg, mode_Iu, bit_offset), mode);
 453                 }
 454
 455                 value = new_r_And(block, value, new_r_Const_long(irg, mode, mask), mode);
 456
 457                 value = new_r_Or(block, value, irn, mode);
 458         }
 459
 460         set_Store_mem(store, mem);
 461         set_Store_value(store, value);
 462         set_Store_ptr(store, ptr);
 463 }  /* lower_bitfields_stores */
 464
 465 /**
 466  * lowers IR-nodes, called from walker
 467  */
 468 static void lower_irnode(ir_node *irn, void *env)
 469 {
 470         (void) env;
 471         switch (get_irn_opcode(irn)) {
 472         case iro_Sel:
 473                 lower_sel(irn);
 474                 break;
 475         case iro_SymConst:
 476                 lower_symconst(irn);
 477                 break;
 478         case iro_Cast:
 479                 exchange(irn, get_Cast_op(irn));
 480                 break;
 481         default:
 482                 break;
 483         }
 484 }
 485
 486 /**
 487  * Walker: lowers IR-nodes for bitfield access
 488  */
 489 static void lower_bf_access(ir_node *irn, void *env)
 490 {
 491         (void) env;
 492         switch (get_irn_opcode(irn)) {
 493         case iro_Proj:
 494         {
 495                 long proj     = get_Proj_proj(irn);
 496                 ir_node *pred = get_Proj_pred(irn);
 497
 498                 if (proj == pn_Load_res && is_Load(pred))
 499                         lower_bitfields_loads(irn, pred);
 500                 break;
 501         }
 502         case iro_Store:
 503                 lower_bitfields_stores(irn);
 504                 break;
 505
 506         default:
 507                 break;
 508         }
 509 }
 510
 511 /*
 512  * Replaces SymConsts by a real constant if possible.
 513  * Replace Sel nodes by address computation.  Also resolves array access.
 514  * Handle Bitfields by added And/Or calculations.
 515  */
 516 void lower_highlevel_graph(ir_graph *irg, int lower_bitfields)
 517 {
 518         if (lower_bitfields) {
 519                 /* First step: lower bitfield access: must be run as long as Sels still
 520                  * exists. */
 521                 irg_walk_graph(irg, NULL, lower_bf_access, NULL);
 522         }
 523
 524         /* Finally: lower SymConst-Size and Sel nodes, Casts, unaligned Load/Stores. */
 525         irg_walk_graph(irg, NULL, lower_irnode, NULL);
 526 }
 527
 528 typedef struct pass_t {
 529         ir_graph_pass_t pass;
 530         int            lower_bitfields;
 531 } pass_t;
 532
 533 /**
 534  * Wrapper for running lower_highlevel_graph() as an ir_graph pass.
 535  */
 536 static int lower_highlevel_graph_wrapper(ir_graph *irg, void *context)
 537 {
 538         pass_t *pass = (pass_t*)context;
 539
 540         lower_highlevel_graph(irg, pass->lower_bitfields);
 541         return 0;
 542 }  /* lower_highlevel_graph_wrapper */
 543
 544 ir_graph_pass_t *lower_highlevel_graph_pass(const char *name, int lower_bitfields)
 545 {
 546         pass_t *pass = XMALLOCZ(pass_t);
 547
 548         pass->lower_bitfields = lower_bitfields;
 549         return def_graph_pass_constructor(
 550                 &pass->pass, name ? name : "lower_hl", lower_highlevel_graph_wrapper);
 551 }  /* lower_highlevel_graph_pass */
 552
 553 /*
 554  * does the same as lower_highlevel() for all nodes on the const code irg
 555  */
 556 void lower_const_code(void)
 557 {
 558         walk_const_code(NULL, lower_irnode, NULL);
 559 }  /* lower_const_code */
 560
 561 ir_prog_pass_t *lower_const_code_pass(const char *name)
 562 {
 563         return def_prog_pass(name ? name : "lower_const_code", lower_const_code);
 564 }
 565
 566 /*
 567  * Replaces SymConsts by a real constant if possible.
 568  * Replace Sel nodes by address computation.  Also resolves array access.
 569  * Handle Bitfields by added And/Or calculations.
 570  */
 571 void lower_highlevel(int lower_bitfields)
 572 {
 573         size_t i, n;
 574
 575         n = get_irp_n_irgs();
 576         for (i = 0; i < n; ++i) {
 577                 ir_graph *irg = get_irp_irg(i);
 578                 lower_highlevel_graph(irg, lower_bitfields);
 579         }
 580         lower_const_code();
 581 }  /* lower_highlevel */