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.
23 #include "scalar_replace.h"
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
36 * An access path, used to assign value numbers
37 * to variables that will be skalar replaced
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 */
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. */
50 typedef struct _scalars_t {
51 entity *ent; /**< A entity for scalar replacement. */
52 type *ent_owner; /**< The owner of this entity. */
59 * @return 0 if they are identically
61 static int path_cmp(const void *elt, const void *key, size_t size)
63 const path_t *p1 = elt;
64 const path_t *p2 = key;
66 return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
70 * Compare two elements of the repairs_t set.
72 * @return 0 if they are identically
74 static int set_cmp(const void *elt, const void *key, size_t size)
76 const repairs_t *c1 = elt;
77 const repairs_t *c2 = key;
79 return c1->irn != c2->irn;
83 * Compare two elements of the scalars_t set.
85 * @return 0 if they are identically
87 static int ent_cmp(const void *elt, const void *key, size_t size)
89 const scalars_t *c1 = elt;
90 const scalars_t *c2 = key;
92 return c1->ent != c2->ent;
96 * Calculate a hash value for a path.
98 static unsigned path_hash(const path_t *path)
103 for (i = 0; i < path->path_len; ++i)
104 hash ^= (unsigned)path->path[i].ent;
110 * Returns non-zero, if all indeces of a Sel node are constants.
112 * @param sel the Sel node that will be checked
114 static int is_const_sel(ir_node *sel) {
115 int i, n = get_Sel_n_indexs(sel);
117 for (i = 0; i < n; ++i) {
118 ir_node *idx = get_Sel_index(sel, i);
120 if (get_irn_op(idx) != op_Const)
127 * Returns non-zero, if the address of a Sel node (or it's succsessor Sels) is taken.
129 * @param sel the Sel node
131 static int is_address_taken(type *ent_type, ir_node *sel)
135 if (! is_const_sel(sel))
138 n = get_irn_n_outs(sel);
139 for (i = 0; i < n; ++i) {
140 ir_node *succ = get_irn_out(sel, i);
142 switch (get_irn_opcode(succ)) {
147 /* check that Sel is not the store's value */
148 if (get_Store_value(succ) == sel)
153 /* Check the Sel successor of Sel */
154 int res = is_address_taken(ent_type, succ);
161 /* another op, the address is taken */
169 * Link all leave Sels with the entity.
171 * @param ent the entity that will be scalar replaced
172 * @param sel a Sel node that selects some fields of this entity
174 static void link_all_leave_sels(entity *ent, ir_node *sel)
178 n = get_irn_n_outs(sel);
179 for (i = 0; i < n; ++i) {
180 ir_node *succ = get_irn_out(sel, i);
182 if (get_irn_op(succ) == op_Sel) {
183 link_all_leave_sels(ent, succ);
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
192 set_irn_link(sel, get_entity_link(ent));
193 set_entity_link(ent, sel);
197 /* we need a special address that serves as an address taken marker */
199 static void *ADDRESS_TAKEN = &_x;
202 * Find possible scalar replacements.
204 * @param irg an IR graph
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.
212 static void do_find_scalar_replacements(ir_graph *irg)
214 ir_node *irg_frame = get_irg_frame(irg);
217 n = get_irn_n_outs(irg_frame);
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);
223 if (get_irn_op(succ) == op_Sel) {
224 entity *ent = get_Sel_entity(succ);
225 set_entity_link(ent, NULL);
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);
234 if (get_irn_op(succ) == op_Sel) {
235 entity *ent = get_Sel_entity(succ);
236 type *ent_type = get_entity_type(ent);
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);
244 if (get_entity_link(ent) != ADDRESS_TAKEN)
245 link_all_leave_sels(ent, succ);
253 * Return a path from the Sel node sel to it's root.
255 static path_t *find_path(ir_node *sel, unsigned len)
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);
264 if (get_irn_op(pred) != op_Sel) {
265 /* we found the root */
267 res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
271 res = find_path(pred, len);
273 pos = res->path_len - len;
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);
279 res->path[pos++].tv = get_Const_tarval(index);
286 * Allocate value numbers for the leaves
287 * in our found entities.
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
294 * @return the next free value number
296 static unsigned allocate_value_numbers(entity *ent, unsigned vnum, ir_mode ***modes)
300 set *pathes = new_set(path_cmp, 8);
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);
306 key = find_path(sel, 0);
307 path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
310 set_irn_link(sel, (void *)path->vnum);
316 set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
318 set_irn_link(sel, (void *)key->vnum);
319 ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15);
321 (*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel)));
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));
328 printf("[%ld]", get_tarval_long(key->path[i].tv));
330 printf(" = %u (%s)\n", (int)get_irn_link(sel), get_mode_name((*modes)[key->vnum]));
336 set_entity_link(ent, NULL);
341 static void *NODE_VISITED = &p;
343 static void *LOOP_WALK = &t;
345 static void *LOOP_HEAD_PHI = &s;
348 * environment for memory walker
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 */
357 static void *PRED_SEARCH = &q;
360 * Recursive walk over the blocks, that are predecessors of "node".
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.
371 static void pred_search(ir_node *node, repairs_t *value, set *repairs, int pos, int phi_pred)
373 ir_node *nodes_block;
374 repairs_t key, *value_pred;
378 nodes_block = get_nodes_block(node);
380 /* If the predecessor is found. */
381 if ((pos == -2 && value->link[pos] != NULL))
384 n = get_Block_n_cfgpreds(nodes_block);
386 for (i = n - 1; i >= 0; --i) {
387 ir_node *pred = get_Block_cfgpred(nodes_block, i);
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);
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];
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]);
420 if (get_irn_link(node) == PRED_SEARCH)
421 set_irn_link(node, NULL);
425 * Create a link for blocks, that have Phi, Load or Store nodes for scalar_replacement.
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.
432 static void block_link(ir_node *node, env_t *env, set *repairs)
434 repairs_t key, *value;
435 ir_node *nods_block ;
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) {
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);
454 * Handle Phis, that get the memory edge of Loads or Stors, that were been scalar replaced or
455 * will be scalar replaced.
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.
462 static void phi_handling(ir_node *phi, env_t *env, set *repairs)
464 ir_node *phi_block, **link;
465 repairs_t key, *value;
467 int p = 0, i, phi_preds;
471 value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
473 /* Test if the phi have been handled. */
477 rem = get_optimize();
479 phi_block = get_nodes_block(phi);
480 phi_preds = get_Phi_n_preds(phi);
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);
487 key.irn = pred_block;
488 value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
493 /* Phis from the loop head muss be handled.*/
494 if (get_irn_link(phi) == LOOP_HEAD_PHI)
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".*/
501 value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
507 if (get_irn_link(phi_block) == NULL)
508 block_link(phi, env, repairs);
510 link = get_irn_link(phi_block);
513 value = set_find(repairs, &key, sizeof(key), HASH_PTR(phi_block));
515 in = alloca(phi_preds * sizeof(*in));
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
520 for (p = 0; p < env->nvals; ++p) {
522 for (i = 0; i < phi_preds; ++i)
523 in[i] = new_Unknown(env->modes[p]);
526 value->link[p] = new_r_Phi(current_ir_graph, get_nodes_block(phi), phi_preds, in, env->modes[p]);
532 * Handle Loads, that were been scalar replaced or
533 * will be scalar replaced.
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.
540 static void load_handling(ir_node *load, env_t *env, set *repairs)
542 repairs_t key, *value;
543 ir_node *load_ptr, *load_mem, *nods_block;
546 nods_block = get_nodes_block(load);
547 load_ptr = get_Load_ptr(load);
548 load_mem = get_Load_mem(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)
557 key.irn = nods_block;
558 value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
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);
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 .*/
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);
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]);
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());
588 * A walker along the memory edge. Load and Phi nodes muss be found for optimization
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.
595 static void memory_edge_walk2(ir_node *node, env_t *env, set *repairs)
597 int i, p, n = get_irn_arity(node);
598 repairs_t key, *value, *value_block;
602 for (i = 0; i < n; i++) {
603 ir_node *pred = get_irn_n(node, i);
605 if((get_irn_op(pred) == op_Proj &&
606 get_irn_mode(pred) == mode_M) ||
607 get_irn_mode(pred) == mode_T ||
609 get_irn_op(pred) == op_Call ||
610 get_irn_op(pred) == op_Alloc)
611 memory_edge_walk2(pred, env, repairs);
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);
621 if (get_irn_op(node) == op_Load)
622 load_handling(node, env, repairs);
624 if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
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.*/
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);
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);
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
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.
655 static void loop_walk(ir_node *node, env_t *env, set *repairs)
657 int i, p, n = get_irn_arity(node);
658 repairs_t key, *value, *value_block;
662 /* Test if the loop head have been achieved. */
663 if (has_backedges(get_nodes_block(node)))
666 for (i = 0; i < n; i++) {
667 ir_node *pred = get_irn_n(node, i);
669 if((get_irn_op(pred) == op_Proj &&
670 get_irn_mode(pred) == mode_M) ||
671 get_irn_mode(pred) == mode_T ||
673 get_irn_op(pred) == op_Call ||
674 get_irn_op(pred) == op_Alloc)
675 loop_walk(pred, env, repairs);
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);
685 if (get_irn_op(node) == op_Load)
686 load_handling(node, env, repairs);
688 if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
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.*/
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);
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);
711 * Handle Stores that were been scalar replaced or
712 * will be scalar replaced.
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.
719 static void store_handling(ir_node *store, env_t *env, set *repairs)
721 repairs_t key, *value;
722 ir_node *nods_block, *store_mem, *store_ptr, *store_value, *phi;
725 store_ptr = get_Store_ptr(store);
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)
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));
743 set_irn_link(phi, LOOP_HEAD_PHI);
744 block_link(phi, env, repairs);
745 phi_handling(phi, env, repairs);
751 nods_block = get_nodes_block(store);
753 key.irn = nods_block;
754 value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
756 store_mem = get_Store_mem(store);
757 store_value = get_Store_value(store);
760 loop_walk(store, env, repairs);
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;
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());
775 * A walker along the memory edge. Stores, Phis and their blocks as well Load's blocks must be found for optimization
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.
782 static void memory_edge_walk(ir_node *node, env_t *env, set *repairs)
784 int i, n = get_irn_arity(node);
789 set_irn_link(get_nodes_block(node), NULL);
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);
795 if ((op == op_Proj &&
796 get_irn_mode(pred) == mode_M) ||
801 memory_edge_walk(pred, env, repairs);
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);
811 op = get_irn_op(node);
812 if (op == op_Store || op == op_Load)
813 block_link(node, env, repairs);
815 if (op == op_Phi && get_irn_mode(node) == mode_M)
816 phi_handling(node, env, repairs);
819 store_handling(node, env, repairs);
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);
827 * Make scalar replacement.
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
835 static void do_scalar_replacements(int nvals, set * repairs, ir_mode **modes)
837 ir_node *end_block = get_irg_end_block(current_ir_graph);
839 int n = get_Block_n_cfgpreds(end_block);
842 obstack_init(&env.obst);
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);
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);
859 obstack_free(&env.obst, NULL);
863 * Find possible scalar replacements
865 * @param irg The current ir graph.
867 void find_scalar_replacements(ir_graph *irg)
871 scalars_t key, *value;
874 set *set_ent, *repairs;
877 /* Call algorithm that computes the out edges */
879 /* Call algorithm that computes the loop information */
880 construct_backedges(irg);
882 /* Call algorithm that computes the backedges */
883 construct_cf_backedges(irg);
885 /* Call algorithm that computes the dominator trees. */
888 /* Find possible scalar replacements */
889 do_find_scalar_replacements(irg);
891 printf("Called for %s\n", get_entity_name(get_irg_entity(irg)));
893 /* Insert in set the scalar replacemnts. */
894 irg_frame = get_irg_frame(irg);
896 modes = NEW_ARR_F(ir_mode *, 16);
897 set_ent = new_set(ent_cmp, 8);
899 for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) {
900 ir_node *succ = get_irn_out(irg_frame, i);
902 if (get_irn_op(succ) == op_Sel) {
903 entity *ent = get_Sel_entity(succ);
905 if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
908 ent_type = get_entity_type(ent);
911 key.ent_owner = get_entity_owner (ent);
912 set_insert(set_ent, &key, sizeof(key), HASH_PTR(key.ent));
914 if (is_Array_type(ent_type)) {
915 printf("<<<<<<<found array %s\n", get_entity_name(ent));
917 else if (is_Struct_type(ent_type)) {
918 printf("<<<<<<<found struct %s\n", get_entity_name(ent));
920 else if(is_atomic_type(ent_type))
921 printf("<<<<<<<found atomic value %s\n", get_entity_name(ent));
923 assert(0 && "\nDon't a array, struct or atomic value");
926 nvals = allocate_value_numbers(ent, nvals, &modes);
930 printf(" %u values will be needed\n", nvals);
932 /* A set of nodes that must be repaired. These are Phi or Unknown nodes. */
933 repairs = new_set(set_cmp, 8);
935 /* If scalars ware found. */
937 do_scalar_replacements(nvals, repairs, modes);
939 value = set_first(set_ent);
940 for (; value != NULL; value = set_next(set_ent))
941 remove_class_member(value->ent_owner, value->ent);