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