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