3 * File name: ir/opt/scalar_replace.c
4 * Purpose: scalar replacement of arrays and compounds
5 * Author: Beyhan Veliev
8 * Copyright: (c) 1998-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
12 #include "scalar_replace.h"
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
25 * An access path, used to assign value numbers
26 * to variables that will be skalar replaced
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 */
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.*/
39 typedef struct _scalars_t{
40 entity *ent; /* A entity for scalar replacement.*/
41 type *ent_owner; /* The owner of this entity.*/
48 static int path_cmp(const void *elt, const void *key, size_t size)
50 const path_t *p1 = elt;
51 const path_t *p2 = key;
53 return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
57 * Compare two elements of the repairs_t set
59 static int set_cmp(const void *elt, const void *key, size_t size)
61 const repairs_t *c1 = elt;
62 const repairs_t *c2 = key;
64 return c1->irn != c2->irn;
68 * Compare two elements of the scalars_t set
70 static int ent_cmp(const void *elt, const void *key, size_t size)
72 const scalars_t *c1 = elt;
73 const scalars_t *c2 = key;
75 return c1->ent != c2->ent;
81 static unsigned path_hash(const path_t *path)
86 for (i = 0; i < path->path_len; ++i)
87 hash ^= (unsigned)path->path[i].ent;
93 * Returns non-zero, if all indeces of a Sel node are constants
95 * @param *sel The Sel node,that muss be chek.
97 static int is_const_sel(ir_node *sel) {
98 int i, n = get_Sel_n_indexs(sel);
100 for (i = 0; i < n; ++i) {
101 ir_node *idx = get_Sel_index(sel, i);
103 if (get_irn_op(idx) != op_Const)
110 * Returns non-zero, if the address of a sel (or it's succsessor sels is taken).
114 static int is_address_taken(type *ent_type, ir_node *sel)
118 if (! is_const_sel(sel))
121 n = get_irn_n_outs(sel);
122 for (i = 0; i < n; ++i) {
123 ir_node *succ = get_irn_out(sel, i);
125 switch (get_irn_opcode(succ)) {
130 /* check that Sel is not the store's value */
131 if (get_Store_value(succ) == sel)
136 /* Check the Sel successor of Sel */
137 int res = is_address_taken(ent_type, succ);
144 /* another op, the address is taken */
152 * link all leave Sels with the entity
154 * @param ent the entity that will be scalar replaced
155 * @param sel a Sel node that selects some fields of this entity
157 static void link_all_leave_sels(entity *ent, ir_node *sel)
161 n = get_irn_n_outs(sel);
162 for (i = 0; i < n; ++i) {
163 ir_node *succ = get_irn_out(sel, i);
165 if (get_irn_op(succ) == op_Sel) {
166 link_all_leave_sels(ent, succ);
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
175 set_irn_link(sel, get_entity_link(ent));
176 set_entity_link(ent, sel);
181 static void *ADDRESS_TAKEN = &_x;
184 * find possible scalar replacements
186 * @param irg an IR graph
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.
194 static void do_find_scalar_replacements(ir_graph *irg)
196 ir_node *irg_frame = get_irg_frame(irg);
199 n = get_irn_n_outs(irg_frame);
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);
205 if (get_irn_op(succ) == op_Sel) {
206 entity *ent = get_Sel_entity(succ);
207 set_entity_link(ent, NULL);
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);
216 if (get_irn_op(succ) == op_Sel) {
217 entity *ent = get_Sel_entity(succ);
218 type *ent_type = get_entity_type(ent);
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);
226 if (get_entity_link(ent) != ADDRESS_TAKEN)
227 link_all_leave_sels(ent, succ);
235 * return a path from the sel node sel to it's root
237 static path_t *find_path(ir_node *sel, unsigned len)
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);
246 if (get_irn_op(pred) != op_Sel) {
247 /* we found the root */
249 res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
253 res = find_path(pred, len);
255 pos = res->path_len - len;
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);
261 res->path[pos++].tv = get_Const_tarval(index);
268 * allocate value numbers for the leaves
269 * in our found entities
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
276 * @return the next free value number
278 static unsigned allocate_value_numbers(entity *ent, unsigned vnum, ir_mode ***modes)
282 set *pathes = new_set(path_cmp, 8);
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);
288 key = find_path(sel, 0);
289 path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
292 set_irn_link(sel, (void *)path->vnum);
298 set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
300 set_irn_link(sel, (void *)key->vnum);
301 ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15);
303 (*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel)));
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));
310 printf("[%ld]", get_tarval_long(key->path[i].tv));
312 printf(" = %u (%s)\n", (int)get_irn_link(sel), get_mode_name((*modes)[key->vnum]));
318 set_entity_link(ent, NULL);
323 static void *NODE_VISITED = &p;
325 static void * LOOP_WALK = &t;
327 static void *LOOP_HEAD_PHI = &s;
330 * environment for memory walker
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 */
339 static void *PRED_SEARCH = &q;
342 * Recursive walk over the blocks, that are predecessors of "node".
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.
353 static void pred_search(ir_node *node, repairs_t *value, set *repairs, int pos, int phi_pred)
355 ir_node *nodes_block;
356 repairs_t key, *value_pred;
358 nodes_block = get_nodes_block(node);
359 /* If the predecessor is faund. */
360 if((pos == -2 && value->link[pos] != NULL))
363 int i, n = get_Block_n_cfgpreds(nodes_block) ;
365 for (i = (n - 1); i >= 0; i--){
367 ir_node *pred = get_Block_cfgpred(nodes_block, i);
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);
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];
388 if(get_irn_op(value->link[pos]) == op_Phi && pos != -2 &&
389 value->link[pos] != value_pred->link[pos]){
391 set_Phi_pred(value->link[pos], phi_pred, value_pred->link[pos]);
400 if(get_irn_link(node) == PRED_SEARCH)
401 set_irn_link(node, NULL);
406 * Create a link for blocks, that have Phi, Load or Store nodes for scalar_replacement.
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.
413 static void block_link(ir_node *node, env_t *env, set *repairs)
415 repairs_t key, *value;
416 ir_node *nods_block ;
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){
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);
436 * Handle Phis, that get the memory edge of Loads or Stors, that were been scalar replaced or
437 * will be scalar replaced.
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.
446 static void phi_handling(ir_node *phi, env_t *env, set *repairs)
448 ir_node *phi_block, **link;
449 repairs_t key, *value;
452 value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
453 /* Test if the phi have been handled. */
457 int rem = get_optimize();
459 int p = 0, i, phi_preds;
460 phi_block = get_nodes_block(phi);
461 phi_preds = get_Phi_n_preds(phi);
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);
468 key.irn = pred_block;
469 value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
474 /* Phis from the loop head muss be handled.*/
475 if(get_irn_link(phi) == LOOP_HEAD_PHI)
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".*/
482 value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
487 if (get_irn_link(phi_block) == NULL)
488 block_link(phi, env, repairs);
490 link = get_irn_link(phi_block);
492 ir_node *in[phi_preds] ;
494 value = set_find(repairs, &key, sizeof(key), HASH_PTR(phi_block));
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
499 for(p = 0; p < env->nvals; p ++) {
501 for(i = 0; i < phi_preds; i++)
502 in[i] = new_Unknown(env->modes[p]);
505 value->link[p] = new_r_Phi(current_ir_graph, get_nodes_block(phi), phi_preds, in, env->modes[p]);
511 * Handle Loads, that were been scalar replaced or
512 * will be scalar replaced.
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.
521 static void load_handling(ir_node *load, env_t *env, set *repairs)
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);
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)
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);
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".*/
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);
550 if(value->link[i] == NULL)
551 pred_search(load, value, repairs, i, 0);
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());
566 * A walker along the memory edge. Load and Phi nodes muss be found for optimisation
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.
574 static void memory_edge_walk2(ir_node *node, env_t *env, set *repairs)
576 int i, p, n = get_irn_arity(node);
577 repairs_t key, *value, *value_block;
581 for (i = 0; i < n; i++){
583 ir_node *pred = get_irn_n(node, i);
585 if((get_irn_op(pred) == op_Proj &&
586 get_irn_mode(pred) == mode_M) ||
587 get_irn_mode(pred) == mode_T ||
589 get_irn_op(pred) == op_Call ||
590 get_irn_op(pred) == op_Alloc)
591 memory_edge_walk2(pred, env, repairs);
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);
601 if (get_irn_op(node) == op_Load)
602 load_handling(node, env, repairs);
604 if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
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.*/
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);
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);
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
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.
635 static void loop_walk(ir_node *node, env_t *env, set *repairs)
637 int i, p, n = get_irn_arity(node);
638 repairs_t key, *value, *value_block;
642 /* Test if the loop head have been achieved. */
643 if(has_backedges(get_nodes_block(node)))
646 for (i = 0; i < n; i++){
648 ir_node *pred = get_irn_n(node, i);
651 if((get_irn_op(pred) == op_Proj &&
652 get_irn_mode(pred) == mode_M) ||
653 get_irn_mode(pred) == mode_T ||
655 get_irn_op(pred) == op_Call ||
656 get_irn_op(pred) == op_Alloc)
657 loop_walk(pred, env, repairs);
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);
670 if (get_irn_op(node) == op_Load)
671 load_handling(node, env, repairs);
673 if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
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.*/
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);
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);
696 * Handle Stors, that were been scalar replaced or
697 * will be scalar replaced.
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.
705 static void store_handling(ir_node *store, env_t *env, set *repairs)
707 repairs_t key, *value;
708 ir_node *nods_block, *store_mem, *store_ptr, *store_value, **link, *phi;
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.*/
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) {
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)
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);
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));
732 set_irn_link(phi, LOOP_HEAD_PHI);
733 block_link(phi, env, repairs);
734 phi_handling(phi, env, repairs);
741 nods_block = get_nodes_block(store);
743 key.irn = nods_block;
744 value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
746 store_mem = get_Store_mem(store);
747 store_value = get_Store_value(store);
752 loop_walk(store, env, repairs);
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;
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());
764 set_irn_link(nods_block, link);
769 * A walker along the memory edge. Stors, Phis and their blocks as well Load's blocks muss be found for optimisation
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.
776 static void memory_edge_walk(ir_node *node, env_t *env, set *repairs)
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);
783 for (i = (n - 1); i >= 0; i--){
785 ir_node *pred = get_irn_n(node, i);
788 if((get_irn_op(pred) == op_Proj &&
789 get_irn_mode(pred) == mode_M) ||
791 get_irn_op(pred) == op_Call ||
792 get_irn_op(pred) == op_Alloc)
793 memory_edge_walk(pred, env, repairs);
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);
805 if (get_irn_op(node) == op_Store ||
806 get_irn_op(node) == op_Load)
807 block_link(node, env, repairs);
809 if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M)
810 phi_handling(node, env, repairs);
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);
823 * Make scalar replacement
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
831 static void do_scalar_replacements(int nvals, set * repairs, ir_mode **modes)
833 ir_node *end_block = get_irg_end_block(current_ir_graph);
835 int n = get_Block_n_cfgpreds(end_block);
838 obstack_init(&env.obst);
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);
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);
855 obstack_free(&env.obst, NULL);
860 * Find possible scalar replacements
862 * @param *irg The current ir graph.
864 void find_scalar_replacements(ir_graph *irg)
868 scalars_t key, *value;
872 /* Call algorithm that computes the out edges */
874 /* Call algorithm that computes the loop information */
875 construct_backedges(irg);
877 /* Call algorithm that computes the backedges */
878 construct_cf_backedges(irg);
880 /* Call algorithm that computes the dominator trees. */
883 /* Find possible scalar replacements */
884 do_find_scalar_replacements(irg);
886 printf("Called for %s\n", get_entity_name(get_irg_entity(irg)));
888 /* Insert in set the scalar replacemnts. */
889 irg_frame = get_irg_frame(irg);
891 modes = NEW_ARR_F(ir_mode *, 16);
892 set *set_ent = new_set(ent_cmp, 8);
894 for (i = 0 ; i < get_irn_n_outs(irg_frame); i++){
895 ir_node *succ = get_irn_out(irg_frame, i);
897 if( get_irn_op(succ) == op_Sel) {
898 entity *ent = get_Sel_entity(succ);
900 if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
903 type *ent_type = get_entity_type(ent);
906 key.ent_owner = get_entity_owner (ent);
907 set_insert(set_ent, &key, sizeof(key), HASH_PTR(key.ent));
909 if (is_Array_type(ent_type)) {
910 printf("<<<<<<<found array %s\n", get_entity_name(ent));
912 else if (is_Struct_type(ent_type)) {
913 printf("<<<<<<<found struct %s\n", get_entity_name(ent));
915 else if(is_atomic_type(ent_type))
916 printf("<<<<<<<found atomic value %s\n", get_entity_name(ent));
918 assert(0 && "\nDon't a array, struct or atomic value");
921 nvals = allocate_value_numbers(ent, nvals, &modes);
925 printf(" %u values will be needed\n", nvals);
927 /* A set for nodes that muss be repair. This are phi or unknown nodes. */
928 set *repairs = new_set(set_cmp, 8);
930 /* If scalars ware found. */
932 do_scalar_replacements(nvals, repairs, modes);
934 value = set_first(set_ent);
935 for (; value != NULL; value = set_next(set_ent))
936 remove_class_member (value->ent_owner, value->ent);