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