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