nsz Git - libfirm/blob - ir/opt/scalar_replace.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   Scalar replacement of compounds.
  23  * @author  Beyhan Veliev, Michael Beck
  24  * @version $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include <string.h>
  31
  32 #include "iroptimize.h"
  33 #include "scalar_replace.h"
  34 #include "irflag_t.h"
  35 #include "irouts.h"
  36 #include "set.h"
  37 #include "pset.h"
  38 #include "array.h"
  39 #include "tv.h"
  40 #include "ircons_t.h"
  41 #include "hashptr.h"
  42 #include "irgwalk.h"
  43 #include "irgmod.h"
  44 #include "irnode_t.h"
  45 #include "irtools.h"
  46 #include "xmalloc.h"
  47
  48 #define SET_VNUM(node, vnum) set_irn_link(node, INT_TO_PTR(vnum))
  49 #define GET_VNUM(node)       (unsigned)PTR_TO_INT(get_irn_link(node))
  50
  51 /**
  52  * A path element entry: it is either an entity
  53  * or a tarval, because we evaluate only constant array
  54  * accesses like a.b.c[8].d
  55  */
  56 typedef union {
  57         ir_entity *ent;
  58         tarval *tv;
  59 } path_elem_t;
  60
  61 /**
  62  * An access path, used to assign value numbers
  63  * to variables that will be scalar replaced.
  64  */
  65 typedef struct _path_t {
  66         unsigned    vnum;      /**< The value number. */
  67         unsigned    path_len;  /**< The length of the access path. */
  68         path_elem_t path[1];   /**< The path. */
  69 } path_t;
  70
  71 /** The size of a path in bytes. */
  72 #define PATH_SIZE(p)  (sizeof(*(p)) + sizeof((p)->path[0]) * ((p)->path_len - 1))
  73
  74 typedef struct _scalars_t {
  75         ir_entity *ent;              /**< A entity for scalar replacement. */
  76         ir_type *ent_owner;          /**< The owner of this entity. */
  77 } scalars_t;
  78
  79
  80 /**
  81  * Compare two pathes.
  82  *
  83  * @return 0 if they are identically
  84  */
  85 static int path_cmp(const void *elt, const void *key, size_t size) {
  86         const path_t *p1 = elt;
  87         const path_t *p2 = key;
  88         (void) size;
  89
  90         /* we can use memcmp here, because identical tarvals should have identical addresses */
  91         return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
  92 }
  93
  94 /**
  95  * Compare two elements of the scalars_t set.
  96  *
  97  * @return 0 if they are identically
  98  */
  99 static int ent_cmp(const void *elt, const void *key, size_t size) {
 100         const scalars_t *c1 = elt;
 101         const scalars_t *c2 = 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         unsigned hash = 0;
 112         unsigned i;
 113
 114         for (i = 0; i < path->path_len; ++i)
 115                 hash ^= (unsigned)PTR_TO_INT(path->path[i].ent);
 116
 117         return hash >> 4;
 118 }
 119
 120 /**
 121  * Returns non-zero, if all indeces of a Sel node are constants.
 122  *
 123  * @param sel  the Sel node that will be checked
 124  */
 125 static int is_const_sel(ir_node *sel) {
 126         int i, n = get_Sel_n_indexs(sel);
 127
 128         for (i = 0; i < n; ++i) {
 129                 ir_node *idx = get_Sel_index(sel, i);
 130
 131                 if (get_irn_op(idx) != op_Const)
 132                         return 0;
 133         }
 134         return 1;
 135 }
 136
 137 /**
 138  * Check the mode of a Load/Store with the mode of the entity
 139  * that is accessed.
 140  * If the mode of the entity and the Load/Store mode do not match, we
 141  * have the bad reinterpret case:
 142  *
 143  * int i;
 144  * char b = *(char *)&i;
 145  *
 146  * We do NOT count this as one value and return address_taken
 147  * in that case.
 148  * However, we support an often used case. If the mode is two-complement
 149  * we allow casts between signed/unsigned.
 150  *
 151  * @param mode     the mode of the Load/Store
 152  * @param ent_mode the mode of the accessed entity
 153  */
 154 static int check_load_store_mode(ir_mode *mode, ir_mode *ent_mode) {
 155         if (ent_mode != mode) {
 156                 if (ent_mode == NULL ||
 157                     get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
 158                     get_mode_sort(ent_mode) != get_mode_sort(mode) ||
 159                     get_mode_arithmetic(ent_mode) != irma_twos_complement ||
 160                     get_mode_arithmetic(mode) != irma_twos_complement)
 161                         return 0;
 162         }
 163         return 1;
 164 }
 165
 166 /*
 167  * Returns non-zero, if the address of an entity
 168  * represented by a Sel node (or it's successor Sels) is taken.
 169  */
 170 int is_address_taken(ir_node *sel)
 171 {
 172         int     i;
 173         ir_mode *emode, *mode;
 174         ir_node *value;
 175         ir_entity *ent;
 176
 177         if (! is_const_sel(sel))
 178                 return 1;
 179
 180         for (i = get_irn_n_outs(sel) - 1; i >= 0; --i) {
 181                 ir_node *succ = get_irn_out(sel, i);
 182
 183                 switch (get_irn_opcode(succ)) {
 184                 case iro_Load:
 185                         /* check if this load is not a hidden conversion */
 186                         mode = get_Load_mode(succ);
 187                         ent = get_Sel_entity(sel);
 188                         emode = get_type_mode(get_entity_type(ent));
 189                         if (! check_load_store_mode(mode, emode))
 190                                 return 1;
 191                         /* do not remove volatile variables */
 192                         if (get_Load_volatility(succ) == volatility_is_volatile)
 193                                 return 1;
 194                         break;
 195
 196                 case iro_Store:
 197                         /* check that Sel is not the Store's value */
 198                         value = get_Store_value(succ);
 199                         if (value == sel)
 200                                 return 1;
 201                         /* check if this Store is not a hidden conversion */
 202                         mode = get_irn_mode(value);
 203                         ent = get_Sel_entity(sel);
 204                         emode = get_type_mode(get_entity_type(ent));
 205                         if (! check_load_store_mode(mode, emode))
 206                                 return 1;
 207                         /* do not remove volatile variables */
 208                         if (get_Store_volatility(succ) == volatility_is_volatile)
 209                                 return 1;
 210                         break;
 211
 212                 case iro_Sel: {
 213                         /* Check the Sel successor of Sel */
 214                         int res = is_address_taken(succ);
 215
 216                         if (res)
 217                                 return 1;
 218                         break;
 219                 }
 220
 221                 case iro_Call:
 222                         /* The address of an entity is given as a parameter.
 223                          * As long as we do not have analyses that can tell what
 224                          * is done with parameters, think is taken.
 225                          * One special case: If the Call type tells that it's a
 226                          * value parameter, the address is NOT taken.
 227                          */
 228                         return 1;
 229
 230                 default:
 231                         /* another op, the address is taken */
 232                         return 1;
 233                 }
 234         }
 235         return 0;
 236 }
 237
 238 /**
 239  * Link all leave Sels with the entity.
 240  *
 241  * @param ent  the entity that will be scalar replaced
 242  * @param sel  a Sel node that selects some fields of this entity
 243  */
 244 static void link_all_leave_sels(ir_entity *ent, ir_node *sel) {
 245         int i, n, flag = 1;
 246
 247         n = get_irn_n_outs(sel);
 248         for (i = 0; i < n; ++i) {
 249                 ir_node *succ = get_irn_out(sel, i);
 250
 251                 if (is_Sel(succ)) {
 252                         link_all_leave_sels(ent, succ);
 253                         flag = 0;
 254                 }
 255         }
 256
 257         if (flag) {
 258                 /* if Sel nodes with memory inputs are used, a entity can be
 259                  * visited more than once causing a ring here, so we use the
 260                  * node flag to mark linked nodes
 261                  */
 262                 if (irn_visited(sel))
 263                         return;
 264
 265                 /* we know we are at a leave, because this function is only
 266                  * called if the address is NOT taken, so succ must be a Load
 267                  * or a Store node
 268                  */
 269                 set_irn_link(sel, get_entity_link(ent));
 270                 set_entity_link(ent, sel);
 271
 272                 mark_irn_visited(sel);
 273         }
 274 }
 275
 276 /* we need a special address that serves as an address taken marker */
 277 static char _x;
 278 static void *ADDRESS_TAKEN = &_x;
 279
 280 /**
 281  * Find possible scalar replacements.
 282  *
 283  * @param irg  an IR graph
 284  *
 285  * This function finds variables on the (members of the) frame type
 286  * that can be scalar replaced, because their address is never taken.
 287  * If such a variable is found, it's entity link will hold a list of all
 288  * Sel nodes, that selects the atomic fields of this entity.
 289  * Otherwise, the link will be ADDRESS_TAKEN or NULL.
 290  *
 291  * @return  non-zero if at least one entity could be replaced
 292  *          potentially
 293  */
 294 static int find_possible_replacements(ir_graph *irg) {
 295         ir_node *irg_frame = get_irg_frame(irg);
 296         int i, n;
 297         int res = 0;
 298
 299         inc_irg_visited(irg);
 300
 301         n = get_irn_n_outs(irg_frame);
 302
 303         /*
 304          * First, clear the link field of all interesting entities.
 305          * Note that we did not rely on the fact that there is only
 306          * one Sel node per entity, so we might access one entity
 307          * more than once here.
 308          * That's why we have need two loops.
 309          */
 310         for (i = 0; i < n; ++i) {
 311                 ir_node *succ = get_irn_out(irg_frame, i);
 312
 313                 if (is_Sel(succ)) {
 314                         ir_entity *ent = get_Sel_entity(succ);
 315                         set_entity_link(ent, NULL);
 316                 }
 317         }
 318
 319         /*
 320          * Check the ir_graph for Sel nodes. If the entity of Sel
 321          * isn't a scalar replacement set the link of this entity
 322          * equal ADDRESS_TAKEN.
 323          */
 324         for (i = 0; i < n; ++i) {
 325                 ir_node *succ = get_irn_out(irg_frame, i);
 326
 327                 if (is_Sel(succ)) {
 328                         ir_entity *ent = get_Sel_entity(succ);
 329                         ir_type *ent_type;
 330
 331                         if (get_entity_link(ent) == ADDRESS_TAKEN)
 332                                 continue;
 333
 334                         /*
 335                          * Beware: in rare cases even entities on the frame might be
 336                          * volatile. This might happen if the entity serves as a store
 337                          * to a value that must survive a exception. Do not optimize
 338                          * such entities away.
 339                          */
 340                         if (get_entity_volatility(ent) == volatility_is_volatile) {
 341                                 set_entity_link(ent, ADDRESS_TAKEN);
 342                                 continue;
 343                         }
 344
 345                         ent_type = get_entity_type(ent);
 346
 347                         /* we can handle arrays, structs and atomic types yet */
 348                         if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
 349                                 if (is_address_taken(succ)) {
 350                                         if (get_entity_link(ent)) /* killing one */
 351                                                 --res;
 352                                         set_entity_link(ent, ADDRESS_TAKEN);
 353                                 } else {
 354                                         /* possible found one */
 355                                         if (get_entity_link(ent) == NULL)
 356                                                 ++res;
 357                                         link_all_leave_sels(ent, succ);
 358                                 }
 359                         }
 360                 }
 361         }
 362
 363         return res;
 364 }
 365
 366 /**
 367  * Return a path from the Sel node sel to it's root.
 368  *
 369  * @param sel  the Sel node
 370  * @param len  the length of the path so far
 371  */
 372 static path_t *find_path(ir_node *sel, unsigned len) {
 373         int pos, i, n;
 374         path_t *res;
 375         ir_node *pred = get_Sel_ptr(sel);
 376
 377         /* the current Sel node will add some path elements */
 378         n    = get_Sel_n_indexs(sel);
 379         len += n + 1;
 380
 381         if (! is_Sel(pred)) {
 382                 /* we found the root */
 383
 384                 res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
 385                 res->path_len = len;
 386         } else
 387                 res = find_path(pred, len);
 388
 389         pos = res->path_len - len;
 390
 391         res->path[pos++].ent = get_Sel_entity(sel);
 392         for (i = 0; i < n; ++i) {
 393                 ir_node *index = get_Sel_index(sel, i);
 394
 395                 res->path[pos++].tv = get_Const_tarval(index);
 396         }
 397         return res;
 398 }
 399
 400
 401 /**
 402  * Allocate value numbers for the leaves
 403  * in our found entities.
 404  *
 405  * @param sels  a set that will contain all Sels that have a value number
 406  * @param ent   the entity that will be scalar replaced
 407  * @param vnum  the first value number we can assign
 408  * @param modes a flexible array, containing all the modes of
 409  *              the value numbers.
 410  *
 411  * @return the next free value number
 412  */
 413 static unsigned allocate_value_numbers(pset *sels, ir_entity *ent, unsigned vnum, ir_mode ***modes)
 414 {
 415         ir_node *sel, *next;
 416         path_t *key, *path;
 417         set *pathes = new_set(path_cmp, 8);
 418
 419         /* visit all Sel nodes in the chain of the entity */
 420         for (sel = get_entity_link(ent); sel; sel = next) {
 421                 next = get_irn_link(sel);
 422
 423                 /* we must mark this sel for later */
 424                 pset_insert_ptr(sels, sel);
 425
 426                 key  = find_path(sel, 0);
 427                 path = set_find(pathes, key, PATH_SIZE(key), path_hash(key));
 428
 429                 if (path)
 430                         SET_VNUM(sel, path->vnum);
 431                 else {
 432                         key->vnum = vnum++;
 433
 434                         set_insert(pathes, key, PATH_SIZE(key), path_hash(key));
 435
 436                         SET_VNUM(sel, key->vnum);
 437                         ARR_EXTO(ir_mode *, *modes, (int)((key->vnum + 15) & ~15));
 438
 439                         (*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel)));
 440
 441                         assert((*modes)[key->vnum] && "Value is not atomic");
 442
 443 #ifdef DEBUG_libfirm
 444                         /* Debug output */
 445                         if (get_opt_scalar_replacement_verbose() && get_firm_verbosity() > 1) {
 446                                 unsigned i;
 447                                 printf("  %s", get_entity_name(key->path[0].ent));
 448                                 for (i = 1; i < key->path_len; ++i) {
 449                                         if (is_entity(key->path[i].ent))
 450                                                 printf(".%s", get_entity_name(key->path[i].ent));
 451                                         else
 452                                                 printf("[%ld]", get_tarval_long(key->path[i].tv));
 453                                 }
 454                                 printf(" = %u (%s)\n", PTR_TO_INT(get_irn_link(sel)), get_mode_name((*modes)[key->vnum]));
 455                         }
 456 #endif /* DEBUG_libfirm */
 457                 }
 458                 free(key);
 459         }
 460
 461         del_set(pathes);
 462         set_entity_link(ent, NULL);
 463         return vnum;
 464 }
 465
 466 /**
 467  * A list entry for the fixing lists
 468  */
 469 typedef struct _list_entry_t {
 470         ir_node  *node;   /**< the node that must be fixed */
 471         unsigned vnum;    /**< the value number of this node */
 472 } list_entry_t;
 473
 474 /**
 475  * environment for memory walker
 476  */
 477 typedef struct _env_t {
 478         struct obstack obst;      /**< a obstack for the value blocks */
 479         int          nvals;       /**< number of values */
 480         ir_mode      **modes;     /**< the modes of the values */
 481         list_entry_t *fix_phis;   /**< list of all Phi nodes that must be fixed */
 482         list_entry_t *fix_loads;  /**< list of all Load nodes that must be fixed */
 483         pset         *sels;       /**< A set of all Sel nodes that have a value number */
 484 } env_t;
 485
 486 /**
 487  * topological walker.
 488  */
 489 static void topologic_walker(ir_node *node, void *ctx) {
 490         env_t        *env = ctx;
 491         ir_op        *op = get_irn_op(node);
 492         ir_node      *adr, *block, *mem, *unk, **value_arr, **in, *val;
 493         ir_mode      *mode;
 494         unsigned     vnum;
 495         int          i, j, n;
 496         list_entry_t *l;
 497
 498         if (op == op_Load) {
 499                 /* a load, check if we can resolve it */
 500                 adr = get_Load_ptr(node);
 501
 502                 if (! is_Sel(adr))
 503                         return;
 504
 505                 if (! pset_find_ptr(env->sels, adr))
 506                         return;
 507
 508                 /* ok, we have a Load that will be replaced */
 509                 vnum = GET_VNUM(adr);
 510
 511                 assert(vnum < (unsigned)env->nvals);
 512
 513                 block     = get_nodes_block(node);
 514                 value_arr = get_irn_link(block);
 515
 516                 /* check, if we can replace this Load */
 517                 if (value_arr[vnum]) {
 518                         mem = get_Load_mem(node);
 519
 520                         /* Beware: A Load can contain a hidden conversion in Firm.
 521                         This happens for instance in the following code:
 522
 523                          int i;
 524                          unsigned j = *(unsigned *)&i;
 525
 526                         Handle this here. */
 527                         val = value_arr[vnum];
 528                         mode = get_Load_mode(node);
 529                         if (mode != get_irn_mode(val))
 530                                 val = new_d_Conv(get_irn_dbg_info(node), val, mode);
 531
 532                         turn_into_tuple(node, pn_Load_max);
 533                         set_Tuple_pred(node, pn_Load_M,         mem);
 534                         set_Tuple_pred(node, pn_Load_res,       val);
 535                         set_Tuple_pred(node, pn_Load_X_regular, new_r_Jmp(current_ir_graph, block));
 536                         set_Tuple_pred(node, pn_Load_X_except,  new_Bad());
 537                 } else {
 538                         l = obstack_alloc(&env->obst, sizeof(*l));
 539                         l->node = node;
 540                         l->vnum = vnum;
 541
 542                         set_irn_link(node, env->fix_loads);
 543                         env->fix_loads = l;
 544                 }
 545         } else if (op == op_Store) {
 546                 /* a Store always can be replaced */
 547                 adr = get_Store_ptr(node);
 548
 549                 if (! is_Sel(adr))
 550                         return;
 551
 552                 if (! pset_find_ptr(env->sels, adr))
 553                         return;
 554
 555                 vnum = GET_VNUM(adr);
 556
 557                 assert(vnum < (unsigned)env->nvals);
 558
 559                 block     = get_nodes_block(node);
 560                 value_arr = get_irn_link(block);
 561
 562                 /* Beware: A Store can contain a hidden conversion in Firm. */
 563                 val = get_Store_value(node);
 564                 if (get_irn_mode(val) != env->modes[vnum])
 565                         val = new_d_Conv(get_irn_dbg_info(node), val, env->modes[vnum]);
 566                 value_arr[vnum] = val;
 567
 568                 mem = get_Store_mem(node);
 569                 block = get_nodes_block(node);
 570
 571                 turn_into_tuple(node, pn_Store_max);
 572                 set_Tuple_pred(node, pn_Store_M,         mem);
 573                 set_Tuple_pred(node, pn_Store_X_regular, new_r_Jmp(current_ir_graph, block));
 574                 set_Tuple_pred(node, pn_Store_X_except,  new_Bad());
 575         } else if (op == op_Phi && get_irn_mode(node) == mode_M) {
 576                 /*
 577                  * found a memory Phi: Here, we must create new Phi nodes
 578                  */
 579                 block     = get_nodes_block(node);
 580                 value_arr = get_irn_link(block);
 581
 582                 n = get_Block_n_cfgpreds(block);
 583
 584                 in = alloca(sizeof(*in) * n);
 585
 586                 for (i = env->nvals - 1; i >= 0; --i) {
 587                         unk = new_Unknown(env->modes[i]);
 588                         for (j = n - 1; j >= 0; --j)
 589                                 in[j] = unk;
 590
 591                         value_arr[i] = new_r_Phi(current_ir_graph, block, n, in, env->modes[i]);
 592
 593                         l = obstack_alloc(&env->obst, sizeof(*l));
 594                         l->node = value_arr[i];
 595                         l->vnum = i;
 596
 597                         set_irn_link(value_arr[i], env->fix_phis);
 598                         env->fix_phis = l;
 599                 }
 600         }
 601 }
 602
 603 /**
 604  * Walker: allocate the value array for every block.
 605  */
 606 static void alloc_value_arr(ir_node *block, void *ctx) {
 607         env_t *env = ctx;
 608         ir_node **var_arr = obstack_alloc(&env->obst, sizeof(*var_arr) * env->nvals);
 609
 610         /* the value array is empty at start */
 611         memset(var_arr, 0, sizeof(*var_arr) * env->nvals);
 612         set_irn_link(block, var_arr);
 613 }
 614
 615 /**
 616  * searches through blocks beginning from block for value
 617  * vnum and return it.
 618  */
 619 static ir_node *find_vnum_value(ir_node *block, unsigned vnum) {
 620         ir_node **value_arr;
 621         int i;
 622         ir_node *res;
 623
 624         if (Block_not_block_visited(block)) {
 625                 mark_Block_block_visited(block);
 626
 627                 value_arr = get_irn_link(block);
 628
 629                 if (value_arr[vnum])
 630                         return value_arr[vnum];
 631
 632                 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 633                         ir_node *pred = get_Block_cfgpred(block, i);
 634
 635                         res = find_vnum_value(get_nodes_block(pred), vnum);
 636                         if (res)
 637                                 return res;
 638                 }
 639         }
 640         return NULL;
 641 }
 642
 643 /**
 644  * fix the Phi list
 645  */
 646 static void fix_phis(env_t *env) {
 647         list_entry_t *l;
 648         ir_node      *phi, *block, *pred, *val;
 649         int          i;
 650
 651         for (l = env->fix_phis; l; l = get_irn_link(phi)) {
 652                 phi = l->node;
 653
 654                 block = get_nodes_block(phi);
 655                 for (i = get_irn_arity(phi) - 1; i >= 0; --i) {
 656                         pred = get_Block_cfgpred(block, i);
 657                         pred = get_nodes_block(pred);
 658
 659                         inc_irg_block_visited(current_ir_graph);
 660                         val = find_vnum_value(pred, l->vnum);
 661
 662                         if (val)
 663                                 set_irn_n(phi, i, val);
 664                 }
 665         }
 666 }
 667
 668 /**
 669  * fix the Load list
 670  */
 671 static void fix_loads(env_t *env) {
 672         list_entry_t *l;
 673         ir_node      *load, *block, *pred, *val = NULL, *mem;
 674         ir_mode      *mode;
 675         int          i;
 676
 677         for (l = env->fix_loads; l; l = get_irn_link(load)) {
 678                 load = l->node;
 679
 680                 block = get_nodes_block(load);
 681                 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 682                         pred = get_Block_cfgpred(block, i);
 683                         pred = get_nodes_block(pred);
 684
 685                         inc_irg_block_visited(current_ir_graph);
 686                         val = find_vnum_value(pred, l->vnum);
 687
 688                         if (val)
 689                                 break;
 690                 }
 691
 692                 if (! val) {
 693                         /* access of an uninitialized value */
 694                         val = new_Unknown(env->modes[l->vnum]);
 695                 }
 696
 697                 /* Beware: A Load can contain a hidden conversion in Firm.
 698                    Handle this here. */
 699                 mode = get_Load_mode(load);
 700                 if (mode != get_irn_mode(val))
 701                         val = new_d_Conv(get_irn_dbg_info(load), val, mode);
 702
 703                 mem = get_Load_mem(load);
 704
 705                 turn_into_tuple(load, pn_Load_max);
 706                 set_Tuple_pred(load, pn_Load_M,         mem);
 707                 set_Tuple_pred(load, pn_Load_res,       val);
 708                 set_Tuple_pred(load, pn_Load_X_regular, new_r_Jmp(current_ir_graph, block));
 709                 set_Tuple_pred(load, pn_Load_X_except,  new_Bad());
 710         }
 711 }
 712
 713 /**
 714  *  Make scalar replacement.
 715  *
 716  * @param sels    A set containing all Sel nodes that have a value number
 717  * @param nvals   The number of scalars.
 718  * @param modes   A flexible array, containing all the modes of
 719  *                the value numbers.
 720  */
 721 static void do_scalar_replacements(pset *sels, int nvals, ir_mode **modes) {
 722         env_t env;
 723
 724         obstack_init(&env.obst);
 725         env.nvals     = nvals;
 726         env.modes     = modes;
 727         env.fix_phis  = NULL;
 728         env.fix_loads = NULL;
 729         env.sels      = sels;
 730
 731         /* first step: allocate the value arrays for every block */
 732         irg_block_walk_graph(current_ir_graph, NULL, alloc_value_arr, &env);
 733
 734         /*
 735          * second step: walk over the graph blockwise in topological order
 736          * and fill the array as much as possible.
 737          */
 738         irg_walk_blkwise_graph(current_ir_graph, NULL, topologic_walker, &env);
 739
 740         /* third, fix the list of Phis, then the list of Loads */
 741         fix_phis(&env);
 742         fix_loads(&env);
 743
 744         obstack_free(&env.obst, NULL);
 745 }
 746
 747 /*
 748  * Find possible scalar replacements
 749  *
 750  * @param irg  The current ir graph.
 751  */
 752 void scalar_replacement_opt(ir_graph *irg) {
 753         unsigned  nvals;
 754         int       i;
 755         scalars_t key, *value;
 756         ir_node   *irg_frame;
 757         ir_mode   **modes;
 758         set       *set_ent;
 759         pset      *sels;
 760         ir_type   *ent_type;
 761         ir_graph  *rem;
 762
 763         if (! get_opt_scalar_replacement())
 764                 return;
 765
 766         rem = current_ir_graph;
 767
 768         /* Call algorithm that computes the out edges */
 769         assure_irg_outs(irg);
 770
 771         /* Find possible scalar replacements */
 772         if (find_possible_replacements(irg)) {
 773
 774                 if (get_opt_scalar_replacement_verbose()) {
 775                         printf("Scalar Replacement: %s\n", get_entity_name(get_irg_entity(irg)));
 776                 }
 777
 778                 /* Insert in set the scalar replacements. */
 779                 irg_frame = get_irg_frame(irg);
 780                 nvals = 0;
 781                 modes = NEW_ARR_F(ir_mode *, 16);
 782                 set_ent = new_set(ent_cmp, 8);
 783                 sels    = pset_new_ptr(8);
 784
 785                 for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) {
 786                         ir_node *succ = get_irn_out(irg_frame, i);
 787
 788                         if (is_Sel(succ)) {
 789                                 ir_entity *ent = get_Sel_entity(succ);
 790
 791                                 if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
 792                                         continue;
 793
 794                                 ent_type = get_entity_type(ent);
 795
 796                                 key.ent       = ent;
 797                                 key.ent_owner = get_entity_owner(ent);
 798                                 set_insert(set_ent, &key, sizeof(key), HASH_PTR(key.ent));
 799
 800                                 if (get_opt_scalar_replacement_verbose()) {
 801                                         if (is_Array_type(ent_type)) {
 802                                                 printf("  found array %s\n", get_entity_name(ent));
 803                                         }
 804                                         else if (is_Struct_type(ent_type)) {
 805                                                 printf("  found struct %s\n", get_entity_name(ent));
 806                                         }
 807                                         else if (is_atomic_type(ent_type))
 808                                                 printf("  found atomic value %s\n", get_entity_name(ent));
 809                                         else {
 810                                                 assert(0 && "Neither an array nor a struct or atomic value");
 811                                         }
 812                                 }
 813
 814                                 nvals = allocate_value_numbers(sels, ent, nvals, &modes);
 815                         }
 816                 }
 817
 818                 if (get_opt_scalar_replacement_verbose()) {
 819                         printf("  %u values will be needed\n", nvals);
 820                 }
 821
 822                 /* If scalars were found. */
 823                 if (nvals) {
 824                         do_scalar_replacements(sels, nvals, modes);
 825
 826                         for (value = set_first(set_ent); value; value = set_next(set_ent)) {
 827                                 remove_class_member(value->ent_owner, value->ent);
 828                         }
 829                 }
 830
 831                 del_pset(sels);
 832                 del_set(set_ent);
 833                 DEL_ARR_F(modes);
 834
 835                 if (nvals) {
 836                         /*
 837                          * We changed the graph, but did NOT introduce new blocks
 838                          * neither changed control flow, cf-backedges should be still
 839                          * consistent.
 840                          */
 841                         set_irg_outs_inconsistent(irg);
 842                         set_irg_loopinfo_inconsistent(irg);
 843                 }
 844         }
 845
 846         current_ir_graph = rem;
 847 }