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  * @param  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 static void pred_search(ir_node *node, repairs_t *value, set *repairs, int pos, int phi_pred)
 371 {
 372   ir_node *nodes_block;
 373   repairs_t key, *value_pred;
 374   int i, n;
 375
 376   DDMN(node);
 377   nodes_block = get_nodes_block(node);
 378
 379   /* If the predecessor is found.  */
 380   if ((pos == -2 && value->link[pos] !=  NULL))
 381     return;
 382
 383   n = get_Block_n_cfgpreds(nodes_block);
 384
 385   for (i = n - 1; i >= 0; --i) {
 386     ir_node *pred = get_Block_cfgpred(nodes_block, i);
 387
 388     key.irn = nodes_block;
 389     value_pred = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 390     /* If nodes_block don't have the necessary information and the predecessor of it isn't
 391        visited "pred_search" was called recursive. Else the necessary information is found
 392        and the recursion stops. */
 393     if (value_pred == NULL || value_pred->link[pos] == NULL) {
 394       if (get_irn_link(pred) != PRED_SEARCH) {
 395         set_irn_link(node, PRED_SEARCH);
 396         pred_search(pred, value, repairs, pos, phi_pred);
 397       }
 398     }
 399     else {
 400       if (value->link[pos] == NULL && pos != -2) {
 401         if (get_Block_dom_depth(value->irn) >=
 402             get_Block_dom_depth(get_nodes_block(value_pred->link[pos]))) {
 403           value->link[pos] = value_pred->link[pos];
 404           pos = -2;
 405           break;
 406         }
 407       }
 408       else {
 409         if (get_irn_op(value->link[pos]) == op_Phi && pos != -2 &&
 410             value->link[pos] != value_pred->link[pos]) {
 411           set_Phi_pred(value->link[pos], phi_pred, value_pred->link[pos]);
 412           pos = -2;
 413           break;
 414         }
 415       }
 416     }
 417   }
 418
 419   if (get_irn_link(node) == PRED_SEARCH)
 420     set_irn_link(node, NULL);
 421 }
 422
 423 /**
 424  * Create a link for blocks, that have Phi, Load or Store nodes for scalar_replacement.
 425  *
 426  * @param node    A Phi, Load or Store node, that block muss get a  link.
 427  * @param env     Contains information about scalars number and mode.
 428  * @param repairs A set, that contains all blocks, that have a link, and all Phis, that
 429  *                have copies to repair.
 430  */
 431 static void block_link(ir_node *node, env_t *env, set *repairs)
 432 {
 433   repairs_t key, *value;
 434   ir_node *nods_block ;
 435   int i;
 436   nods_block = get_nodes_block(node);
 437   /* If the block of the node have no link. */
 438   if (get_irn_link(nods_block) == NULL) {
 439     DDMN(nods_block);
 440     key.irn = nods_block;
 441     value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 442     value->link = obstack_alloc(&env->obst, sizeof(ir_node *) * env->nvals);
 443      /* The block of the node be inserted in the set repairs, because it have yet a link.
 444         The link is a array with size equal to number of scalars.*/
 445     for (i = 0; i < env->nvals; i++)
 446       /* First  all links member be set to NULL. */
 447       value->link[i] = NULL;
 448     set_irn_link(nods_block, value->link);
 449   }
 450 }
 451
 452 /**
 453  * Handle Phis, that get the memory edge of Loads or Stors, that were been scalar replaced or
 454  * will be scalar replaced.
 455  *
 456  * @param phi     A Phi node, that muss have mode_M.
 457  * @param env     Contains information about scalars number and mode.
 458  * @param repairs A set that contains all blocks having a link and all Phis that
 459  *                have copies to repair.
 460  */
 461 static void phi_handling(ir_node *phi, env_t *env, set *repairs)
 462 {
 463   ir_node *phi_block, **link;
 464   repairs_t key, *value;
 465   int rem;
 466   int p = 0, i, phi_preds;
 467   ir_node **in;
 468
 469   key.irn = phi;
 470   value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 471
 472   /* Test if the phi have been handled. */
 473   if (value != NULL)
 474     return;
 475
 476   rem = get_optimize();
 477
 478   phi_block = get_nodes_block(phi);
 479   phi_preds = get_Phi_n_preds(phi);
 480
 481   /* Test if the Phi have predecessors, that were been or will be scalar replaced. */
 482   for (i = 0; i < phi_preds; i++){
 483     ir_node *pred = get_Phi_pred(phi, i);
 484     ir_node *pred_block = get_nodes_block(pred);
 485
 486     key.irn = pred_block;
 487     value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 488
 489     if (value != NULL)
 490       p++;
 491   }
 492   /* Phis from the loop head muss be handled.*/
 493   if (get_irn_link(phi) == LOOP_HEAD_PHI)
 494     p++;
 495
 496   /* If the Phi node have such predecessor(s), be inserted in the repairs set, else is nothing to do
 497      and exit "phi_handling".*/
 498   if (p) {
 499     key.irn = phi;
 500     value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 501   }
 502   else
 503     return;
 504
 505   //DDMN(phi);
 506   if (get_irn_link(phi_block) == NULL)
 507     block_link(phi, env, repairs);
 508
 509   link = get_irn_link(phi_block);
 510
 511   key.irn = phi_block;
 512   value = set_find(repairs, &key, sizeof(key), HASH_PTR(phi_block));
 513
 514   in = alloca(phi_preds * sizeof(*in));
 515
 516   /* We will build some Phi nodes. Beware, as they have all Unknown predecessors, CSE
 517    * would combine them into one. To prevent this, we must deactivate Optimizations here
 518    */
 519   for (p = 0; p < env->nvals; ++p) {
 520
 521     for (i = 0; i < phi_preds; ++i)
 522       in[i] = new_Unknown(env->modes[p]);
 523
 524     set_optimize(0);
 525     value->link[p] = new_r_Phi(current_ir_graph, get_nodes_block(phi), phi_preds, in, env->modes[p]);
 526     set_optimize(rem);
 527   }
 528 }
 529
 530 /**
 531  * Handle Loads, that were been scalar replaced or
 532  * will be scalar replaced.
 533  *
 534  * @param load    A load node.
 535  * @param env     Contains information about scalars number and mode.
 536  * @param repairs A set, that contains all blocks, that have a  link, and all Phis, that
 537  *                have copies to repair.
 538  */
 539 static void load_handling(ir_node *load, env_t *env, set *repairs)
 540 {
 541   repairs_t key, *value;
 542   ir_node *load_ptr, *load_mem, *nods_block;
 543   unsigned i;
 544
 545   nods_block = get_nodes_block(load);
 546   load_ptr = get_Load_ptr(load);
 547   load_mem = get_Load_mem(load);
 548   // DDMN(load);
 549   /* The pointer predecessor of Load muss be a Sel node. */
 550   if (get_irn_op(load_ptr) == op_Sel) {
 551     /* If the link field of sel's entity is set to "ADDRESS_TAKEN", that means this value
 552        can't be scalar replaced. It is nothing to do and load_handling() must be exited. */
 553     if (get_entity_link(get_Sel_entity(load_ptr)) == ADDRESS_TAKEN)
 554       return;
 555
 556     key.irn = nods_block;
 557     value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
 558
 559     /* Load's pointer predecessor's link field contains the position in the block's link, where
 560        must be searched the predecessor of this Load. */
 561     i = (unsigned)get_irn_link(load_ptr);
 562
 563     /* If the link of Load's block doesn't contains at position "i" a node or isn't calculated,
 564        than pred_search() must be called .*/
 565     if (value == NULL) {
 566       block_link(load, env, repairs);
 567       key.irn = nods_block;
 568       value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
 569       pred_search(load, value, repairs, i, 0);
 570     } else if (value->link[i] == NULL)
 571       pred_search(load, value, repairs, i, 0);
 572
 573     /* If after the pred_search() call the link of Load's block at position "i" is equal to NULL,
 574        that means the loaded value wasn't initialized and the load predecessor is set to Unknown */
 575     if (value->link[i] == NULL)
 576       value->link[i] = new_Unknown(env->modes[i]);
 577
 578     /* The Load node can be turned into a tuple now. This tuple will be optimized later. */
 579     turn_into_tuple(load, pn_Load_max);
 580     set_Tuple_pred(load, pn_Load_M, load_mem);
 581     set_Tuple_pred(load, pn_Load_res, value->link[i]);
 582     set_Tuple_pred(load, pn_Load_X_except, new_Bad());
 583   }
 584 }
 585
 586 /**
 587  * A walker along the memory edge. Load and Phi nodes muss be found for optimization
 588  *
 589  * @param node    A node from the graph.
 590  * @param env     Contains information about scalars number and mode.
 591  * @param repairs A set, that contains all blocks, that have a  link, and all Phis, that
 592  *                have copies to repair.
 593 */
 594 static void memory_edge_walk2(ir_node *node, env_t *env, set *repairs)
 595 {
 596   int i, p, n = get_irn_arity(node);
 597   repairs_t key, *value, *value_block;
 598   ir_node *phi_pred;
 599   DDMN(node);
 600
 601   for (i = 0; i < n; i++) {
 602     ir_node *pred = get_irn_n(node, i);
 603
 604     if((get_irn_op(pred) == op_Proj    &&
 605         get_irn_mode(pred) == mode_M)  ||
 606        get_irn_mode(pred) == mode_T    ||
 607        is_memop(pred)                  ||
 608        get_irn_op(pred) == op_Call     ||
 609        get_irn_op(pred) == op_Alloc)
 610       memory_edge_walk2(pred, env, repairs);
 611
 612     if(get_irn_op(pred) == op_Phi    &&
 613        get_irn_mode(pred) == mode_M &&
 614        get_irn_link(pred) != NODE_VISITED){
 615       set_irn_link(pred, NODE_VISITED);
 616       memory_edge_walk2(pred, env, repairs);
 617     }
 618   }
 619
 620    if (get_irn_op(node) == op_Load)
 621      load_handling(node, env, repairs);
 622
 623    if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
 624      key.irn = node;
 625      value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 626      /* If the phi is in the set " repairs ", then must be handled.*/
 627      if (value != NULL){
 628        //  DDMN(node);
 629        key.irn = get_nodes_block(node);
 630        value_block = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 631        n = get_irn_arity(node);
 632        /* All predecessors of a Phi node muss be found.*/
 633        for(i = 0; i < env->nvals; i ++)
 634          for(p = 0; p < n; p ++){
 635            phi_pred = get_Phi_pred(value->irn, p);
 636            pred_search(phi_pred, value_block, repairs, i, p);
 637          }
 638      }
 639    }
 640    /* Reset the links, that have been used by the walk.*/
 641    if (get_irn_link(node) == NODE_VISITED)
 642      set_irn_link(node, NULL);
 643 }
 644
 645 /**
 646  * A walker along the memory edge in a loop.The walker walk from the node to the loop head.
 647  * Load and Phi nodes muss be found for optimisation
 648  *
 649  * @param *node    A node from the graph.
 650  * @param *env     Contains information about scalars number and mode.
 651  * @param *repairs A set, that contains all blocks, that have a  link, and all Phis, that
 652  *                 have copies to repair.
 653 */
 654 static void loop_walk(ir_node *node, env_t *env, set *repairs)
 655 {
 656   int i, p, n = get_irn_arity(node);
 657   repairs_t key, *value, *value_block;
 658   ir_node *phi_pred;
 659   DDMN(node);
 660
 661   /* Test if the loop head have been achieved. */
 662   if (has_backedges(get_nodes_block(node)))
 663     return;
 664
 665   for (i = 0; i < n; i++) {
 666     ir_node *pred = get_irn_n(node, i);
 667
 668     if((get_irn_op(pred) == op_Proj    &&
 669         get_irn_mode(pred) == mode_M)  ||
 670        get_irn_mode(pred) == mode_T    ||
 671        is_memop(pred)                  ||
 672        get_irn_op(pred) == op_Call     ||
 673        get_irn_op(pred) == op_Alloc)
 674       loop_walk(pred, env, repairs);
 675
 676     if(get_irn_op(pred) == op_Phi    &&
 677        get_irn_mode(pred) == mode_M &&
 678        get_irn_link(pred) !=  LOOP_WALK) {
 679       set_irn_link(pred, LOOP_WALK);
 680       loop_walk(pred, env, repairs);
 681     }
 682   }
 683
 684   if (get_irn_op(node) == op_Load)
 685     load_handling(node, env, repairs);
 686
 687   if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
 688     key.irn = node;
 689     value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 690     /* If the phi is in the set " repairs ", then muss be handled.*/
 691     if(value != NULL){
 692       DDMN(node);
 693       key.irn = get_nodes_block(node);
 694       value_block = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 695       n = get_irn_arity(node);
 696       /* All predecessors of a Phi node muss be found.*/
 697       for(i = 0; i < env->nvals; i ++)
 698         for(p = 0; p < n; p ++){
 699           phi_pred = get_Phi_pred(value->irn, p);
 700           pred_search(phi_pred, value_block, repairs, i, p);
 701         }
 702     }
 703   }
 704   /* Reset the links, that have beeb used by the walk.*/
 705   if(get_irn_link(node) == LOOP_WALK)
 706     set_irn_link(node, NULL);
 707 }
 708
 709 /**
 710  * Handle Stores that were been scalar replaced or
 711  * will be scalar replaced.
 712  *
 713  * @param load    A store node.
 714  * @param env     Contains information about scalars number and mode.
 715  * @param repairs A set, that contains all blocks, that have a link, and all Phis, that
 716  *                have copies to repair.
 717  */
 718 static void store_handling(ir_node *store, env_t *env, set *repairs)
 719 {
 720   repairs_t key, *value;
 721   ir_node *nods_block, *store_mem, *store_ptr, *store_value, *phi;
 722   ir_loop *store_l;
 723
 724   store_ptr = get_Store_ptr(store);
 725
 726   /* The pointer predecessor of Store must be a Sel node.*/
 727   if (get_irn_op(store_ptr) == op_Sel) {
 728     /* If the link field of a Store's is set to "ADDRESS_TAKEN", that mean this value
 729        can't be scalar replaced. It's nothing to do and store_handling() must be exit.*/
 730     if (get_entity_link(get_Sel_entity(store_ptr)) == ADDRESS_TAKEN)
 731       return;
 732
 733     /* If the Store node is in a loop, than the loop head of the Store
 734      * must be handled, if this was not already done. */
 735     store_l = get_irn_loop(store);
 736     if (store_l != NULL) {
 737       phi = get_loop_node(store_l, 0);
 738       if (get_irn_op(phi) != op_Block) {
 739         key.irn = get_nodes_block(phi);
 740         value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
 741         if (value == NULL) {
 742           set_irn_link(phi, LOOP_HEAD_PHI);
 743           block_link(phi, env, repairs);
 744           phi_handling(phi, env, repairs);
 745         }
 746       }
 747     }
 748
 749     DDMN(store);
 750     nods_block = get_nodes_block(store);
 751
 752     key.irn = nods_block;
 753     value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
 754
 755     store_mem   = get_Store_mem(store);
 756     store_value = get_Store_value(store);
 757
 758     if (store_l != NULL)
 759       loop_walk(store, env, repairs);
 760     else
 761       memory_edge_walk2(store, env, repairs);
 762     /* Store's pointer predecessor's link field contains the position in the block's link, where
 763      must be saved the value predecessor of this store. */
 764     value->link[(unsigned)get_irn_link(store_ptr)] = store_value;
 765
 766     /* The store node can be turned into a tuple now. This tuple will be optimized later. */
 767     turn_into_tuple(store, pn_Store_max);
 768     set_Tuple_pred(store, pn_Store_M, store_mem);
 769     set_Tuple_pred(store, pn_Store_X_except, new_Bad());
 770   }
 771 }
 772
 773 /**
 774  * A walker along the memory edge. Stores, Phis and their blocks as well Load's blocks must be found for optimization
 775  *
 776  * @param node    A node from the graph.
 777  * @param env     Contains information about scalars number and mode.
 778  * @param repairs A set, that contains all blocks, that have a link, and all Phis, that
 779  *                have copies to repair.
 780 */
 781 static void memory_edge_walk(ir_node *node, env_t *env, set *repairs)
 782 {
 783   int i, n = get_irn_arity(node);
 784   ir_op *op;
 785
 786   DDMN(node);
 787
 788   set_irn_link(get_nodes_block(node), NULL);
 789
 790   for (i = n - 1; i >= 0; --i) {
 791     ir_node *pred = get_irn_n(node, i);
 792     ir_op *op = get_irn_op(pred);
 793
 794     if ((op == op_Proj    &&
 795          get_irn_mode(pred) == mode_M) ||
 796        op == op_Load                   ||
 797        op == op_Store                  ||
 798        op == op_Call                   ||
 799        op == op_Alloc)
 800       memory_edge_walk(pred, env, repairs);
 801
 802     if (op == op_Phi                 &&
 803         get_irn_mode(pred) == mode_M &&
 804         get_irn_link(pred) != NODE_VISITED) {
 805       set_irn_link(pred, NODE_VISITED);
 806       memory_edge_walk(pred, env, repairs);
 807     }
 808   }
 809
 810   op =  get_irn_op(node);
 811   if (op == op_Store || op == op_Load)
 812     block_link(node, env, repairs);
 813
 814   if (op == op_Phi && get_irn_mode(node) == mode_M)
 815     phi_handling(node, env, repairs);
 816
 817   if (op == op_Store)
 818     store_handling(node, env, repairs);
 819
 820   /* Reset the links, that have been used by the walk.*/
 821   if (get_irn_link(node) == NODE_VISITED)
 822     set_irn_link(node, NULL);
 823 }
 824
 825 /**
 826  *  Make scalar replacement.
 827  *
 828  * @param envals  The number of scalars.
 829  * @param repairs A set, that contains all blocks, that have a  link, and all Phis, that
 830  *                have copies to repair.
 831  * @param modes   A flexible array, containing all the modes of
 832  *                the value numbers.
 833  */
 834 static void do_scalar_replacements(int nvals, set * repairs, ir_mode **modes)
 835 {
 836   ir_node *end_block = get_irg_end_block(current_ir_graph);
 837   int i;
 838   int n = get_Block_n_cfgpreds(end_block);
 839   env_t env;
 840
 841   obstack_init(&env.obst);
 842   env.nvals = nvals;
 843   env.modes = modes;
 844
 845   /* Search for scalars.*/
 846   for (i = 0; i < n; ++i) {
 847     ir_node *pred = get_Block_cfgpred(end_block, i);
 848     if (get_irn_op(pred) != op_Block)
 849       memory_edge_walk(pred, &env, repairs);
 850   }
 851
 852   /* Search for predecessors of scalars.*/
 853   for (i = 0; i < n; ++i) {
 854     ir_node *pred = get_Block_cfgpred(end_block, i);
 855     if (get_irn_op(pred) != op_Block)
 856       memory_edge_walk2(pred, &env, repairs);
 857   }
 858   obstack_free(&env.obst, NULL);
 859 }
 860
 861 /*
 862  * Find possible scalar replacements
 863  *
 864  * @param irg  The current ir graph.
 865  */
 866 void find_scalar_replacements(ir_graph *irg)
 867 {
 868   unsigned nvals;
 869   int i;
 870   scalars_t key, *value;
 871   ir_node *irg_frame;
 872   ir_mode **modes;
 873   set *set_ent, *repairs;
 874   type *ent_type;
 875
 876   /* Call algorithm that computes the out edges */
 877   compute_outs(irg);
 878
 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 && "Neither an array nor a 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 }