2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief scalar replacement of arrays and compounds
23 * @author Beyhan Veliev, Michael Beck
30 #include "iroptimize.h"
44 #include "analyze_irg_args.h"
49 #define SET_ENT_VNUM(ent, vnum) set_entity_link(ent, INT_TO_PTR(vnum))
50 #define GET_ENT_VNUM(ent) (unsigned)PTR_TO_INT(get_entity_link(ent))
51 #define SET_IRN_VNUM(irn, vnum) set_irn_link(irn, INT_TO_PTR(vnum))
52 #define GET_IRN_VNUM(irn) (unsigned)PTR_TO_INT(get_irn_link(irn))
56 typedef struct _ent_leaves_t{
57 ir_entity *ent; /**< An entity, that contains scalars for replace.*/
58 pset *leaves; /**< All leaves of this entity.*/
61 typedef struct _sels_t {
62 ir_node *sel; /**< A sel node, thats entity have scalars.*/
63 ir_entity *ent; /**< The entity of this sel node.*/
66 typedef struct _call_access_t {
67 ir_node *call; /**< A call node, that have as parameter a scalar.*/
68 unsigned int access_type; /**< The access type, with that this call access this scalar.*/
71 typedef struct _fixlist_entry_t {
72 ir_node *irn; /**< An ir node, that must be fixed.*/
73 unsigned int vnum; /**< The value number, that must became this ir node.*/
76 typedef struct _syncs_fixlist_entry_t {
77 ir_node *irn; /**< A sync node that must be fixed.*/
78 int *accessed_vnum; /**< A pointer to save an array with value numbers, that must became this sync.*/
79 }syncs_fixlist_entry_t;
81 /* A entry, that save the memory
82 * edge state and the access state for this leave
83 * int the array,that is created for every block.*/
84 typedef struct _leave_t {
85 ir_node *mem_edge_state; /**< memory state for this scalar in this block.*/
86 unsigned int access_type; /**< access state for this scalar in this block.*/
87 set *calls; /**< call nodes,that change this scalar in this block.*/
91 * A path element entry: it is either an entity
92 * or a tarval, because we evaluate only constant array
93 * accesses like a.b.c[8].d
101 * An access path, used to assign value numbers
102 * to variables that will be scalar replaced
104 typedef struct _path_t {
105 unsigned vnum; /**< the value number */
106 unsigned path_len; /**< the length of the access path */
107 path_elem_t path[1]; /**< the path */
111 * environment for memory walker
113 typedef struct _env_t {
114 struct obstack obst; /**< a obstack for the memory edge */
115 set *set_sels; /**< a set with all sels, that are reachable from an entity with a scalar.*/
116 set *set_ent; /**< a set with all entities that have one or more scalars.*/
117 fixlist_entry_t *fix_phis; /**< list of all Phi nodes that must be fixed */
118 fixlist_entry_t *fix_ls; /**< list of all Load or Store nodes that must be fixed */
119 syncs_fixlist_entry_t *fix_syncs; /**< list of all Sync nodes that must be fixed */
120 unsigned int nvals; /**< to save the number of scalars.*/
121 unsigned int gl_mem_vnum; /**< indicate the position of the globule memory edge state in var_arr.*/
122 unsigned int vnum_state; /**< indicate the position of the value number state in var_arr.*/
123 unsigned int changes; /**< to save if by anlyse_calls is changed anything.*/
129 * Compare two elements of the ent_leaves_t set.
131 * @return 0 if they are identically
133 static int ent_leaves_t_cmp(const void *elt, const void *key, size_t size)
135 const ent_leaves_t *c1 = elt;
136 const ent_leaves_t *c2 = key;
139 return c1->ent != c2->ent;
143 * Compare two elements of the ent_access_t set.
145 * @return 0 if they are identically
147 static int ent_cmp(const void *elt, const void *key)
149 const ir_entity *c1 = elt;
150 const ir_entity *c2 = key;
156 * Compare two elements of the sels_t set.
158 * @return 0 if they are identically
160 static int sels_cmp(const void *elt, const void *key, size_t size)
162 const sels_t *c1 = elt;
163 const sels_t *c2 = key;
166 return c1->sel != c2->sel;
170 * Compare two elements of the leave_t set.
172 * @return 0 if they are identically
174 static int leave_cmp(const void *elt, const void *key)
176 ir_node *c1 = (ir_node *)elt;
177 ir_node *c2 = (ir_node *)key;
179 return get_Sel_entity(c1) != get_Sel_entity(c2);
183 * Compare two elements of the call_access_t set.
185 * @return 0 if they are identically
187 static int call_cmp(const void *elt, const void *key, size_t size)
189 const call_access_t *c1 = elt;
190 const call_access_t *c2 = key;
193 return c1->call != c2->call;
199 * @return 0 if they are identically
201 static int path_cmp(const void *elt, const void *key, size_t size)
203 const path_t *p1 = elt;
204 const path_t *p2 = key;
207 /* we can use memcmp here, because identical tarvals should have identical addresses */
208 return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
212 * Calculate a hash value for a path.
214 static unsigned path_hash(const path_t *path)
219 for (i = 0; i < path->path_len; ++i)
220 hash ^= (unsigned)PTR_TO_INT(path->path[i].ent);
226 * Returns non-zero, if all induces of a Sel node are constants.
228 * @param sel the Sel node that will be checked
230 static int is_const_sel(ir_node *sel) {
231 int i, n = get_Sel_n_indexs(sel);
233 for (i = 0; i < n; ++i) {
234 ir_node *idx = get_Sel_index(sel, i);
243 * Returns non-zero, if the address of an entity
244 * represented by a Sel node (or it's successor Sels) is taken.
246 static int is_address_taken_2(ir_node *sel)
250 if (! is_const_sel(sel))
253 for (i = get_irn_n_outs(sel) - 1; i >= 0; --i) {
254 ir_node *succ = get_irn_out(sel, i);
256 switch (get_irn_opcode(succ)) {
258 /* ok, we just load from that entity */
262 /* check that Sel is not the Store's value */
263 if (get_Store_value(succ) == sel)
268 /* Check the Sel successor of Sel */
269 int res = is_address_taken_2(succ);
277 /* The address of an entity is given as a parameter.
278 * We analyzes that later and optimizes this scalar
284 /* another op, the address is taken */
292 * Link all Sels with the entity.
294 * @param ent the entity that will be scalar replaced
295 * @param sel a Sel node that selects some fields of this entity
297 static void link_all_leave_sels(ir_entity *ent, ir_node *sel)
301 n = get_irn_n_outs(sel);
302 for (i = 0; i < n; ++i) {
303 ir_node *succ = get_irn_out(sel, i);
306 link_all_leave_sels(ent, succ);
309 /* if Sel nodes with memory inputs are used, a entity can be
310 * visited more than once causing a ring here, so we use the
311 * node flag to mark linked nodes
313 if (irn_visited(sel))
317 * we link the sels to the entity.
319 set_irn_link(sel, get_entity_link(ent));
320 set_entity_link(ent, sel);
322 mark_irn_visited(sel);
325 /* we need a special address that serves as an address taken marker */
327 static void *ADDRESS_TAKEN = &_x;
330 * Find possible scalar replacements.
332 * @param irg an IR graph
334 * This function finds variables on the (members of the) frame type
335 * that can be scalar replaced, because their address is never taken.
336 * If such a variable is found, it's entity link will hold a list of all
337 * Sel nodes, that selects anythings of this entity.
338 * Otherwise, the link will be ADDRESS_TAKEN or NULL.
340 * @return non-zero if at least one entity could be replaced
343 static int find_possible_replacements(ir_graph *irg)
345 ir_node *irg_frame = get_irg_frame(irg);
349 inc_irg_visited(irg);
351 n = get_irn_n_outs(irg_frame);
354 * First, clear the link field of all interestingentities.
355 * Note that we did not rely on the fact that there is only
356 * one Sel node per entity, so we might access one entity
357 * more than once here.
358 * That's why we have need two loops.
360 for (i = 0; i < n; ++i) {
361 ir_node *succ = get_irn_out(irg_frame, i);
364 ir_entity *ent = get_Sel_entity(succ);
365 set_entity_link(ent, NULL);
370 * Check the ir_graph for Sel nodes. If the entity of Sel
371 * isn't a scalar replacement set the link of this entity
372 * equal ADDRESS_TAKEN.
374 for (i = 0; i < n; ++i) {
375 ir_node *succ = get_irn_out(irg_frame, i);
378 ir_entity *ent = get_Sel_entity(succ);
381 if (get_entity_link(ent) == ADDRESS_TAKEN)
385 * Beware: in rare cases even entities on the frame might be
386 * volatile. This might happen if the entity serves as a store
387 * to a value that must survive a exception. Do not optimize
388 * such entities away.
390 if (get_entity_volatility(ent) == volatility_is_volatile) {
391 set_entity_link(ent, ADDRESS_TAKEN);
395 ent_type = get_entity_type(ent);
397 /* we can handle arrays, structs and atomic types yet */
398 if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
399 if (is_address_taken_2(succ)) {
400 if (get_entity_link(ent)) /* killing one */
402 set_entity_link(ent, ADDRESS_TAKEN);
405 /* possible found one */
406 if (get_entity_link(ent) == NULL)
408 link_all_leave_sels(ent, succ);
417 static int is_leave_sel(ir_node *sel) {
421 for(i = get_irn_n_outs(sel) - 1; i >= 0; i--) {
422 succ = get_irn_out(sel, i);
431 * Return a path from the Sel node sel to it's root.
433 * @param sel the Sel node
434 * @param len the length of the path so far
436 static path_t *find_path(ir_node *sel, unsigned len)
440 ir_node *pred = get_Sel_ptr(sel);
442 /* the current Sel node will add some path elements */
443 n = get_Sel_n_indexs(sel);
447 /* we found the root */
449 res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
453 res = find_path(pred, len);
455 pos = res->path_len - len;
457 res->path[pos++].ent = get_Sel_entity(sel);
458 for (i = 0; i < n; ++i) {
459 ir_node *index = get_Sel_index(sel, i);
462 res->path[pos++].tv = get_Const_tarval(index);
468 * Allocate value numbers for the leaves
469 * in our found entities.
471 * @param sels a set that will contain all Sels that have a value number
472 * @param ent the entity that will be scalar replaced
473 * @param vnum the first value number we can assign
474 * @param modes a flexible array, containing all the modes of
477 * @return the next free value number
479 static unsigned allocate_value_numbers(set *set_sels, pset *leaves, ir_entity *ent, unsigned vnum)
484 set *pathes = new_set(path_cmp, 8);
486 /* visit all Sel nodes in the chain of the entity */
487 for (sel = get_entity_link(ent); sel; sel = next) {
488 next = get_irn_link(sel);
490 /* we save for every sel it root entity, why
491 * we need this information, when we split the memory edge,
492 * and we must mark this sel for later. */
495 set_insert(set_sels, &key_sels, sizeof(key_sels), HASH_PTR(sel));
497 if(! is_leave_sel(sel))
499 /* We have found a leave and we add it to the pset of this entity.*/
500 pset_insert(leaves, sel, HASH_PTR(get_Sel_entity(sel)));
502 key = find_path(sel, 0);
503 path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
506 SET_IRN_VNUM(sel, path->vnum);
511 set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
513 SET_IRN_VNUM(sel, key->vnum);
519 set_entity_link(ent, NULL);
523 * Add a sync node to it fix list.
525 * @param sync The sync node, that myst be addet to the fix list.
526 * @param unk_vnum An array whit the value number, that are synced with this sync node.
527 * @param env The enviroment pinter.
529 static void add_sync_to_fixlist(ir_node *sync, int *unk_vnum, env_t *env) {
531 syncs_fixlist_entry_t *s;
533 s = obstack_alloc(&env->obst, sizeof(*s));
535 s->accessed_vnum = unk_vnum;
536 set_irn_link(sync, env->fix_syncs);
540 * Add a ir node to it fix list.
542 * @param irn The ir node, that myst be addet to the fix list.
543 * @param vnum The value number, that must baceme this ir node as predecessor later.
544 * @param env The enviroment pinter.
546 static void add_ls_to_fixlist(ir_node *irn, int vnum, env_t *env) {
550 l = obstack_alloc(&env->obst, sizeof(*l));
554 if(get_irn_op(irn) == op_Phi) {
555 set_irn_link(l->irn, env->fix_phis);
558 set_irn_link(l->irn, env->fix_ls);
563 static void add_mem_edge(value_arr_entry_t *val_arr, int vnum, ir_node ***in, int **accessed_vnum) {
565 if(val_arr[vnum].mem_edge_state != NULL)
566 ARR_APP1(ir_node *, *in, val_arr[vnum].mem_edge_state);
568 ARR_APP1(int, *accessed_vnum, vnum);
569 ARR_APP1(ir_node *, *in, new_Unknown(mode_M));
573 * The function handles the scalars, that wase stored
576 * @param blk The block, that must be handled.
577 * @param env The enviroment pinter.
580 /* Return the memory successor of the call node.*/
581 static ir_node *get_Call_mem_out(ir_node *call) {
586 for(i = get_irn_n_outs(call) - 1; i >= 0; i--) {
587 mem = get_irn_out(call, i);
588 if(get_irn_mode(mem) == mode_M)
591 /* is not reachable*/
596 static void sync_stored_scalars(ir_node *blk, env_t *env) {
599 int *unk_vnum; /**< An arraw, where are saved the value number, that
600 are synced from this sync node.*/
601 ent_leaves_t *value_ent;
602 value_arr_entry_t *val_arr_blk, *val_arr;
603 ir_node *pred, *leave, *sync, **in;
604 ir_node *sync_blk; /**< The block, where the sync node must be created.*/
607 val_arr_blk = get_irn_link(blk);
609 for(value_ent = set_first(env->set_ent); value_ent; value_ent = set_next(env->set_ent)) {
612 if(val_arr_blk[GET_ENT_VNUM(value_ent->ent)].access_type <= 3)
613 /* This entity is not stored in this block.*/
616 for(i = get_Block_n_cfgpreds(blk) - 1; i >= 0; i--) {
618 pred = get_Block_cfgpred(blk, i);
619 pred = get_nodes_block(pred);
620 val_arr = get_irn_link(pred);
622 if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type == SYNCED)
623 /* This entity was synced.*/
626 if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type <= 3) {
628 /* To avoid repeated sync of this entity in this block.*/
629 val_arr[GET_ENT_VNUM(value_ent->ent)].access_type = SYNCED;
630 /* In this predecessor block is this entity not acessed.
631 * We must sync in the end ot this block.*/
632 if(get_Block_n_cfgpreds(blk) > 1)
633 sync_blk = get_nodes_block(get_Block_cfgpred(blk, i));
637 val_arr = get_irn_link(sync_blk);
638 /* An array to save the memory edges, that must be
640 in = NEW_ARR_F(ir_node *, 1);
642 /* An array to save the value numbers,
643 * that must be repaired.*/
644 unk_vnum = NEW_ARR_F(int, 0);
645 /* The global memory edge.*/
646 if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL)
647 in[0] = new_Unknown(mode_M);
649 in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
651 for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves))
652 /* All this memory edges must be synced.*/
653 add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &unk_vnum);
655 /* We create the sync and set it in the global memory state.*/
656 sync = new_r_Sync(current_ir_graph, sync_blk, ARR_LEN(in), in);
657 /* We must check this, why it is possible to get a Bad node
658 * form new_r_Sync(), when the node can be optimized.
659 * In this case we must do nothing.*/
661 val_arr[env->gl_mem_vnum].mem_edge_state = sync;
662 /* We add this sync node to the sync's fix list.*/
663 add_sync_to_fixlist(val_arr[env->gl_mem_vnum].mem_edge_state, unk_vnum, env);
671 * The function split the memory edge of load and store nodes, that have
672 * as predecessor a scalar
674 * @param irn The node, that memory edge must be spleted.
675 * @param env The enviroment pinter.
677 static void split_ls_mem_edge(ir_node *irn, env_t *env) {
680 ir_node *leave, *irn_blk, *mem_state, *new_mem_state;
681 unsigned ent_vnum, sel_vnum, i;
682 value_arr_entry_t *val_arr;
683 sels_t key_sels, *value_sels;
684 ent_leaves_t key_ent, *value_ent;
686 op = get_irn_op(irn);
689 key_sels.sel = get_Load_ptr(irn);
691 key_sels.sel = get_Store_ptr(irn);
693 value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
695 if(value_sels != NULL) {
696 /* we have found a load or store, that use a sel of our set
697 * and we must split or extend, if the memory edge have been
698 * split for this sel, the memory edge.*/
700 key_ent.ent = value_sels->ent;
701 value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
702 /*To check if the enities set is right filled. */
703 assert(value_ent && " This sel's entity isn't int the entity set.");
705 leave = pset_find(value_ent->leaves, key_sels.sel, HASH_PTR(get_Sel_entity(key_sels.sel)));
706 /*To check if the leaves set is right filled. */
707 assert(leave && "Anything in data_flow_scalar_replacment algorithm is wrong.");
709 ent_vnum = GET_ENT_VNUM(value_ent->ent);
710 sel_vnum = GET_IRN_VNUM(leave);
711 irn_blk = get_nodes_block(irn);
712 val_arr = get_irn_link(irn_blk);
714 if(val_arr[ent_vnum].access_type == 0)
715 /* We have found a scalar, that address is not stored as jet.*/
718 /* This scalar have been stored.*/
719 i = env->gl_mem_vnum;
721 if(val_arr[i].mem_edge_state == NULL) {
722 /* We split now for this sel the memory edge in this block.*/
723 mem_state = new_Unknown(mode_M);
724 /* We must mark this node to fix later*/
725 add_ls_to_fixlist(irn, i, env);
728 /* We have split the memory edge and the current state is saved.*/
729 mem_state = val_arr[i].mem_edge_state;
731 /* We set this Load or Store to the memory edge of this
734 set_Load_mem(irn, mem_state);
736 set_Store_mem(irn, mem_state);
738 /* When we have split or extended the memory edge we must
739 * update the memory_edge_state of this sel*/
740 new_mem_state = get_irn_out(irn, 0);
741 if(get_irn_mode(new_mem_state) == mode_M)
742 val_arr[i].mem_edge_state = new_mem_state;
744 val_arr[i].mem_edge_state = get_irn_out(irn, 1);
749 * The function split the memory edge of phi nodes, that have
750 * as predecessor a scalar
752 * @param irn The phi node, that memory edge must be spleted.
753 * @param env The enviroment pinter.
755 static void split_phi_mem_edge(ir_node *irn, env_t *env) {
757 ir_node *irn_blk, *unk, *leave, **in;
759 ent_leaves_t *value_ent;
760 value_arr_entry_t *val_arr;
762 irn_blk = get_nodes_block(irn);
763 val_arr = get_irn_link(irn_blk);
765 n = get_Block_n_cfgpreds(irn_blk);
767 in = alloca(sizeof(*in) * n);
769 for(value_ent = set_first(env->set_ent); value_ent; value_ent = set_next(env->set_ent))
770 if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type < 3)
771 /* This scalar wasn't be saved and we need to produce a phi for it.*/
772 for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves)){
774 unk = new_Unknown(mode_M);
775 for (j = n - 1; j >= 0; --j)
778 val_arr[GET_IRN_VNUM(leave)].mem_edge_state = new_r_Phi(current_ir_graph, irn_blk, n, in, mode_M);
780 add_ls_to_fixlist(val_arr[GET_IRN_VNUM(leave)].mem_edge_state, GET_IRN_VNUM(leave), env);
783 /* We use for the global memory the phi node, that
784 * is already available.*/
785 val_arr[env->gl_mem_vnum].mem_edge_state = irn;
789 * The function handles the call nodes, that have
790 * as parameter a scalar
792 * @param env The enviroment pinter.
793 * @param call The call node, that must be handled.
794 * @param accessed_entities A set wit all entities, that are accessed from this call node.*/
795 static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entities) {
797 ent_leaves_t key_ent, *value_ent;
798 value_arr_entry_t *val_arr;
799 call_access_t key_call, *value_call;
800 ir_node *call_blk, *new_mem_state, *leave;
804 int fix_irn = 0; /**< Set to 1 if we must add this call to it fix list.*/
805 int *accessed_leaves_vnum = NULL; /**< An arraw, where are saved the value number, that
806 are synced from call's sync node, if we need it.*/
808 call_blk = get_nodes_block(call);
809 val_arr = get_irn_link(call_blk);
810 /* An array to save the memory edges, that must be
812 in = NEW_ARR_F(ir_node *, 1);
813 /* An array to save the value numbers of the memory
814 * edges that must be repaired.*/
815 accessed_leaves_vnum = NEW_ARR_F(int, 0);
817 /* We get the memory successor of the call node.
818 * It is the new memory state for all synced memory
820 new_mem_state = get_Call_mem_out(call);
822 /* The global memory is the first predecessor of the create sync node.*/
823 if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) {
824 in[0] = new_Unknown(mode_M);
828 in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
831 for(ent = pset_first(accessed_entities); ent; ent = pset_next(accessed_entities)) {
832 /* Whit this loop we iterate all accessed entities from this call and collect
833 * all memory edges, that we must sync.*/
834 ent_vnum = GET_ENT_VNUM(ent);
836 key_call.call = call;
837 value_call = set_find(val_arr[ent_vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
840 value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
842 if(val_arr[ent_vnum].access_type <= 3) {
843 /* This scalar's address wasn't stored in this block.*/
844 switch(value_call->access_type) {
846 case ptr_access_none :
847 /* In this case we have nothing to do.*/
850 case ptr_access_read:
851 case ptr_access_write:
853 /* All this cases must be traded equal.*/
855 for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves)){
856 /* All this memory edges must be synced.*/
857 add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &accessed_leaves_vnum);
859 /* We update the memory state of this leave.*/
860 if(value_call->access_type != ptr_access_read)
861 val_arr[GET_IRN_VNUM(leave)].mem_edge_state = new_mem_state;
870 /* We must update the global memory state.*/
871 val_arr[env->gl_mem_vnum].mem_edge_state = new_mem_state;
873 if(ARR_LEN(in) == 1) {
874 /* we must set the call memory to gobale momory*/
875 set_Call_mem(call,in[0]);
878 /* We add this call node to the call fix list..*/
879 add_ls_to_fixlist(call, env->gl_mem_vnum, env);
882 /* We create the sync and set it as memory predecessor of the call node.*/
883 sync = new_r_Sync(current_ir_graph, call_blk, ARR_LEN(in), in);
884 /* We must check this, why it is possible to get a Bad node
885 * form new_r_Sync(), when the node can be optimized.
886 * In this case we must do nothing.*/
888 set_Call_mem(call, sync);
889 if(ARR_LEN(accessed_leaves_vnum))
890 /* We add this sync node to the sync's fix list.*/
891 add_sync_to_fixlist(sync, accessed_leaves_vnum, env);
898 * The function split the memory edge from the passed
899 * ir node if this is needed
901 * @param irn The node, that memory edge must be spleted.
902 * @param env The enviroment pinter.
904 static void split_memory_edge(ir_node *irn, void *ctx) {
907 ir_node *sel, *irn_blk;
909 sels_t key_sels, *value_sels;
910 value_arr_entry_t *val_arr;
911 pset *accessed_entities; /**< A set to save all entities accessed from a call.*/
915 op = get_irn_op(irn);
920 irn_blk = get_nodes_block(irn);
922 if (!Block_block_visited(irn_blk)) {
923 /* We sync first the stored scalar address in this block.*/
924 mark_Block_block_visited(irn_blk);
925 sync_stored_scalars(irn_blk, env);
928 if(op == op_Load || op == op_Store)
930 split_ls_mem_edge(irn, env);
933 if (op == op_Phi && get_irn_mode(irn) == mode_M) {
935 * found a memory Phi: Here, we must create new Phi nodes
937 split_phi_mem_edge(irn, env);
942 /* Calls that have a NoMem input do neither read nor write memory.
943 We can completely ignore them here. */
944 if (is_NoMem(get_Call_mem(irn)))
947 /* We save in this set all entities,
948 * that are accessed from this call node.*/
949 accessed_entities = new_pset(ent_cmp, 8);
950 val_arr = get_irn_link(get_nodes_block(irn));
952 for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
954 sel = get_Call_param(irn, i);
958 value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
960 if(value_sels != NULL && val_arr[GET_ENT_VNUM(value_sels->ent)].access_type <= 3)
961 /* We save in this set all accessed entities from this call node whit
962 * access none, read, write or rw..*/
963 pset_insert(accessed_entities, value_sels->ent, HASH_PTR(value_sels->ent));
967 if(pset_count(accessed_entities))
968 split_call_mem_edge(env, irn, accessed_entities);
970 del_pset(accessed_entities);
977 * searches through blocks beginning from block for value
978 * vnum and return it.
980 * @param block A block from the current ir graph.
981 * @param vnum The value number, that must be found.
983 static ir_node *find_vnum_value(ir_node *block, unsigned vnum)
985 value_arr_entry_t *val_arr;
989 if (!Block_block_visited(block)) {
990 mark_Block_block_visited(block);
992 val_arr = get_irn_link(block);
994 if (val_arr[vnum].mem_edge_state)
995 return val_arr[vnum].mem_edge_state;
997 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
998 ir_node *pred = get_Block_cfgpred(block, i);
1000 res = find_vnum_value(get_nodes_block(pred), vnum);
1009 * fix the Load/Store or Call list
1011 * @param The enviroment pinter.
1013 static void fix_ls(env_t *env)
1016 ir_node *irn, *block, *pred, *val = NULL;
1020 for (l = env->fix_ls; l; l = get_irn_link(irn)) {
1023 op = get_irn_op(irn);
1024 block = get_nodes_block(irn);
1025 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
1026 pred = get_Block_cfgpred(block, i);
1027 pred = get_nodes_block(pred);
1029 inc_irg_block_visited(current_ir_graph);
1030 val = find_vnum_value(pred, l->vnum);
1038 set_Store_mem(irn, val);
1041 set_Load_mem(irn, val);
1043 set_Call_mem(irn, val);
1051 * @param The enviroment pinter.
1053 static void fix_phis(env_t *env)
1056 ir_node *phi, *block, *pred, *val;
1059 for (l = env->fix_phis; l; l = get_irn_link(phi)) {
1062 block = get_nodes_block(phi);
1063 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
1065 pred = get_Block_cfgpred(block, i);
1066 pred = get_nodes_block(pred);
1068 inc_irg_block_visited(current_ir_graph);
1069 val = find_vnum_value(pred, l->vnum);
1072 set_irn_n(phi, i, val);
1081 * @param The enviroment pinter.
1083 static void fix_syncs(env_t *env)
1085 syncs_fixlist_entry_t *l;
1086 ir_node *sync, *block, *pred, *val;
1090 for (l = env->fix_syncs; l; l = get_irn_link(sync)) {
1094 /* The sync block must have one predecessor, when it
1095 have unknown nodes as predecessor.*/
1096 block = get_nodes_block(sync);
1097 pred = get_Block_cfgpred(block, 0);
1098 pred = get_nodes_block(pred);
1100 /* We first repair the global memory edge at the first position of sync predecessors.*/
1101 if (is_Unknown(get_irn_n(sync, 0))) {
1102 inc_irg_block_visited(current_ir_graph);
1103 val = find_vnum_value(pred, env->gl_mem_vnum);
1106 set_irn_n(sync, 0, val);
1109 for (i = get_irn_arity(sync) - 1; i >= 1; --i) {
1110 /* We repair the leaves*/
1112 assert(k <= ARR_LEN(l->accessed_vnum) && "The algorythm for sync repair is wron");
1113 if (is_Unknown(get_irn_n(sync, i))) {
1114 inc_irg_block_visited(current_ir_graph);
1115 val = find_vnum_value(pred, l->accessed_vnum[k++]);
1118 set_irn_n(sync, i, val);
1121 DEL_ARR_F(l->accessed_vnum);
1125 * For the end node we must sync all memory edges.
1127 * @param The enviroment pinter.
1129 static void sync_mem_edges(env_t *env) {
1131 value_arr_entry_t *val_arr;
1132 ir_node **in, *sync, *Return, *Return_blk;
1133 int i, vnum, vnum_state;
1135 Return = get_Block_cfgpred(get_irg_end_block(current_ir_graph), 0);
1136 Return_blk = get_nodes_block(Return);
1137 val_arr = get_irn_link(Return_blk);
1141 for(i = 0; i <= (int)env->gl_mem_vnum; i++)
1142 /* we get the current state of non saved scalars.*/
1143 if(val_arr[i].access_type <= 3)
1146 /* We allocate the memory, that we need for the predecessors of the sync.*/
1147 in = xmalloc(sizeof(ir_node*) *vnum_state);
1149 /* The global memory edge is the first predecessor of this sync node.*/
1150 if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) {
1151 /* We must search through blocks for this memory state.*/
1152 inc_irg_block_visited(current_ir_graph);
1153 in[0] = find_vnum_value(Return_blk, env->gl_mem_vnum);
1156 in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
1159 for(i = 1, vnum = 0; vnum < (int)env->gl_mem_vnum; vnum++) {
1161 if(val_arr[vnum].access_type <= 3) {
1162 /* we add the non saved scalars as predecessors of the sync.*/
1164 if(val_arr[vnum].mem_edge_state == NULL) {
1165 /* We must search through blocks for this memory state.*/
1166 inc_irg_block_visited(current_ir_graph);
1167 in[i] = find_vnum_value(Return_blk, vnum);
1170 in[i] = val_arr[vnum].mem_edge_state;
1175 sync = new_r_Sync(current_ir_graph, Return_blk, vnum_state, in);
1176 set_Return_mem(Return, sync);
1182 * Walker: allocate the value array for every block.
1184 * @param block A block from the current ir graph for that must be allocated a value array.
1185 * @param ctx The enviroment pinter.
1187 static void alloc_value_arr(ir_node *block, void *ctx)
1192 value_arr_entry_t *var_arr = obstack_alloc(&env->obst, sizeof(value_arr_entry_t) *(env->nvals + set_count(env->set_ent) + 1));
1194 /* the value array is empty at start */
1195 memset(var_arr, 0, sizeof(value_arr_entry_t) * (env->nvals + set_count(env->set_ent) + 1));
1196 set_irn_link(block, var_arr);
1198 /* We set the block value number state to optimal and later we update this.*/
1199 var_arr[env->vnum_state].access_type = env->nvals;
1201 if(get_irg_start_block(current_ir_graph) == block)
1202 /* We initilize the startblocks array with the irg initilize memory, why
1203 * it must be the start point of all memory edges.*/
1204 for(i = (env->nvals + set_count(env->set_ent)) ; i >=0; i--)
1205 var_arr[i].mem_edge_state = get_irg_initial_mem(current_ir_graph);
1209 /* Analyze call nodes to get information, if they store the address of a scalar.
1211 * @param *irn An ir node from the current_ir_graph.
1212 * @param *env The enviroment pointer.
1214 static void analyse_calls(ir_node *irn, void *ctx) {
1217 unsigned int acces_type;
1218 ir_node *param, *call_ptr, *blk;
1219 ir_entity *meth_ent;
1220 sels_t key_sels, *value_sels;
1221 call_access_t key_call, *value_call;
1222 value_arr_entry_t *val_arr;
1229 /* Calls that have a NoMem input do neither read nor write memory.
1230 We can completely ignore them here. */
1231 if (is_NoMem(get_Call_mem(irn)))
1234 /* We iterate over the parameters of this call nodes.*/
1235 for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
1236 param = get_Call_param(irn, i);
1237 if (is_Sel(param)) {
1238 /* We have found a parameter with operation sel.*/
1239 key_sels.sel = param;
1240 value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
1241 if(value_sels != NULL ) {
1243 /* We have found a call, that have as parameter a sel from our set_sels.*/
1244 call_ptr = get_Call_ptr(irn);
1246 if (is_SymConst(call_ptr) && get_SymConst_kind(call_ptr) == symconst_addr_ent) {
1247 meth_ent = get_SymConst_entity(call_ptr);
1248 /* we get the access type for our sel.*/
1249 acces_type = get_method_param_access(meth_ent, i);
1251 /* We can't analyze this function and we asume, that it store the address.*/
1252 acces_type = ptr_access_store;
1254 /* we save the access type and this call in the array allocated for this block.
1255 * The value number of this entity get us the position in the array to save this
1256 * information. Why we expect more calls as one we allocate a set.*/
1257 vnum = GET_ENT_VNUM(value_sels->ent);
1258 blk = get_nodes_block(irn);
1259 val_arr = get_irn_link(blk);
1261 if(val_arr[vnum].access_type > 3)
1262 /* The address of this entity have been stored.*/
1265 if(val_arr[vnum].calls == NULL)
1266 /* for this entity i have found the firs call in this block and we must allocate the set.*/
1267 val_arr[vnum].calls = new_set(call_cmp, 8);
1269 /* This call performs anything with the scalar and we must mark it.*/
1270 key_call.call = irn;
1271 key_call.access_type = acces_type;
1272 value_call = set_insert(val_arr[vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
1274 if(value_call->access_type < acces_type)
1275 /* this case tread, when a call access an entity more at once.
1276 * Than we must save the highest access type.*/
1277 value_call->access_type = acces_type;
1280 /* This call save the address of our scalar and we can't
1281 * use the scalars of this entity for optimization as from now.
1283 val_arr[vnum].access_type = acces_type;
1289 static int set_block_dominated_first_access(ir_node *blk, int vnum, unsigned int access) {
1291 ir_node *idom, *succ;
1292 value_arr_entry_t *val_arr;
1295 idom = get_Block_idom(blk);
1296 for(i = get_Block_n_cfg_outs(idom) - 1; i >=1; i--) {
1297 succ = get_Block_cfg_out(idom, i);
1298 val_arr = get_irn_link(succ);
1299 if(val_arr[vnum].access_type < 3) {
1300 val_arr[vnum].access_type = access;
1306 /* Update the access information of a block if a predecessor of
1307 * this black have a higher access for an entity.
1309 * @param *irn An ir node from the current_ir_graph.
1310 * @param *env The enviroment pointer.
1312 static void set_block_access(ir_node *irn, void *ctx){
1314 value_arr_entry_t *val_arr, *val_arr_pred;
1315 ent_leaves_t *value_leaves;
1316 ir_node *pred, *pred_blk, *leave;
1321 val_arr = get_irn_link(irn);
1323 for( i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--) {
1324 /* We analyze the predecessors of this block to see if this block must
1326 pred = get_Block_cfgpred(irn, i);
1327 pred_blk = get_nodes_block(pred);
1329 val_arr_pred = get_irn_link(pred_blk);
1331 for(value_leaves = set_first(env->set_ent); value_leaves; value_leaves = set_next(env->set_ent)) {
1332 vnum = GET_ENT_VNUM(value_leaves->ent);
1334 if((get_Block_n_cfgpreds(irn) > 1) && (val_arr[vnum].access_type > 3))
1335 env->changes = set_block_dominated_first_access(irn, vnum, val_arr[vnum].access_type);
1337 if((val_arr_pred[vnum].access_type > 3) && (val_arr[vnum].access_type < 3)) {
1338 /* We have found a block for update it access and value number information.*/
1339 val_arr[vnum].access_type = val_arr_pred[vnum].access_type;
1340 /* We update the access information of all leave, that belong to
1343 for(leave = pset_first(value_leaves->leaves); leave; leave = pset_next(value_leaves->leaves))
1344 val_arr[GET_IRN_VNUM(leave)].access_type = val_arr[vnum].access_type;
1346 /* In this way can't be got the actuall number of value numbers.
1347 val_arr[env->vnum_state].access_type = val_arr_pred[env->vnum_state].access_type; */
1353 /* Free the allocated call sets.
1355 * @param irn A block form the ir graph.
1356 * @param env The enviroment pinter.
1358 static void free_call_info(ir_node *irn, void *ctx) {
1362 value_arr_entry_t *val_arr;
1365 val_arr = get_irn_link(irn);
1367 for(i = env->nvals + set_count(env->set_ent); i >= 0; i--) {
1368 if(val_arr[i].calls != NULL)
1370 del_set(val_arr[i].calls);
1374 static void print_block_state(ir_node *irn, void *ctx) {
1376 value_arr_entry_t *val_arr;
1377 ent_leaves_t *value_leaves;
1378 call_access_t *value_calls;
1383 val_arr = get_irn_link(irn);
1384 ir_printf("\n\nThe actual value number state of this block is: %i \n",
1385 val_arr[env->vnum_state].access_type - 1);
1387 for(value_leaves = set_first(env->set_ent); value_leaves; value_leaves = set_next(env->set_ent)) {
1389 vnum = GET_ENT_VNUM(value_leaves->ent);
1390 ir_printf("The entity %F access type in the block with nr %u is %i \n",
1391 value_leaves->ent, get_irn_node_nr(irn), val_arr[vnum].access_type);
1393 if(val_arr[vnum].calls != NULL)
1394 for(value_calls = set_first(val_arr[vnum].calls); value_calls; value_calls = set_next(val_arr[vnum].calls))
1396 ir_printf("A call with nr %i acess a element of this entity with access %u \n",
1397 get_irn_node_nr(value_calls->call), value_calls->access_type);
1402 /** Optimize the found scalar replacements.
1404 * @param set_sels A set with all entities, that
1406 * @param set_ent A set with all sels nodes,
1407 * that belong to our scalars.
1408 * @param vnum The number of scalars.
1410 static void do_data_flow_scalar_replacement(set *set_ent, set *set_sels, int vnum) {
1414 obstack_init(&env.obst);
1415 env.set_ent = set_ent;
1416 env.set_sels = set_sels;
1418 env.fix_phis = NULL;
1419 env.fix_syncs = NULL;
1420 env.gl_mem_vnum = vnum - 2;
1421 env.vnum_state = vnum - 1;
1422 /* nvals are vnum - 1, why we indicate with nvals the number
1423 * of memory edges we will produce. For vnum_state we don't
1424 * need to produce a memory edge.*/
1425 env.nvals = vnum - 1;
1428 /* first step: allocate the value arrays for every block */
1429 irg_block_walk_graph(current_ir_graph, NULL, alloc_value_arr, &env);
1431 /* second step: we analyze all calls, that have as parameter scalar(s).
1432 * We mark the calls, that save the address of a scalar and we
1433 * mark the entity owner of this scalar as not optimizeble by now.*/
1434 irg_walk_graph(current_ir_graph, NULL, analyse_calls, &env);
1436 while(env.changes) {
1441 * third step: walk over the blocks of a graph and update
1442 * the information for the access of our scalars.
1444 irg_block_walk_graph(current_ir_graph, NULL, set_block_access, &env);
1448 // if(get_firm_verbosity())
1449 /* Debug info to see if analyse_calls work properly.*/
1450 irg_block_walk_graph(current_ir_graph, NULL, print_block_state, &env);
1453 * fourth step: walk over the graph blockwise in topological order
1454 * and split the memrory edge.
1456 inc_irg_block_visited(current_ir_graph);
1457 irg_walk_blkwise_graph(current_ir_graph, NULL, split_memory_edge, &env);
1461 /* fifth step: fix all nodes, that have as predecessor Unknown.*/
1466 /* sixth step: sync memory enges for the end block.*/
1467 sync_mem_edges(&env);
1469 /*seventh step: free the allocated memory*/
1470 irg_block_walk_graph(current_ir_graph, NULL, free_call_info, &env);
1471 obstack_free(&env.obst, NULL);
1475 * Find possible scalar replacements
1477 * @param irg The current ir graph.
1479 void data_flow_scalar_replacement_opt(ir_graph *irg) {
1485 ent_leaves_t key_leaves, *value_leaves;
1488 if (! get_opt_scalar_replacement())
1491 set_sels = new_set(sels_cmp, 8);
1492 set_ent = new_set(ent_leaves_t_cmp, 8);
1494 /* Call algorithm that remove the critical edges of a ir graph. */
1495 remove_critical_cf_edges(irg);
1497 /* Call algorithm that computes the out edges.*/
1498 assure_irg_outs(irg);
1500 /* Call algorithm that computes the loop information.*/
1501 construct_cf_backedges(irg);
1503 /* Call algorithm that computes the dominance information.*/
1506 /* Find possible scalar replacements */
1507 if (find_possible_replacements(irg)) {
1509 /* Insert in set the scalar replacements. */
1510 irg_frame = get_irg_frame(irg);
1512 for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) {
1513 ir_node *succ = get_irn_out(irg_frame, i);
1516 ir_entity *ent = get_Sel_entity(succ);
1518 if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
1520 /* we have found a entity, that have scalars and we insert it to our set_ent*/
1521 key_leaves.ent = ent;
1522 key_leaves.leaves = new_pset(leave_cmp, 8);
1523 value_leaves = set_insert(set_ent, &key_leaves, sizeof(key_leaves), HASH_PTR(ent));
1525 /* We allocate for every leave sel a vnum.*/
1526 vnum = allocate_value_numbers(set_sels, value_leaves->leaves, ent, vnum);
1530 /* Allocate value number for the globule memory edge.
1531 * and a value number for the value numbers state.*/
1534 /* Allocate value numbers for the entities .*/
1535 for(i = vnum,value_leaves = set_first(set_ent); value_leaves; i++, value_leaves = set_next(set_ent))
1536 SET_ENT_VNUM(value_leaves->ent, i);
1539 do_data_flow_scalar_replacement(set_ent, set_sels, vnum);
1541 /*free the allocated memory.*/
1542 for(value_leaves = set_first(set_ent); value_leaves; value_leaves = set_next(set_ent))
1543 del_pset(value_leaves->leaves);