nsz Git - libfirm/blob - ir/opt/scalar_replace.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Scalar replacement of compounds.
   9  * @author  Beyhan Veliev, Michael Beck
  10  */
  11 #include "config.h"
  12
  13 #include <string.h>
  14 #include <stdbool.h>
  15
  16 #include "iroptimize.h"
  17 #include "scalar_replace.h"
  18 #include "opt_init.h"
  19 #include "irflag_t.h"
  20 #include "irouts.h"
  21 #include "set.h"
  22 #include "pset.h"
  23 #include "array.h"
  24 #include "tv.h"
  25 #include "ircons_t.h"
  26 #include "hashptr.h"
  27 #include "irgwalk.h"
  28 #include "irgmod.h"
  29 #include "irnode_t.h"
  30 #include "irpass.h"
  31 #include "util.h"
  32 #include "xmalloc.h"
  33 #include "debug.h"
  34 #include "error.h"
  35
  36 static unsigned get_vnum(const ir_node *node)
  37 {
  38         return (unsigned)PTR_TO_INT(get_irn_link(node));
  39 }
  40
  41 static void set_vnum(ir_node *node, unsigned vnum)
  42 {
  43         set_irn_link(node, INT_TO_PTR(vnum));
  44 }
  45
  46 /**
  47  * A path element entry: it is either an entity
  48  * or a tarval, because we evaluate only constant array
  49  * accesses like a.b.c[8].d
  50  */
  51 typedef union {
  52         ir_entity *ent;
  53         ir_tarval *tv;
  54 } path_elem_t;
  55
  56 /**
  57  * An access path, used to assign value numbers
  58  * to variables that will be scalar replaced.
  59  */
  60 typedef struct path_t {
  61         unsigned    vnum;      /**< The value number. */
  62         size_t      path_len;  /**< The length of the access path. */
  63         path_elem_t path[1];   /**< The path. */
  64 } path_t;
  65
  66 /** The size of a path in bytes. */
  67 static size_t path_size(path_t *p)
  68 {
  69         return sizeof(*p) + sizeof(p->path[0]) * (p->path_len-1);
  70 }
  71
  72 typedef struct scalars_t {
  73         ir_entity *ent;              /**< A entity for scalar replacement. */
  74 } scalars_t;
  75
  76 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  77
  78 /**
  79  * Compare two pathes.
  80  *
  81  * @return 0 if they are identically
  82  */
  83 static int path_cmp(const void *elt, const void *key, size_t size)
  84 {
  85         const path_t *p1 = (const path_t*)elt;
  86         const path_t *p2 = (const path_t*)key;
  87         (void) size;
  88
  89         /* we can use memcmp here, because identical tarvals should have identical addresses */
  90         return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
  91 }
  92
  93 /**
  94  * Compare two elements of the scalars_t set.
  95  *
  96  * @return 0 if they are identically
  97  */
  98 static int ent_cmp(const void *elt, const void *key, size_t size)
  99 {
 100         const scalars_t *c1 = (const scalars_t*)elt;
 101         const scalars_t *c2 = (const scalars_t*)key;
 102         (void) size;
 103
 104         return c1->ent != c2->ent;
 105 }
 106
 107 /**
 108  * Calculate a hash value for a path.
 109  */
 110 static unsigned path_hash(const path_t *path)
 111 {
 112         unsigned hash = 0;
 113         unsigned i;
 114
 115         for (i = 0; i < path->path_len; ++i)
 116                 hash ^= (unsigned)PTR_TO_INT(path->path[i].ent);
 117
 118         return hash >> 4;
 119 }
 120
 121 /**
 122  * Returns non-zero, if all indeces of a Sel node are constants.
 123  *
 124  * @param sel  the Sel node that will be checked
 125  */
 126 static bool is_const_sel(ir_node *sel)
 127 {
 128         int i, n = get_Sel_n_indexs(sel);
 129
 130         for (i = 0; i < n; ++i) {
 131                 ir_node *idx = get_Sel_index(sel, i);
 132
 133                 if (!is_Const(idx))
 134                         return false;
 135         }
 136         return true;
 137 }
 138
 139 /**
 140  * Check the mode of a Load/Store with the mode of the entity
 141  * that is accessed.
 142  * If the mode of the entity and the Load/Store mode do not match, we
 143  * have the bad reinterpret case:
 144  *
 145  * int i;
 146  * char b = *(char *)&i;
 147  *
 148  * We do NOT count this as one value and return address_taken
 149  * in that case.
 150  * However, we support an often used case. If the mode is two-complement
 151  * we allow casts between signed/unsigned.
 152  *
 153  * @param mode     the mode of the Load/Store
 154  * @param ent_mode the mode of the accessed entity
 155  */
 156 static bool check_load_store_mode(ir_mode *mode, ir_mode *ent_mode)
 157 {
 158         if (ent_mode != mode) {
 159                 if (ent_mode == NULL ||
 160                     get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
 161                     get_mode_arithmetic(ent_mode) != irma_twos_complement ||
 162                     get_mode_arithmetic(mode) != irma_twos_complement)
 163                         return false;
 164         }
 165         return true;
 166 }
 167
 168 /*
 169  * Returns non-zero, if the address of an entity
 170  * represented by a Sel node (or its successor Sels) is taken.
 171  */
 172 bool is_address_taken(ir_node *sel)
 173 {
 174         int       input_nr;
 175         ir_mode   *emode, *mode;
 176         ir_node   *value;
 177         ir_entity *ent;
 178
 179         if (! is_const_sel(sel))
 180                 return true;
 181
 182         for (unsigned i = get_irn_n_outs(sel); i-- > 0; ) {
 183                 ir_node *succ = get_irn_out(sel, i);
 184
 185                 switch (get_irn_opcode(succ)) {
 186                 case iro_Load:
 187                         /* do not remove volatile variables */
 188                         if (get_Load_volatility(succ) == volatility_is_volatile)
 189                                 return true;
 190                         /* check if this load is not a hidden conversion */
 191                         mode = get_Load_mode(succ);
 192                         ent = get_Sel_entity(sel);
 193                         emode = get_type_mode(get_entity_type(ent));
 194                         if (! check_load_store_mode(mode, emode))
 195                                 return true;
 196                         break;
 197
 198                 case iro_Store:
 199                         /* check that Sel is not the Store's value */
 200                         value = get_Store_value(succ);
 201                         if (value == sel)
 202                                 return true;
 203                         /* do not remove volatile variables */
 204                         if (get_Store_volatility(succ) == volatility_is_volatile)
 205                                 return true;
 206                         /* check if this Store is not a hidden conversion */
 207                         mode = get_irn_mode(value);
 208                         ent = get_Sel_entity(sel);
 209                         emode = get_type_mode(get_entity_type(ent));
 210                         if (! check_load_store_mode(mode, emode))
 211                                 return true;
 212                         break;
 213
 214                 case iro_Sel: {
 215                         int       res;
 216                         ir_entity *entity = get_Sel_entity(succ);
 217                         /* we can't handle unions correctly yet -> address taken */
 218                         if (is_Union_type(get_entity_owner(entity)))
 219                                 return true;
 220
 221                         /* Check the Sel successor of Sel */
 222                         res = is_address_taken(succ);
 223                         if (res)
 224                                 return true;
 225                         break;
 226                 }
 227
 228                 case iro_Call:
 229                         /* The address of an entity is given as a parameter.
 230                          * As long as we do not have analyses that can tell what
 231                          * is done with parameters, think is taken.
 232                          * One special case: If the Call type tells that it's a
 233                          * value parameter, the address is NOT taken.
 234                          */
 235                         return true;
 236
 237                 case iro_Id: {
 238                         int res = is_address_taken(succ);
 239                         if (res)
 240                                 return true;
 241                         break;
 242                 }
 243
 244                 case iro_Tuple:
 245                         /* Non-optimized Tuple, happens in inlining */
 246                         for (input_nr = get_Tuple_n_preds(succ) - 1; input_nr >= 0; --input_nr) {
 247                                 ir_node *pred = get_Tuple_pred(succ, input_nr);
 248
 249                                 if (pred == sel) {
 250                                         /* we found one input */
 251                                         for (unsigned k = get_irn_n_outs(succ); k-- > 0; ) {
 252                                                 ir_node *proj = get_irn_out(succ, k);
 253
 254                                                 if (is_Proj(proj) && get_Proj_proj(proj) == input_nr) {
 255                                                         int res = is_address_taken(proj);
 256                                                         if (res)
 257                                                                 return true;
 258                                                 }
 259                                         }
 260                                 }
 261                         }
 262                         break;
 263
 264                 default:
 265                         /* another op, the address is taken */
 266                         return true;
 267                 }
 268         }
 269         return false;
 270 }
 271
 272 /**
 273  * Link all leave Sels with the entity.
 274  *
 275  * @param ent  the entity that will be scalar replaced
 276  * @param sel  a Sel node that selects some fields of this entity
 277  */
 278 static bool link_all_leave_sels(ir_entity *ent, ir_node *sel)
 279 {
 280         bool is_leave = true;
 281
 282         for (unsigned i = get_irn_n_outs(sel); i-- > 0; ) {
 283                 ir_node *succ = get_irn_out(sel, i);
 284
 285                 if (is_Sel(succ)) {
 286                         /* the current leave has further Sel's, no leave */
 287                         is_leave = false;
 288                         link_all_leave_sels(ent, succ);
 289                 } else if (is_Id(succ)) {
 290                         is_leave &= link_all_leave_sels(ent, succ);
 291                 }
 292         }
 293
 294         if (is_leave) {
 295                 /* beware of Id's */
 296                 sel = skip_Id(sel);
 297
 298                 /* we know we are at a leave, because this function is only
 299                  * called if the address is NOT taken, so sel's successor(s)
 300                  * must be Loads or Stores
 301                  */
 302                 set_irn_link(sel, get_entity_link(ent));
 303                 set_entity_link(ent, sel);
 304         }
 305         return is_leave;
 306 }
 307
 308 /* we need a special address that serves as an address taken marker */
 309 static char _x;
 310 static void *ADDRESS_TAKEN = &_x;
 311
 312 /**
 313  * Find possible scalar replacements.
 314  *
 315  * @param irg  an IR graph
 316  *
 317  * This function finds variables on the (members of the) frame type
 318  * that can be scalar replaced, because their address is never taken.
 319  * If such a variable is found, its entity link will hold a list of all
 320  * Sel nodes, that selects the atomic fields of this entity.
 321  * Otherwise, the link will be ADDRESS_TAKEN or NULL.
 322  *
 323  * @return  non-zero if at least one entity could be replaced
 324  *          potentially
 325  */
 326 static int find_possible_replacements(ir_graph *irg)
 327 {
 328         ir_node *irg_frame;
 329         ir_type *frame_tp;
 330         size_t  mem_idx;
 331         long    static_link_arg;
 332         int     res = 0;
 333
 334         /*
 335          * First, clear the link field of all interesting entities.
 336          */
 337         frame_tp = get_irg_frame_type(irg);
 338         for (mem_idx = get_class_n_members(frame_tp); mem_idx > 0;) {
 339                 ir_entity *ent = get_class_member(frame_tp, --mem_idx);
 340                 set_entity_link(ent, NULL);
 341         }
 342
 343         /* check for inner functions:
 344          * FIXME: need a way to get the argument position for the static link */
 345         static_link_arg = 0;
 346         for (mem_idx = get_class_n_members(frame_tp); mem_idx > 0;) {
 347                 ir_entity *ent = get_class_member(frame_tp, --mem_idx);
 348                 if (is_method_entity(ent)) {
 349                         ir_graph *inner_irg = get_entity_irg(ent);
 350                         ir_node  *args;
 351
 352                         assure_irg_properties(inner_irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS);
 353                         args = get_irg_args(inner_irg);
 354                         for (unsigned j = get_irn_n_outs(args); j-- > 0; ) {
 355                                 ir_node *arg = get_irn_out(args, j);
 356
 357                                 if (get_Proj_proj(arg) == static_link_arg) {
 358                                         for (unsigned k = get_irn_n_outs(arg); k-- > 0; ) {
 359                                                 ir_node *succ = get_irn_out(arg, k);
 360
 361                                                 if (is_Sel(succ)) {
 362                                                         ir_entity *ent = get_Sel_entity(succ);
 363
 364                                                         if (get_entity_owner(ent) == frame_tp) {
 365                                                                 /* found an access to the outer frame */
 366                                                                 set_entity_link(ent, ADDRESS_TAKEN);
 367                                                         }
 368                                                 }
 369                                         }
 370                                 }
 371                         }
 372                 }
 373         }
 374
 375         /*
 376          * Check the ir_graph for Sel nodes. If the entity of Sel
 377          * isn't a scalar replacement set the link of this entity
 378          * equal ADDRESS_TAKEN.
 379          */
 380         irg_frame = get_irg_frame(irg);
 381         for (unsigned i = get_irn_n_outs(irg_frame); i-- > 0; ) {
 382                 ir_node *succ = get_irn_out(irg_frame, i);
 383
 384                 if (is_Sel(succ)) {
 385                         ir_entity *ent = get_Sel_entity(succ);
 386                         ir_type *ent_type;
 387
 388                         /* we are only interested in entities on the frame, NOT
 389                            on the value type */
 390                         if (get_entity_owner(ent) != frame_tp)
 391                                 continue;
 392
 393                         if (get_entity_link(ent) == ADDRESS_TAKEN)
 394                                 continue;
 395
 396                         ent_type = get_entity_type(ent);
 397
 398                         /* we can handle arrays, structs and atomic types yet */
 399                         if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
 400                                 if (is_address_taken(succ)) {
 401                                          /* killing one */
 402                                         if (get_entity_link(ent))
 403                                                 --res;
 404                                         set_entity_link(ent, ADDRESS_TAKEN);
 405                                 } else {
 406                                         /* possible found one */
 407                                         if (get_entity_link(ent) == NULL)
 408                                                 ++res;
 409                                         link_all_leave_sels(ent, succ);
 410                                 }
 411                         }
 412                 }
 413         }
 414
 415         return res;
 416 }
 417
 418 /**
 419  * Return a path from the Sel node "sel" to its root.
 420  *
 421  * @param sel  the Sel node
 422  * @param len  the length of the path so far
 423  */
 424 static path_t *find_path(ir_node *sel, size_t len)
 425 {
 426         size_t pos;
 427         int i, n;
 428         path_t *res;
 429         ir_node *pred = get_Sel_ptr(sel);
 430
 431         /* the current Sel node will add some path elements */
 432         n    = get_Sel_n_indexs(sel);
 433         len += n + 1;
 434
 435         if (! is_Sel(pred)) {
 436                 /* we found the root */
 437                 res = XMALLOCF(path_t, path, len);
 438                 res->path_len = len;
 439         } else
 440                 res = find_path(pred, len);
 441
 442         assert(len <= res->path_len);
 443         pos = res->path_len - len;
 444
 445         res->path[pos++].ent = get_Sel_entity(sel);
 446         for (i = 0; i < n; ++i) {
 447                 ir_node *index = get_Sel_index(sel, i);
 448
 449                 res->path[pos++].tv = get_Const_tarval(index);
 450         }
 451         return res;
 452 }
 453
 454
 455 /**
 456  * Allocate value numbers for the leaves
 457  * in our found entities.
 458  *
 459  * @param sels  a set that will contain all Sels that have a value number
 460  * @param ent   the entity that will be scalar replaced
 461  * @param vnum  the first value number we can assign
 462  * @param modes a flexible array, containing all the modes of
 463  *              the value numbers.
 464  *
 465  * @return the next free value number
 466  */
 467 static unsigned allocate_value_numbers(pset *sels, ir_entity *ent, unsigned vnum, ir_mode ***modes)
 468 {
 469         ir_node *sel, *next;
 470         path_t *key, *path;
 471         set *pathes = new_set(path_cmp, 8);
 472
 473         DB((dbg, SET_LEVEL_3, "  Visiting Sel nodes of entity %+F\n", ent));
 474         /* visit all Sel nodes in the chain of the entity */
 475         for (sel = (ir_node*)get_entity_link(ent); sel != NULL; sel = next) {
 476                 next = (ir_node*)get_irn_link(sel);
 477
 478                 /* we must mark this sel for later */
 479                 pset_insert_ptr(sels, sel);
 480
 481                 key  = find_path(sel, 0);
 482                 path = set_find(path_t, pathes, key, path_size(key), path_hash(key));
 483
 484                 if (path) {
 485                         set_vnum(sel, path->vnum);
 486                         DB((dbg, SET_LEVEL_3, "  %+F represents value %u\n", sel, path->vnum));
 487                 } else {
 488                         key->vnum = vnum++;
 489
 490                         (void)set_insert(path_t, pathes, key, path_size(key), path_hash(key));
 491
 492                         set_vnum(sel, key->vnum);
 493                         DB((dbg, SET_LEVEL_3, "  %+F represents value %u\n", sel, key->vnum));
 494
 495                         ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15);
 496
 497                         (*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel)));
 498
 499                         assert((*modes)[key->vnum] && "Value is not atomic");
 500
 501 #ifdef DEBUG_libfirm
 502                         /* Debug output */
 503                         {
 504                                 unsigned i;
 505                                 DB((dbg, SET_LEVEL_2, "  %s", get_entity_name(key->path[0].ent)));
 506                                 for (i = 1; i < key->path_len; ++i) {
 507                                         if (is_entity(key->path[i].ent))
 508                                                 DB((dbg, SET_LEVEL_2, ".%s", get_entity_name(key->path[i].ent)));
 509                                         else
 510                                                 DB((dbg, SET_LEVEL_2, "[%ld]", get_tarval_long(key->path[i].tv)));
 511                                 }
 512                                 DB((dbg, SET_LEVEL_2, " = %u (%s)\n", PTR_TO_INT(get_irn_link(sel)), get_mode_name((*modes)[key->vnum])));
 513                         }
 514 #endif /* DEBUG_libfirm */
 515                 }
 516                 free(key);
 517         }
 518
 519         del_set(pathes);
 520         set_entity_link(ent, NULL);
 521         return vnum;
 522 }
 523
 524 /**
 525  * environment for memory walker
 526  */
 527 typedef struct env_t {
 528         unsigned nvals;      /**< number of values */
 529         ir_mode  **modes;    /**< the modes of the values */
 530         pset     *sels;      /**< A set of all Sel nodes that have a value number */
 531 } env_t;
 532
 533 /**
 534  * topological post-walker.
 535  */
 536 static void walker(ir_node *node, void *ctx)
 537 {
 538         env_t    *env = (env_t*)ctx;
 539         ir_graph *irg = get_irn_irg(node);
 540         ir_node  *addr, *block, *mem, *val;
 541         ir_mode  *mode;
 542         unsigned vnum;
 543
 544         if (is_Load(node)) {
 545                 /* a load, check if we can resolve it */
 546                 addr = get_Load_ptr(node);
 547
 548                 DB((dbg, SET_LEVEL_3, "  checking %+F for replacement ", node));
 549                 if (! is_Sel(addr)) {
 550                         DB((dbg, SET_LEVEL_3, "no Sel input (%+F)\n", addr));
 551                         return;
 552                 }
 553
 554                 if (! pset_find_ptr(env->sels, addr)) {
 555                         DB((dbg, SET_LEVEL_3, "Sel %+F has no VNUM\n", addr));
 556                         return;
 557                 }
 558
 559                 /* ok, we have a Load that will be replaced */
 560                 vnum = get_vnum(addr);
 561                 assert(vnum < env->nvals);
 562
 563                 DB((dbg, SET_LEVEL_3, "replacing by value %u\n", vnum));
 564
 565                 block = get_nodes_block(node);
 566                 set_cur_block(block);
 567
 568                 /* check, if we can replace this Load */
 569                 val = get_value(vnum, env->modes[vnum]);
 570
 571                 /* Beware: A Load can contain a hidden conversion in Firm.
 572                 This happens for instance in the following code:
 573
 574                  int i;
 575                  unsigned j = *(unsigned *)&i;
 576
 577                 Handle this here. */
 578                 mode = get_Load_mode(node);
 579                 if (mode != get_irn_mode(val))
 580                         val = new_rd_Conv(get_irn_dbg_info(node), block, val, mode);
 581
 582                 mem = get_Load_mem(node);
 583                 ir_node *const in[] = {
 584                         [pn_Load_M]         = mem,
 585                         [pn_Load_res]       = val,
 586                         [pn_Load_X_regular] = new_r_Jmp(block),
 587                         [pn_Load_X_except]  = new_r_Bad(irg, mode_X),
 588                 };
 589                 turn_into_tuple(node, ARRAY_SIZE(in), in);
 590         } else if (is_Store(node)) {
 591                 DB((dbg, SET_LEVEL_3, "  checking %+F for replacement ", node));
 592
 593                 /* a Store always can be replaced */
 594                 addr = get_Store_ptr(node);
 595
 596                 if (! is_Sel(addr)) {
 597                         DB((dbg, SET_LEVEL_3, "no Sel input (%+F)\n", addr));
 598                         return;
 599                 }
 600
 601                 if (! pset_find_ptr(env->sels, addr)) {
 602                         DB((dbg, SET_LEVEL_3, "Sel %+F has no VNUM\n", addr));
 603                         return;
 604                 }
 605
 606                 vnum = get_vnum(addr);
 607                 assert(vnum < env->nvals);
 608
 609                 DB((dbg, SET_LEVEL_3, "replacing by value %u\n", vnum));
 610
 611                 block = get_nodes_block(node);
 612                 set_cur_block(block);
 613
 614                 /* Beware: A Store can contain a hidden conversion in Firm. */
 615                 val = get_Store_value(node);
 616                 if (get_irn_mode(val) != env->modes[vnum])
 617                         val = new_rd_Conv(get_irn_dbg_info(node), block, val, env->modes[vnum]);
 618
 619                 set_value(vnum, val);
 620
 621                 mem = get_Store_mem(node);
 622                 ir_node *const in[] = {
 623                         [pn_Store_M]         = mem,
 624                         [pn_Store_X_regular] = new_r_Jmp(block),
 625                         [pn_Store_X_except]  = new_r_Bad(irg, mode_X),
 626                 };
 627                 turn_into_tuple(node, ARRAY_SIZE(in), in);
 628         }
 629 }
 630
 631 /**
 632  * Make scalar replacement.
 633  *
 634  * @param sels    A set containing all Sel nodes that have a value number
 635  * @param nvals   The number of scalars.
 636  * @param modes   A flexible array, containing all the modes of
 637  *                the value numbers.
 638  */
 639 static void do_scalar_replacements(ir_graph *irg, pset *sels, unsigned nvals,
 640                                    ir_mode **modes)
 641 {
 642         env_t env;
 643
 644         ssa_cons_start(irg, (int)nvals);
 645
 646         env.nvals = nvals;
 647         env.modes = modes;
 648         env.sels  = sels;
 649
 650         /*
 651          * second step: walk over the graph blockwise in topological order
 652          * and fill the array as much as possible.
 653          */
 654         DB((dbg, SET_LEVEL_3, "Substituting Loads and Stores in %+F\n", irg));
 655         irg_walk_blkwise_graph(irg, NULL, walker, &env);
 656
 657         ssa_cons_finish(irg);
 658 }
 659
 660 /*
 661  * Find possible scalar replacements
 662  *
 663  * @param irg  The current ir graph.
 664  */
 665 void scalar_replacement_opt(ir_graph *irg)
 666 {
 667         unsigned  nvals;
 668         scalars_t key;
 669         ir_node   *irg_frame;
 670         ir_mode   **modes;
 671         set       *set_ent;
 672         pset      *sels;
 673         ir_type   *ent_type, *frame_tp;
 674
 675         assure_irg_properties(irg,
 676                 IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
 677                 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS);
 678
 679         /* we use the link field to store the VNUM */
 680         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 681         irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
 682
 683         /* Find possible scalar replacements */
 684         if (find_possible_replacements(irg)) {
 685                 DB((dbg, SET_LEVEL_1, "Scalar Replacement: %+F\n", irg));
 686
 687                 /* Insert in set the scalar replacements. */
 688                 irg_frame = get_irg_frame(irg);
 689                 nvals     = 0;
 690                 modes     = NEW_ARR_F(ir_mode *, 16);
 691                 set_ent   = new_set(ent_cmp, 8);
 692                 sels      = pset_new_ptr(8);
 693                 frame_tp  = get_irg_frame_type(irg);
 694
 695                 for (unsigned i = get_irn_n_outs(irg_frame); i-- > 0; ) {
 696                         ir_node *succ = get_irn_out(irg_frame, i);
 697
 698                         if (is_Sel(succ)) {
 699                                 ir_entity *ent = get_Sel_entity(succ);
 700
 701                                 /* we are only interested in entities on the frame, NOT
 702                                    parameters */
 703                                 if (get_entity_owner(ent) != frame_tp
 704                                     || is_parameter_entity(ent))
 705                                         continue;
 706
 707                                 if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
 708                                         continue;
 709
 710                                 ent_type = get_entity_type(ent);
 711
 712                                 key.ent       = ent;
 713                                 (void)set_insert(scalars_t, set_ent, &key, sizeof(key), hash_ptr(key.ent));
 714
 715 #ifdef DEBUG_libfirm
 716                                 if (is_Array_type(ent_type)) {
 717                                         DB((dbg, SET_LEVEL_1, "  found array %s\n", get_entity_name(ent)));
 718                                 } else if (is_Struct_type(ent_type)) {
 719                                         DB((dbg, SET_LEVEL_1, "  found struct %s\n", get_entity_name(ent)));
 720                                 } else if (is_atomic_type(ent_type))
 721                                         DB((dbg, SET_LEVEL_1, "  found atomic value %s\n", get_entity_name(ent)));
 722                                 else {
 723                                         panic("Neither an array nor a struct or atomic value found in scalar replace");
 724                                 }
 725 #endif /* DEBUG_libfirm */
 726
 727                                 nvals = allocate_value_numbers(sels, ent, nvals, &modes);
 728                         }
 729                 }
 730
 731                 DB((dbg, SET_LEVEL_1, "  %u values will be needed\n", nvals));
 732
 733                 /* If scalars were found. */
 734                 if (nvals > 0) {
 735                         do_scalar_replacements(irg, sels, nvals, modes);
 736
 737                         foreach_set(set_ent, scalars_t, value) {
 738                                 free_entity(value->ent);
 739                         }
 740
 741                         /*
 742                          * We changed the graph, but did NOT introduce new blocks
 743                          * neither changed control flow, cf-backedges should be still
 744                          * consistent.
 745                          */
 746                 }
 747                 del_pset(sels);
 748                 del_set(set_ent);
 749                 DEL_ARR_F(modes);
 750         }
 751
 752         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 753         irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
 754
 755         confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
 756 }
 757
 758 ir_graph_pass_t *scalar_replacement_opt_pass(const char *name)
 759 {
 760         return def_graph_pass(name ? name : "scalar_rep", scalar_replacement_opt);
 761 }
 762
 763 void firm_init_scalar_replace(void)
 764 {
 765         FIRM_DBG_REGISTER(dbg, "firm.opt.scalar_replace");
 766 }