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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/scalar_replace.c
   4  * Purpose:     scalar replacement of arrays and compounds
   5  * Author:      Beyhan Veliev
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2005 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #ifdef HAVE_ALLOCA_H
  16 #include <alloca.h>
  17 #endif
  18
  19 #ifdef HAVE_MALLOC_H
  20 #include <malloc.h>
  21 #endif
  22
  23 #include "scalar_replace.h"
  24
  25 /**
  26  * A path element entry: it is either an entity
  27  * or a tarval, because the evaluate only constant array
  28  * accesses like a.b.c[8].d
  29  */
  30 typedef union {
  31   entity *ent;
  32   tarval *tv;
  33 } path_elem_t;
  34
  35 /**
  36  * An access path, used to assign value numbers
  37  * to variables that will be skalar replaced
  38  */
  39 typedef struct _path_t {
  40   unsigned    vnum;      /**< the value number */
  41   unsigned    path_len;  /**< the length of the access path */
  42   path_elem_t path[1];   /**< the path */
  43 } path_t;
  44
  45 typedef struct {
  46   ir_node *irn;                 /**< Phi or unknown node from the graph to be repairing. */
  47   ir_node **link;               /**< Array of Stores's volue, that have been scalar replaced. */
  48 } repairs_t;
  49
  50 typedef struct _scalars_t {
  51   entity *ent;                 /**< A entity for scalar replacement. */
  52   type *ent_owner;             /**< The owner of this entity. */
  53 } scalars_t;
  54
  55
  56 /**
  57  * Compare two pathes.
  58  *
  59  * @return 0 if they are identically
  60  */
  61 static int path_cmp(const void *elt, const void *key, size_t size)
  62 {
  63   const path_t *p1 = elt;
  64   const path_t *p2 = key;
  65
  66   return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
  67 }
  68
  69 /**
  70  * Compare two elements of the repairs_t set.
  71  *
  72  * @return 0 if they are identically
  73  */
  74 static int set_cmp(const void *elt, const void *key, size_t size)
  75 {
  76   const repairs_t *c1 = elt;
  77   const repairs_t *c2 = key;
  78
  79   return c1->irn != c2->irn;
  80 }
  81
  82 /**
  83  * Compare two elements of the scalars_t set.
  84  *
  85  * @return 0 if they are identically
  86  */
  87 static int ent_cmp(const void *elt, const void *key, size_t size)
  88 {
  89   const scalars_t *c1 = elt;
  90   const scalars_t *c2 = key;
  91
  92   return c1->ent != c2->ent;
  93 }
  94
  95 /**
  96  * Calculate a hash value for a path.
  97  */
  98 static unsigned path_hash(const path_t *path)
  99 {
 100   unsigned hash = 0;
 101   unsigned i;
 102
 103   for (i = 0; i < path->path_len; ++i)
 104     hash ^= (unsigned)path->path[i].ent;
 105
 106   return hash >> 4;
 107 }
 108
 109 /**
 110  * Returns non-zero, if all indeces of a Sel node are constants.
 111  *
 112  * @param sel  the Sel node that will be checked
 113  */
 114 static int is_const_sel(ir_node *sel) {
 115   int i, n = get_Sel_n_indexs(sel);
 116
 117   for (i = 0; i < n; ++i) {
 118     ir_node *idx = get_Sel_index(sel, i);
 119
 120     if (get_irn_op(idx) != op_Const)
 121       return 0;
 122   }
 123   return 1;
 124 }
 125
 126 /**
 127  * Returns non-zero, if the address of a Sel node (or it's succsessor Sels) is taken.
 128  *
 129  * @param sel  the Sel node
 130  */
 131 static int is_address_taken(type *ent_type, ir_node *sel)
 132 {
 133   int i, n;
 134
 135   if (! is_const_sel(sel))
 136     return 1;
 137
 138   n = get_irn_n_outs(sel);
 139   for (i = 0; i < n; ++i) {
 140     ir_node *succ = get_irn_out(sel, i);
 141
 142     switch (get_irn_opcode(succ)) {
 143     case iro_Load:
 144       break;
 145
 146     case iro_Store:
 147       /* check that Sel is not the store's value */
 148       if (get_Store_value(succ) == sel)
 149         return 1;
 150       break;
 151
 152     case iro_Sel: {
 153       /* Check the Sel successor of Sel */
 154       int res = is_address_taken(ent_type, succ);
 155
 156       if (res)
 157         return 1;
 158       break;
 159     }
 160     default:
 161       /* another op, the address is taken */
 162       return 1;
 163     }
 164   }
 165   return 0;
 166 }
 167
 168 /**
 169  * Link all leave Sels with the entity.
 170  *
 171  * @param ent  the entity that will be scalar replaced
 172  * @param sel  a Sel node that selects some fields of this entity
 173  */
 174 static void link_all_leave_sels(entity *ent, ir_node *sel)
 175 {
 176   int i, n, flag = 1;
 177
 178   n = get_irn_n_outs(sel);
 179   for (i = 0; i < n; ++i) {
 180     ir_node *succ = get_irn_out(sel, i);
 181
 182     if (get_irn_op(succ) == op_Sel) {
 183       link_all_leave_sels(ent, succ);
 184       flag = 0;
 185     }
 186   }
 187   if (flag) {
 188     /* we know we are at a leave, because this function is only
 189      * called if the address is NOT taken, so succ must be a Load
 190      * or a Store node
 191      */
 192     set_irn_link(sel, get_entity_link(ent));
 193     set_entity_link(ent, sel);
 194   }
 195 }
 196
 197 /* we need a special address that serves as an address taken marker */
 198 static char _x;
 199 static void *ADDRESS_TAKEN = &_x;
 200
 201 /**
 202  * Find possible scalar replacements.
 203  *
 204  * @param irg  an IR graph
 205  *
 206  * This function finds variables on the (members of the) frame type
 207  * that can be scalar replaced, because their address is never taken.
 208  * If such a variable is found, it's entity link will hold a list of all
 209  * Sel nodes, that selects the atomar fields of this entity.
 210  * Otherwise, the link will be NULL.
 211  */
 212 static void do_find_scalar_replacements(ir_graph *irg)
 213 {
 214   ir_node *irg_frame = get_irg_frame(irg);
 215   int i, n;
 216
 217   n = get_irn_n_outs(irg_frame);
 218
 219   /* first, clear the link field of all interesting entities */
 220   for (i = 0 ; i < n; i++) {
 221     ir_node *succ = get_irn_out(irg_frame, i);
 222
 223     if (get_irn_op(succ) == op_Sel) {
 224       entity *ent = get_Sel_entity(succ);
 225       set_entity_link(ent, NULL);
 226     }
 227   }
 228
 229   /* Check the ir_graph for Sel nodes. If the entity of Sel isn't a scalar replacement
 230    set the link of this entity equal NULL. */
 231   for (i = 0 ; i < n; i++) {
 232     ir_node *succ = get_irn_out(irg_frame, i);
 233
 234     if (get_irn_op(succ) == op_Sel) {
 235       entity *ent = get_Sel_entity(succ);
 236       type *ent_type = get_entity_type(ent);
 237
 238       /* we can handle arrays, structs and atomic types yet */
 239       if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
 240         if (is_address_taken(ent_type, succ)) {
 241           set_entity_link(ent, ADDRESS_TAKEN);
 242         }
 243         else {
 244           if (get_entity_link(ent) != ADDRESS_TAKEN)
 245             link_all_leave_sels(ent, succ);
 246         }
 247       }
 248     }
 249   }
 250 }
 251
 252 /**
 253  * Return a path from the Sel node sel to it's root.
 254  */
 255 static path_t *find_path(ir_node *sel, unsigned len)
 256 {
 257   int pos, i, n;
 258   path_t *res;
 259   ir_node *pred = get_Sel_ptr(sel);
 260   /* the current Sel node will add some path elements */
 261   n    = get_Sel_n_indexs(sel);
 262   len += n + 1;
 263
 264   if (get_irn_op(pred) != op_Sel) {
 265     /* we found the root */
 266
 267     res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
 268     res->path_len = len;
 269   }
 270   else
 271     res = find_path(pred, len);
 272
 273   pos = res->path_len - len;
 274
 275   res->path[pos++].ent = get_Sel_entity(sel);
 276   for (i = 0; i < n; ++i) {
 277     ir_node *index = get_Sel_index(sel, i);
 278
 279     res->path[pos++].tv = get_Const_tarval(index);
 280   }
 281   return res;
 282 }
 283
 284
 285 /**
 286  * Allocate value numbers for the leaves
 287  * in our found entities.
 288  *
 289  * @param ent   the entity that will be scalar replaced
 290  * @param vnum  the first value number we can assign
 291  * @param modes a flexible array, containing all the modes of
 292  *              the value numbers.
 293  *
 294  * @return the next free value number
 295  */
 296 static unsigned allocate_value_numbers(entity *ent, unsigned vnum, ir_mode ***modes)
 297 {
 298   ir_node *sel, *next;
 299   path_t *key, *path;
 300   set *pathes = new_set(path_cmp, 8);
 301
 302   /* visit all Sel nodes in the chain of the entity */
 303   for (sel = get_entity_link(ent); sel; sel = next) {
 304     next = get_irn_link(sel);
 305
 306     key  = find_path(sel, 0);
 307     path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
 308
 309     if (path)
 310       set_irn_link(sel, (void *)path->vnum);
 311     else {
 312       unsigned i;
 313
 314       key->vnum = vnum++;
 315
 316       set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
 317
 318       set_irn_link(sel, (void *)key->vnum);
 319       ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15);
 320
 321       (*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel)));
 322
 323       printf("  %s", get_entity_name(ent));
 324       for (i = 1; i < key->path_len; ++i) {
 325         if (is_entity(key->path[i].ent))
 326           printf(".%s", get_entity_name(key->path[i].ent));
 327         else
 328           printf("[%ld]", get_tarval_long(key->path[i].tv));
 329       }
 330       printf(" = %u (%s)\n", (int)get_irn_link(sel), get_mode_name((*modes)[key->vnum]));
 331     }
 332     free(key);
 333   }
 334
 335   del_set(pathes);
 336   set_entity_link(ent, NULL);
 337   return vnum;
 338 }
 339
 340 static char p;
 341 static void *NODE_VISITED = &p;
 342 static char t;
 343 static void *LOOP_WALK = &t;
 344 static char s;
 345 static void *LOOP_HEAD_PHI = &s;
 346
 347 /**
 348  * environment for memory walker
 349  */
 350 typedef struct _env_t {
 351   struct obstack obst;  /**< a obstack for the value blocks */
 352   int     nvals;        /**< number of values */
 353   ir_mode **modes;      /**< the modes of the values */
 354 } env_t;
 355
 356 static char q;
 357 static void *PRED_SEARCH = &q;
 358
 359 /**
 360  * Recursive  walk over the blocks, that are predecessors of "node".
 361  *
 362  * @param node     A Load or Phi node. The predecessor of this node muss be faund.
 363  * @param value    A struct pointer, that contains the block of node and their link.
 364  * @parm  repairs  A set, that contains all blocks, that have a array as link, and all Phis, that
 365  *                 have copies to repair.
 366  * @param pos      The position, that muss contain the  predecessor of node, in the array, that have got the bloks
 367  *                 from the repairs set.
 368  * @param phi_pred If node is a Phi, phi_pred is the predecessor number of this Phi, that muss be repair.
 369  */
 370
 371 static void pred_search(ir_node *node, repairs_t *value, set *repairs, int pos, int phi_pred)
 372 {
 373   ir_node *nodes_block;
 374   repairs_t key, *value_pred;
 375   int i, n;
 376
 377   DDMN(node);
 378   nodes_block = get_nodes_block(node);
 379
 380   /* If the predecessor is found.  */
 381   if ((pos == -2 && value->link[pos] !=  NULL))
 382     return;
 383
 384   n = get_Block_n_cfgpreds(nodes_block);
 385
 386   for (i = n - 1; i >= 0; --i) {
 387     ir_node *pred = get_Block_cfgpred(nodes_block, i);
 388
 389     key.irn = nodes_block;
 390     value_pred = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 391     /* If nodes_block don't have the necessary information and the predecessor of it isn't
 392        visited "pred_search" was called recursive. Else the necessary information is found
 393        and the recursion stops. */
 394     if (value_pred == NULL || value_pred->link[pos] == NULL) {
 395       if (get_irn_link(pred) != PRED_SEARCH) {
 396         set_irn_link(node, PRED_SEARCH);
 397         pred_search(pred, value, repairs, pos, phi_pred);
 398       }
 399     }
 400     else {
 401       if (value->link[pos] == NULL && pos != -2) {
 402         if (get_Block_dom_depth(value->irn) >=
 403             get_Block_dom_depth(get_nodes_block(value_pred->link[pos]))) {
 404           value->link[pos] = value_pred->link[pos];
 405           pos = -2;
 406           break;
 407         }
 408       }
 409       else {
 410         if (get_irn_op(value->link[pos]) == op_Phi && pos != -2 &&
 411             value->link[pos] != value_pred->link[pos]) {
 412           set_Phi_pred(value->link[pos], phi_pred, value_pred->link[pos]);
 413           pos = -2;
 414           break;
 415         }
 416       }
 417     }
 418   }
 419
 420   if (get_irn_link(node) == PRED_SEARCH)
 421     set_irn_link(node, NULL);
 422 }
 423
 424 /**
 425  * Create a link for blocks, that have Phi, Load or Store nodes for scalar_replacement.
 426  *
 427  * @param node    A Phi, Load or Store node, that block muss get a  link.
 428  * @param env     Contains information about scalars number and mode.
 429  * @parm  repairs A set, that contains all blocks, that have a link, and all Phis, that
 430  *                 have copies to repair.
 431  */
 432 static void block_link(ir_node *node, env_t *env, set *repairs)
 433 {
 434   repairs_t key, *value;
 435   ir_node *nods_block ;
 436   int i;
 437   nods_block = get_nodes_block(node);
 438   /* If the block of the node have no link. */
 439   if (get_irn_link(nods_block) == NULL) {
 440     DDMN(nods_block);
 441     key.irn = nods_block;
 442     value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 443     value->link = obstack_alloc(&env->obst, sizeof(ir_node *) * env->nvals);
 444      /* The block of the node be inserted in the set repairs, because it have yet a link.
 445         The link is a array with size equal to number of scalars.*/
 446     for (i = 0; i < env->nvals; i++)
 447       /* First  all links member be set to NULL. */
 448       value->link[i] = NULL;
 449     set_irn_link(nods_block, value->link);
 450   }
 451 }
 452
 453 /**
 454  * Handle Phis, that get the memory edge of Loads or Stors, that were been scalar replaced or
 455  * will be scalar replaced.
 456  *
 457  * @param phi     A Phi node, that muss have mode_M.
 458  * @param env     Contains information about scalars number and mode.
 459  * @parm  repairs A set that contains all blocks having a link and all Phis that
 460  *                 have copies to repair.
 461  */
 462 static void phi_handling(ir_node *phi, env_t *env, set *repairs)
 463 {
 464   ir_node *phi_block, **link;
 465   repairs_t key, *value;
 466   int rem;
 467   int p = 0, i, phi_preds;
 468   ir_node **in;
 469
 470   key.irn = phi;
 471   value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 472
 473   /* Test if the phi have been handled. */
 474   if (value != NULL)
 475     return;
 476
 477   rem = get_optimize();
 478
 479   phi_block = get_nodes_block(phi);
 480   phi_preds = get_Phi_n_preds(phi);
 481
 482   /* Test if the Phi have predecessors, that were been or will be scalar replaced. */
 483   for (i = 0; i < phi_preds; i++){
 484     ir_node *pred = get_Phi_pred(phi, i);
 485     ir_node *pred_block = get_nodes_block(pred);
 486
 487     key.irn = pred_block;
 488     value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 489
 490     if (value != NULL)
 491       p++;
 492   }
 493   /* Phis from the loop head muss be handled.*/
 494   if (get_irn_link(phi) == LOOP_HEAD_PHI)
 495     p++;
 496
 497   /* If the Phi node have such predecessor(s), be inserted in the repairs set, else is nothing to do
 498      and exit "phi_handling".*/
 499   if (p) {
 500     key.irn = phi;
 501     value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 502   }
 503   else
 504     return;
 505
 506   //DDMN(phi);
 507   if (get_irn_link(phi_block) == NULL)
 508     block_link(phi, env, repairs);
 509
 510   link = get_irn_link(phi_block);
 511
 512   key.irn = phi_block;
 513   value = set_find(repairs, &key, sizeof(key), HASH_PTR(phi_block));
 514
 515   in = alloca(phi_preds * sizeof(*in));
 516
 517   /* We will build some Phi nodes. Beware, as they have all Unknown predecessors, CSE
 518    * would combine them into one. To prevent this, we must deactivate Optimizations here
 519    */
 520   for (p = 0; p < env->nvals; ++p) {
 521
 522     for (i = 0; i < phi_preds; ++i)
 523       in[i] = new_Unknown(env->modes[p]);
 524
 525     set_optimize(0);
 526     value->link[p] = new_r_Phi(current_ir_graph, get_nodes_block(phi), phi_preds, in, env->modes[p]);
 527     set_optimize(rem);
 528   }
 529 }
 530
 531 /**
 532  * Handle Loads, that were been scalar replaced or
 533  * will be scalar replaced.
 534  *
 535  * @param load    A load node.
 536  * @param env     Contains information about scalars number and mode.
 537  * @parm  repairs A set, that contains all blocks, that have a  link, and all Phis, that
 538  *                 have copies to repair.
 539  */
 540 static void load_handling(ir_node *load, env_t *env, set *repairs)
 541 {
 542   repairs_t key, *value;
 543   ir_node *load_ptr, *load_mem, *nods_block;
 544   unsigned i;
 545
 546   nods_block = get_nodes_block(load);
 547   load_ptr = get_Load_ptr(load);
 548   load_mem = get_Load_mem(load);
 549   // DDMN(load);
 550   /* The pointer predecessor of Load muss be a Sel node. */
 551   if (get_irn_op(load_ptr) == op_Sel) {
 552     /* If the link field of sel's entity is set to "ADDRESS_TAKEN", that means this value
 553        can't be scalar replaced. It is nothing to do and load_handling() must be exited. */
 554     if (get_entity_link(get_Sel_entity(load_ptr)) == ADDRESS_TAKEN)
 555       return;
 556
 557     key.irn = nods_block;
 558     value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
 559
 560     /* Load's pointer predecessor's link field contains the position in the block's link, where
 561        must be searched the predecessor of this Load. */
 562     i = (unsigned)get_irn_link(load_ptr);
 563
 564     /* If the link of Load's block doesn't contains at position "i" a node or isn't calculated,
 565        than pred_search() must be called .*/
 566     if (value == NULL) {
 567       block_link(load, env, repairs);
 568       key.irn = nods_block;
 569       value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
 570       pred_search(load, value, repairs, i, 0);
 571     } else if (value->link[i] == NULL)
 572       pred_search(load, value, repairs, i, 0);
 573
 574     /* If after the pred_search() call the link of Load's block at position "i" is equal to NULL,
 575        that means the loaded value wasn't initialized and the load predecessor is set to Unknown */
 576     if (value->link[i] == NULL)
 577       value->link[i] = new_Unknown(env->modes[i]);
 578
 579     /* The Load node can be turned into a tuple now. This tuple will be optimized later. */
 580     turn_into_tuple(load, pn_Load_max);
 581     set_Tuple_pred(load, pn_Load_M, load_mem);
 582     set_Tuple_pred(load, pn_Load_res, value->link[i]);
 583     set_Tuple_pred(load, pn_Load_X_except, new_Bad());
 584   }
 585 }
 586
 587 /**
 588  * A walker along the memory edge. Load and Phi nodes muss be found for optimization
 589  *
 590  * @param node    A node from the graph.
 591  * @param env     Contains information about scalars number and mode.
 592  * @parm  repairs A set, that contains all blocks, that have a  link, and all Phis, that
 593  *                have copies to repair.
 594 */
 595 static void memory_edge_walk2(ir_node *node, env_t *env, set *repairs)
 596 {
 597   int i, p, n = get_irn_arity(node);
 598   repairs_t key, *value, *value_block;
 599   ir_node *phi_pred;
 600   DDMN(node);
 601
 602   for (i = 0; i < n; i++) {
 603     ir_node *pred = get_irn_n(node, i);
 604
 605     if((get_irn_op(pred) == op_Proj    &&
 606         get_irn_mode(pred) == mode_M)  ||
 607        get_irn_mode(pred) == mode_T    ||
 608        is_memop(pred)                  ||
 609        get_irn_op(pred) == op_Call     ||
 610        get_irn_op(pred) == op_Alloc)
 611       memory_edge_walk2(pred, env, repairs);
 612
 613     if(get_irn_op(pred) == op_Phi    &&
 614        get_irn_mode(pred) == mode_M &&
 615        get_irn_link(pred) != NODE_VISITED){
 616       set_irn_link(pred, NODE_VISITED);
 617       memory_edge_walk2(pred, env, repairs);
 618     }
 619   }
 620
 621    if (get_irn_op(node) == op_Load)
 622      load_handling(node, env, repairs);
 623
 624    if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
 625      key.irn = node;
 626      value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 627      /* If the phi is in the set " repairs ", then must be handled.*/
 628      if (value != NULL){
 629        //  DDMN(node);
 630        key.irn = get_nodes_block(node);
 631        value_block = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 632        n = get_irn_arity(node);
 633        /* All predecessors of a Phi node muss be found.*/
 634        for(i = 0; i < env->nvals; i ++)
 635          for(p = 0; p < n; p ++){
 636            phi_pred = get_Phi_pred(value->irn, p);
 637            pred_search(phi_pred, value_block, repairs, i, p);
 638          }
 639      }
 640    }
 641    /* Reset the links, that have been used by the walk.*/
 642    if (get_irn_link(node) == NODE_VISITED)
 643      set_irn_link(node, NULL);
 644 }
 645
 646 /**
 647  * A walker along the memory edge in a loop.The walker walk from the node to the loop head.
 648  * Load and Phi nodes muss be found for optimisation
 649  *
 650  * @param *node    A node from the graph.
 651  * @param *env     Contains information about scalars number and mode.
 652  * @parm  *repairs A set, that contains all blocks, that have a  link, and all Phis, that
 653  *                 have copies to repair.
 654 */
 655 static void loop_walk(ir_node *node, env_t *env, set *repairs)
 656 {
 657   int i, p, n = get_irn_arity(node);
 658   repairs_t key, *value, *value_block;
 659   ir_node *phi_pred;
 660   DDMN(node);
 661
 662   /* Test if the loop head have been achieved. */
 663   if (has_backedges(get_nodes_block(node)))
 664     return;
 665
 666   for (i = 0; i < n; i++) {
 667     ir_node *pred = get_irn_n(node, i);
 668
 669     if((get_irn_op(pred) == op_Proj    &&
 670         get_irn_mode(pred) == mode_M)  ||
 671        get_irn_mode(pred) == mode_T    ||
 672        is_memop(pred)                  ||
 673        get_irn_op(pred) == op_Call     ||
 674        get_irn_op(pred) == op_Alloc)
 675       loop_walk(pred, env, repairs);
 676
 677     if(get_irn_op(pred) == op_Phi    &&
 678        get_irn_mode(pred) == mode_M &&
 679        get_irn_link(pred) !=  LOOP_WALK) {
 680       set_irn_link(pred, LOOP_WALK);
 681       loop_walk(pred, env, repairs);
 682     }
 683   }
 684
 685   if (get_irn_op(node) == op_Load)
 686     load_handling(node, env, repairs);
 687
 688   if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
 689     key.irn = node;
 690     value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 691     /* If the phi is in the set " repairs ", then muss be handled.*/
 692     if(value != NULL){
 693       DDMN(node);
 694       key.irn = get_nodes_block(node);
 695       value_block = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 696       n = get_irn_arity(node);
 697       /* All predecessors of a Phi node muss be found.*/
 698       for(i = 0; i < env->nvals; i ++)
 699         for(p = 0; p < n; p ++){
 700           phi_pred = get_Phi_pred(value->irn, p);
 701           pred_search(phi_pred, value_block, repairs, i, p);
 702         }
 703     }
 704   }
 705   /* Reset the links, that have beeb used by the walk.*/
 706   if(get_irn_link(node) == LOOP_WALK)
 707     set_irn_link(node, NULL);
 708 }
 709
 710 /**
 711  * Handle Stores that were been scalar replaced or
 712  * will be scalar replaced.
 713  *
 714  * @param load    A store node.
 715  * @param env     Contains information about scalars number and mode.
 716  * @parm  repairs A set, that contains all blocks, that have a link, and all Phis, that
 717  *                have copies to repair.
 718  */
 719 static void store_handling(ir_node *store, env_t *env, set *repairs)
 720 {
 721   repairs_t key, *value;
 722   ir_node *nods_block, *store_mem, *store_ptr, *store_value, *phi;
 723   ir_loop *store_l;
 724
 725   store_ptr = get_Store_ptr(store);
 726
 727   /* The pointer predecessor of Store must be a Sel node.*/
 728   if (get_irn_op(store_ptr) == op_Sel) {
 729     /* If the link field of a Store's is set to "ADDRESS_TAKEN", that mean this value
 730        can't be scalar replaced. It's nothing to do and store_handling() must be exit.*/
 731     if (get_entity_link(get_Sel_entity(store_ptr)) == ADDRESS_TAKEN)
 732       return;
 733
 734     /* If the Store node is in a loop, than the loop head of the Store
 735      * must be handled, if this was not already done. */
 736     store_l = get_irn_loop(store);
 737     if (store_l != NULL) {
 738       phi = get_loop_node(store_l, 0);
 739       if (get_irn_op(phi) != op_Block) {
 740         key.irn = get_nodes_block(phi);
 741         value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 742         if (value == NULL) {
 743           set_irn_link(phi, LOOP_HEAD_PHI);
 744           block_link(phi, env, repairs);
 745           phi_handling(phi, env, repairs);
 746         }
 747       }
 748     }
 749
 750     DDMN(store);
 751     nods_block = get_nodes_block(store);
 752
 753     key.irn = nods_block;
 754     value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
 755
 756     store_mem   = get_Store_mem(store);
 757     store_value = get_Store_value(store);
 758
 759     if (store_l != NULL)
 760       loop_walk(store, env, repairs);
 761     else
 762       memory_edge_walk2(store, env, repairs);
 763     /* Store's pointer predecessor's link field contains the position in the block's link, where
 764      must be saved the value predecessor of this store. */
 765     value->link[(unsigned)get_irn_link(store_ptr)] = store_value;
 766
 767     /* The store node can be turned into a tuple now. This tuple will be optimized later. */
 768     turn_into_tuple(store, pn_Store_max);
 769     set_Tuple_pred(store, pn_Store_M, store_mem);
 770     set_Tuple_pred(store, pn_Store_X_except, new_Bad());
 771   }
 772 }
 773
 774 /**
 775  * A walker along the memory edge. Stores, Phis and their blocks as well Load's blocks must be found for optimization
 776  *
 777  * @param node    A node from the graph.
 778  * @param env     Contains information about scalars number and mode.
 779  * @parm  repairs A set, that contains all blocks, that have a link, and all Phis, that
 780  *                have copies to repair.
 781 */
 782 static void memory_edge_walk(ir_node *node, env_t *env, set *repairs)
 783 {
 784   int i, n = get_irn_arity(node);
 785   ir_op *op;
 786
 787   DDMN(node);
 788
 789   set_irn_link(get_nodes_block(node), NULL);
 790
 791   for (i = n - 1; i >= 0; --i) {
 792     ir_node *pred = get_irn_n(node, i);
 793     ir_op *op = get_irn_op(pred);
 794
 795     if ((op == op_Proj    &&
 796          get_irn_mode(pred) == mode_M) ||
 797        op == op_Load                   ||
 798        op == op_Store                  ||
 799        op == op_Call                   ||
 800        op == op_Alloc)
 801       memory_edge_walk(pred, env, repairs);
 802
 803     if (op == op_Phi                 &&
 804         get_irn_mode(pred) == mode_M &&
 805         get_irn_link(pred) != NODE_VISITED) {
 806       set_irn_link(pred, NODE_VISITED);
 807       memory_edge_walk(pred, env, repairs);
 808     }
 809   }
 810
 811   op =  get_irn_op(node);
 812   if (op == op_Store || op == op_Load)
 813     block_link(node, env, repairs);
 814
 815   if (op == op_Phi && get_irn_mode(node) == mode_M)
 816     phi_handling(node, env, repairs);
 817
 818   if (op == op_Store)
 819     store_handling(node, env, repairs);
 820
 821   /* Reset the links, that have been used by the walk.*/
 822   if (get_irn_link(node) == NODE_VISITED)
 823     set_irn_link(node, NULL);
 824 }
 825
 826 /**
 827  *  Make scalar replacement.
 828  *
 829  * @param envals  The number of scalars.
 830  * @parm  repairs A set, that contains all blocks, that have a  link, and all Phis, that
 831  *                have copies to repair.
 832  * @param modes   A flexible array, containing all the modes of
 833  *                the value numbers.
 834  */
 835 static void do_scalar_replacements(int nvals, set * repairs, ir_mode **modes)
 836 {
 837   ir_node *end_block = get_irg_end_block(current_ir_graph);
 838   int i;
 839   int n = get_Block_n_cfgpreds(end_block);
 840   env_t env;
 841
 842   obstack_init(&env.obst);
 843   env.nvals = nvals;
 844   env.modes = modes;
 845
 846   /* Search for scalars.*/
 847   for (i = 0; i < n; ++i) {
 848     ir_node *pred = get_Block_cfgpred(end_block, i);
 849     if (get_irn_op(pred) != op_Block)
 850       memory_edge_walk(pred, &env, repairs);
 851   }
 852
 853   /* Search for predecessors of scalars.*/
 854   for (i = 0; i < n; ++i) {
 855     ir_node *pred = get_Block_cfgpred(end_block, i);
 856     if (get_irn_op(pred) != op_Block)
 857       memory_edge_walk2(pred, &env, repairs);
 858   }
 859   obstack_free(&env.obst, NULL);
 860 }
 861
 862 /*
 863  * Find possible scalar replacements
 864  *
 865  * @param irg  The current ir graph.
 866  */
 867 void find_scalar_replacements(ir_graph *irg)
 868 {
 869   unsigned nvals;
 870   int i;
 871   scalars_t key, *value;
 872   ir_node *irg_frame;
 873   ir_mode **modes;
 874   set *set_ent, *repairs;
 875   type *ent_type;
 876
 877   /* Call algorithm that computes the out edges */
 878   compute_outs(irg);
 879   /* Call algorithm that computes the loop information */
 880   construct_backedges(irg);
 881
 882   /* Call algorithm that computes the backedges */
 883   construct_cf_backedges(irg);
 884
 885   /* Call algorithm that computes the dominator trees. */
 886   compute_doms(irg);
 887
 888   /* Find possible scalar replacements */
 889   do_find_scalar_replacements(irg);
 890
 891   printf("Called for %s\n", get_entity_name(get_irg_entity(irg)));
 892
 893   /* Insert in set the scalar replacemnts. */
 894   irg_frame = get_irg_frame(irg);
 895   nvals = 0;
 896   modes = NEW_ARR_F(ir_mode *, 16);
 897   set_ent = new_set(ent_cmp, 8);
 898
 899   for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) {
 900     ir_node *succ = get_irn_out(irg_frame, i);
 901
 902     if (get_irn_op(succ) == op_Sel) {
 903       entity *ent = get_Sel_entity(succ);
 904
 905       if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
 906         continue;
 907
 908       ent_type = get_entity_type(ent);
 909
 910       key.ent = ent;
 911       key.ent_owner = get_entity_owner (ent);
 912       set_insert(set_ent, &key, sizeof(key), HASH_PTR(key.ent));
 913
 914       if (is_Array_type(ent_type)) {
 915         printf("<<<<<<<found array %s\n", get_entity_name(ent));
 916       }
 917       else if (is_Struct_type(ent_type)) {
 918         printf("<<<<<<<found struct %s\n", get_entity_name(ent));
 919       }
 920       else if(is_atomic_type(ent_type))
 921         printf("<<<<<<<found atomic value %s\n", get_entity_name(ent));
 922       else {
 923         assert(0 && "\nDon't a array, struct or atomic value");
 924       }
 925
 926       nvals = allocate_value_numbers(ent, nvals, &modes);
 927     }
 928   }
 929
 930   printf("  %u values will be needed\n", nvals);
 931
 932   /* A set of nodes that must be repaired. These are Phi or Unknown nodes. */
 933   repairs = new_set(set_cmp, 8);
 934
 935   /* If scalars ware found. */
 936   if (nvals)
 937     do_scalar_replacements(nvals, repairs, modes);
 938
 939   value = set_first(set_ent);
 940   for (; value != NULL; value = set_next(set_ent))
 941     remove_class_member(value->ent_owner, value->ent);
 942
 943   del_set(set_ent);
 944   del_set(repairs);
 945   DEL_ARR_F(modes);
 946 }