3 * File name: ir/opt/data_flow_scalar_replace.c
4 * Purpose: scalar replacement of arrays and compounds
5 * Author: Beyhan Veliev
6 * Modified by: Michael Beck
9 * Copyright: (c) 1998-2005 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
28 #include "data_flow_scalar_replace.h"
40 #include "analyze_irg_args.h"
43 #define SET_ENT_VNUM(ent, vnum) set_entity_link(ent, INT_TO_PTR(vnum))
44 #define GET_ENT_VNUM(ent) (unsigned)PTR_TO_INT(get_entity_link(ent))
45 #define SET_IRN_VNUM(irn, vnum) set_irn_link(irn, INT_TO_PTR(vnum))
46 #define GET_IRN_VNUM(irn) (unsigned)PTR_TO_INT(get_irn_link(irn))
50 typedef struct _ent_leaves_t{
51 entity *ent; /**< An entity, that contains scalars for replace.*/
52 pset *leaves; /**< All leaves of this entity.*/
55 typedef struct _sels_t {
56 ir_node *sel; /**< A sel node, thats entity have scalars.*/
57 entity *ent; /**< The entity of this sel node.*/
60 typedef struct _call_access_t {
61 ir_node *call; /**< A call node, that have as parameter a scalar.*/
62 unsigned int access_type; /**< The access type, with that this call access this scalar.*/
65 typedef struct _fixlist_entry_t {
66 ir_node *irn; /**< An ir node, that must be fixed.*/
67 unsigned int vnum; /**< The value number, that must became this ir node.*/
70 typedef struct _syncs_fixlist_entry_t {
71 ir_node *irn; /**< A sync node that must be fixed.*/
72 int *accessed_vnum; /**< A pointer to save an array with value numbers, that must became this sync.*/
73 }syncs_fixlist_entry_t;
75 /* A entry, that save the memory
76 * edge state and the access state for this leave
77 * int the array,that is created for every block.*/
78 typedef struct _leave_t {
79 ir_node *mem_edge_state; /**< memory state for this scalar in this block.*/
80 unsigned int access_type; /**< access state for this scalar in this block.*/
81 set *calls; /**< call nodes,that change this scalar in this block.*/
85 * A path element entry: it is either an entity
86 * or a tarval, because we evaluate only constant array
87 * accesses like a.b.c[8].d
95 * An access path, used to assign value numbers
96 * to variables that will be scalar replaced
98 typedef struct _path_t {
99 unsigned vnum; /**< the value number */
100 unsigned path_len; /**< the length of the access path */
101 path_elem_t path[1]; /**< the path */
105 * environment for memory walker
107 typedef struct _env_t {
108 struct obstack obst; /**< a obstack for the memory edge */
109 set *set_sels; /**< a set with all sels, that are reachable from an entity with a scalar.*/
110 set *set_ent; /**< a set with all entities that have one or more scalars.*/
111 fixlist_entry_t *fix_phis; /**< list of all Phi nodes that must be fixed */
112 fixlist_entry_t *fix_ls; /**< list of all Load or Store nodes that must be fixed */
113 syncs_fixlist_entry_t *fix_syncs; /**< list of all Sync nodes that must be fixed */
114 unsigned int nvals; /**< to save the number of scalars.*/
115 unsigned int gl_mem_vnum; /**< indicate the position of the globule memory edge state in var_arr.*/
116 unsigned int vnum_state; /**< indicate the position of the value number state in var_arr.*/
117 unsigned int changes; /**< to save if by anlyse_calls is changed anything.*/
123 * Compare two elements of the ent_leaves_t set.
125 * @return 0 if they are identically
127 static int ent_leaves_t_cmp(const void *elt, const void *key, size_t size)
129 const ent_leaves_t *c1 = elt;
130 const ent_leaves_t *c2 = key;
132 return c1->ent != c2->ent;
136 * Compare two elements of the ent_access_t set.
138 * @return 0 if they are identically
140 static int ent_cmp(const void *elt, const void *key, size_t size)
142 const entity *c1 = elt;
143 const entity *c2 = key;
149 * Compare two elements of the sels_t set.
151 * @return 0 if they are identically
153 static int sels_cmp(const void *elt, const void *key, size_t size)
155 const sels_t *c1 = elt;
156 const sels_t *c2 = key;
158 return c1->sel != c2->sel;
162 * Compare two elements of the leave_t set.
164 * @return 0 if they are identically
166 static int leave_cmp(const void *elt, const void *key, size_t size)
168 const ir_node *c1 = elt;
169 const ir_node *c2 = key;
171 return get_Sel_entity(c1) != get_Sel_entity(c2);
175 * Compare two elements of the call_access_t set.
177 * @return 0 if they are identically
179 static int call_cmp(const void *elt, const void *key, size_t size)
181 const call_access_t *c1 = elt;
182 const call_access_t *c2 = key;
184 return c1->call != c2->call;
190 * @return 0 if they are identically
192 static int path_cmp(const void *elt, const void *key, size_t size)
194 const path_t *p1 = elt;
195 const path_t *p2 = key;
197 /* we can use memcmp here, because identical tarvals should have identical addresses */
198 return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
202 * Calculate a hash value for a path.
204 static unsigned path_hash(const path_t *path)
209 for (i = 0; i < path->path_len; ++i)
210 hash ^= (unsigned)PTR_TO_INT(path->path[i].ent);
216 * Returns non-zero, if all induces of a Sel node are constants.
218 * @param sel the Sel node that will be checked
220 static int is_const_sel(ir_node *sel) {
221 int i, n = get_Sel_n_indexs(sel);
223 for (i = 0; i < n; ++i) {
224 ir_node *idx = get_Sel_index(sel, i);
226 if (get_irn_op(idx) != op_Const)
233 * Returns non-zero, if the address of an entity
234 * represented by a Sel node (or it's successor Sels) is taken.
236 static int is_address_taken(ir_node *sel)
240 if (! is_const_sel(sel))
243 for (i = get_irn_n_outs(sel) - 1; i >= 0; --i) {
244 ir_node *succ = get_irn_out(sel, i);
246 switch (get_irn_opcode(succ)) {
248 /* ok, we just load from that entity */
252 /* check that Sel is not the Store's value */
253 if (get_Store_value(succ) == sel)
258 /* Check the Sel successor of Sel */
259 int res = is_address_taken(succ);
267 /* The address of an entity is given as a parameter.
268 * We analyzes that later and optimizes this scalar
274 /* another op, the address is taken */
282 * Link all Sels with the entity.
284 * @param ent the entity that will be scalar replaced
285 * @param sel a Sel node that selects some fields of this entity
287 static void link_all_leave_sels(entity *ent, ir_node *sel)
291 n = get_irn_n_outs(sel);
292 for (i = 0; i < n; ++i) {
293 ir_node *succ = get_irn_out(sel, i);
295 if (get_irn_op(succ) == op_Sel)
296 link_all_leave_sels(ent, succ);
300 /* if Sel nodes with memory inputs are used, a entity can be
301 * visited more than once causing a ring here, so we use the
302 * node flag to mark linked nodes
304 if (irn_visited(sel))
308 * we link the sels to the entity.
310 set_irn_link(sel, get_entity_link(ent));
311 set_entity_link(ent, sel);
313 mark_irn_visited(sel);
316 /* we need a special address that serves as an address taken marker */
318 static void *ADDRESS_TAKEN = &_x;
321 * Find possible scalar replacements.
323 * @param irg an IR graph
325 * This function finds variables on the (members of the) frame type
326 * that can be scalar replaced, because their address is never taken.
327 * If such a variable is found, it's entity link will hold a list of all
328 * Sel nodes, that selects anythings of this entity.
329 * Otherwise, the link will be ADDRESS_TAKEN or NULL.
331 * @return non-zero if at least one entity could be replaced
334 static int find_possible_replacements(ir_graph *irg)
336 ir_node *irg_frame = get_irg_frame(irg);
340 inc_irg_visited(irg);
342 n = get_irn_n_outs(irg_frame);
345 * First, clear the link field of all interestingentities.
346 * Note that we did not rely on the fact that there is only
347 * one Sel node per entity, so we might access one entity
348 * more than once here.
349 * That's why we have need two loops.
351 for (i = 0; i < n; ++i) {
352 ir_node *succ = get_irn_out(irg_frame, i);
354 if (get_irn_op(succ) == op_Sel) {
355 entity *ent = get_Sel_entity(succ);
356 set_entity_link(ent, NULL);
361 * Check the ir_graph for Sel nodes. If the entity of Sel
362 * isn't a scalar replacement set the link of this entity
363 * equal ADDRESS_TAKEN.
365 for (i = 0; i < n; ++i) {
366 ir_node *succ = get_irn_out(irg_frame, i);
368 if (get_irn_op(succ) == op_Sel) {
369 entity *ent = get_Sel_entity(succ);
372 if (get_entity_link(ent) == ADDRESS_TAKEN)
375 ent_type = get_entity_type(ent);
377 /* we can handle arrays, structs and atomic types yet */
378 if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
379 if (is_address_taken(succ)) {
380 if (get_entity_link(ent)) /* killing one */
382 set_entity_link(ent, ADDRESS_TAKEN);
385 /* possible found one */
386 if (get_entity_link(ent) == NULL)
388 link_all_leave_sels(ent, succ);
397 static int is_leave_sel(ir_node *sel) {
401 for(i = get_irn_n_outs(sel) - 1; i >= 0; i--) {
402 succ = get_irn_out(sel, i);
403 if(get_irn_op(succ) == op_Sel)
411 * Return a path from the Sel node sel to it's root.
413 * @param sel the Sel node
414 * @param len the length of the path so far
416 static path_t *find_path(ir_node *sel, unsigned len)
420 ir_node *pred = get_Sel_ptr(sel);
422 /* the current Sel node will add some path elements */
423 n = get_Sel_n_indexs(sel);
426 if (get_irn_op(pred) != op_Sel) {
427 /* we found the root */
429 res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path));
433 res = find_path(pred, len);
435 pos = res->path_len - len;
437 res->path[pos++].ent = get_Sel_entity(sel);
438 for (i = 0; i < n; ++i) {
439 ir_node *index = get_Sel_index(sel, i);
441 res->path[pos++].tv = get_Const_tarval(index);
447 * Allocate value numbers for the leaves
448 * in our found entities.
450 * @param sels a set that will contain all Sels that have a value number
451 * @param ent the entity that will be scalar replaced
452 * @param vnum the first value number we can assign
453 * @param modes a flexible array, containing all the modes of
456 * @return the next free value number
458 static unsigned allocate_value_numbers(set *set_sels, pset *leaves, entity *ent, unsigned vnum)
463 set *pathes = new_set(path_cmp, 8);
465 /* visit all Sel nodes in the chain of the entity */
466 for (sel = get_entity_link(ent); sel; sel = next) {
467 next = get_irn_link(sel);
469 /* we save for every sel it root entity, why
470 * we need this information, when we split the memory edge,
471 * and we must mark this sel for later. */
474 set_insert(set_sels, &key_sels, sizeof(key_sels), HASH_PTR(sel));
476 if(! is_leave_sel(sel))
479 /* We have found a leave and we add it to the pset of this entity.*/
480 pset_insert(leaves, sel, HASH_PTR(get_Sel_entity(sel)));
482 key = find_path(sel, 0);
483 path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
486 SET_IRN_VNUM(sel, path->vnum);
491 set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key));
493 SET_IRN_VNUM(sel, key->vnum);
499 set_entity_link(ent, NULL);
502 /* Add a sync node to it fix list.
504 * @param sync The sync node, that myst be addet to the fix list.
505 * @param unk_vnum An array whit the value number, that are synced with this sync node.
506 * @param env The enviroment pinter.
508 static void add_sync_to_fixlist(ir_node *sync, int *unk_vnum, env_t *env) {
510 syncs_fixlist_entry_t *s;
512 s = obstack_alloc(&env->obst, sizeof(*s));
514 s->accessed_vnum = unk_vnum;
515 set_irn_link(sync, env->fix_syncs);
518 /* Add a ir node to it fix list.
520 * @param irn The ir node, that myst be addet to the fix list.
521 * @param vnum The value number, that must baceme this ir node as predecessor later.
522 * @param env The enviroment pinter.
524 static void add_ls_to_fixlist(ir_node *irn, int vnum, env_t *env) {
528 l = obstack_alloc(&env->obst, sizeof(*l));
532 if(get_irn_op(irn) == op_Phi) {
533 set_irn_link(l->irn, env->fix_phis);
536 set_irn_link(l->irn, env->fix_ls);
541 static void add_mem_edge(value_arr_entry_t *val_arr, int vnum, ir_node ***in, int **accessed_vnum) {
543 if(val_arr[vnum].mem_edge_state != NULL)
544 ARR_APP1(ir_node *, *in, val_arr[vnum].mem_edge_state);
546 ARR_APP1(int, *accessed_vnum, vnum);
547 ARR_APP1(ir_node *, *in, new_Unknown(mode_M));
550 /** The function handles the scalars, that wase stored
553 * @param blk The block, that must be handled.
554 * @param env The enviroment pinter.
557 static void sync_stored_scalars(ir_node *blk, env_t *env) {
560 int *unk_vnum; /**< An arraw, where are saved the value number, that
561 are synced from this sync node.*/
562 ent_leaves_t *value_ent;
563 value_arr_entry_t *val_arr_blk, *val_arr;
564 ir_node *pred, *leave, **in;
565 ir_node *sync_blk; /**< The block, where the sync node must be created.*/
568 val_arr_blk = get_irn_link(blk);
570 for(value_ent = set_first(env->set_ent); value_ent; value_ent = set_next(env->set_ent)) {
573 if(val_arr_blk[GET_ENT_VNUM(value_ent->ent)].access_type <= 3)
574 /* This entity is not stored in this block.*/
577 for(i = get_Block_n_cfgpreds(blk) - 1; i >= 0; i--) {
579 pred = get_Block_cfgpred(blk, i);
580 pred = get_nodes_block(pred);
581 val_arr = get_irn_link(pred);
583 if(val_arr[GET_ENT_VNUM(value_ent->ent)].access_type <= 3) {
584 /* In this predecessor block is this entity not acessed.
585 * We must sync in the end ot this block.*/
586 if(get_Block_n_cfgpreds(blk) > 1)
587 sync_blk = get_nodes_block(get_Block_cfgpred(blk, i));
591 val_arr = get_irn_link(sync_blk);
592 /* An array to save the memory edges, that must be
594 in = NEW_ARR_F(ir_node *, 1);
596 /* An array to save the value numbers,
597 * that must be repaired.*/
598 unk_vnum = NEW_ARR_F(int, 0);
599 /* The global memory edge.*/
600 if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL)
601 in[0] = new_Unknown(mode_M);
603 in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
605 for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves))
606 /* All this memory edges must be synced.*/
607 add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &unk_vnum);
609 /* We create the sync and set it in the global memory state.*/
610 val_arr[env->gl_mem_vnum].mem_edge_state = new_r_Sync(current_ir_graph, sync_blk, ARR_LEN(in), in);
611 /* We add this sync node to the sync's fix list.*/
612 add_sync_to_fixlist(val_arr[env->gl_mem_vnum].mem_edge_state, unk_vnum, env);
619 /* The function split the memory edge of load and store nodes, that have
620 * as predecessor a scalar
622 * @param irn The node, that memory edge must be spleted.
623 * @param env The enviroment pinter.
625 static void split_ls_mem_edge(ir_node *irn, env_t *env) {
628 ir_node *leave, *irn_blk, *mem_state, *new_mem_state;
629 unsigned ent_vnum, sel_vnum, i;
630 value_arr_entry_t *val_arr;
631 sels_t key_sels, *value_sels;
632 ent_leaves_t key_ent, *value_ent;
634 op = get_irn_op(irn);
637 key_sels.sel = get_Load_ptr(irn);
639 key_sels.sel = get_Store_ptr(irn);
641 value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
643 if(value_sels != NULL) {
644 /* we have found a load or store, that use a sel of our set
645 * and we must split or extend, if the memory edge have been
646 * split for this sel, the memory edge.*/
648 key_ent.ent = value_sels->ent;
649 value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
650 /*To check if the enities set is right filled. */
651 assert(value_ent && " This sel's entity isn't int the entity set.");
653 leave = pset_find(value_ent->leaves, key_sels.sel, HASH_PTR(get_Sel_entity(key_sels.sel)));
654 /*To check if the leaves set is right filled. */
655 assert(leave && "Anything in data_flow_scalar_replacment algorithm is wrong.");
657 ent_vnum = GET_ENT_VNUM(value_ent->ent);
658 sel_vnum = GET_IRN_VNUM(leave);
659 irn_blk = get_nodes_block(irn);
660 val_arr = get_irn_link(irn_blk);
662 if(val_arr[ent_vnum].access_type == 0)
663 /* We have found a scalar, that address is not stored as jet.*/
666 /* This scalar have been stored.*/
667 i = env->gl_mem_vnum;
669 if(val_arr[i].mem_edge_state == NULL) {
670 /* We split now for this sel the memory edge in this block.*/
671 mem_state = new_Unknown(mode_M);
672 /* We must mark this node to fix later*/
673 add_ls_to_fixlist(irn, i, env);
676 /* We have split the memory edge and the current state is saved.*/
677 mem_state = val_arr[i].mem_edge_state;
679 /* We set this Load or Store to the memory edge of this
682 set_Load_mem(irn, mem_state);
684 set_Store_mem(irn, mem_state);
686 /* When we have split or extended the memory edge we must
687 * update the memory_edge_state of this sel*/
688 new_mem_state = get_irn_out(irn, 0);
689 if(get_irn_mode(new_mem_state) == mode_M)
690 val_arr[i].mem_edge_state = new_mem_state;
692 val_arr[i].mem_edge_state = get_irn_out(irn, 1);
696 static void split_phi_mem_edge(ir_node *irn, env_t *env) {
698 ir_node *irn_blk, *unk, **in;
700 value_arr_entry_t *val_arr;
702 irn_blk = get_nodes_block(irn);
703 val_arr = get_irn_link(irn_blk);
705 n = get_Block_n_cfgpreds(irn_blk);
707 in = alloca(sizeof(*in) * n);
709 for (i = env->gl_mem_vnum; i >= 0; --i) {
711 if(val_arr[i].access_type > 3)
712 /* This scalar was saved and we don't need
713 * to produce a phi for it.*/
716 unk = new_Unknown(mode_M);
717 for (j = n - 1; j >= 0; --j)
719 if(i != env->gl_mem_vnum)
720 val_arr[i].mem_edge_state = new_r_Phi(current_ir_graph, irn_blk, n, in, mode_M);
722 /* We use for the global memory the phi node, that
723 * is already available.*/
724 val_arr[i].mem_edge_state = irn;
727 add_ls_to_fixlist(val_arr[i].mem_edge_state, i, env);
731 /* The function handles the call nodes, that have
732 * as parameter a scalar
734 * @param env The enviroment pinter.
735 * @param call The call node, that must be handled.
736 * @param accessed_entities A set wit all entities, that are accessed from this call node.*/
737 static void split_call_mem_edge(env_t *env, ir_node *call, pset *accessed_entities) {
739 ent_leaves_t key_ent, *value_ent;
740 value_arr_entry_t *val_arr;
741 call_access_t key_call, *value_call;
742 ir_node *call_blk, *new_mem_state, *leave;
746 int fix_irn = 0; /**< Set to 1 if we must add this call to it fix list.*/
747 int *accessed_leaves_vnum = NULL; /**< An arraw, where are saved the value number, that
748 are synced from call's sync node, if we need it.*/
750 call_blk = get_nodes_block(call);
751 val_arr = get_irn_link(call_blk);
752 /* An array to save the memory edges, that must be
754 in = NEW_ARR_F(ir_node *, 1);
755 /* An array to save the value numbers of the memory
756 * edges that must be repaired.*/
757 accessed_leaves_vnum = NEW_ARR_F(int, 0);
759 /* We get the memory successor of the call node.
760 * It is the new memory state for all synced memory
762 new_mem_state = get_irn_out(call, 0);
763 if(get_irn_mode(new_mem_state) != mode_M)
764 new_mem_state = get_irn_out(call,1);
766 /* The global memory is the first predecessor of the create sync node.*/
767 if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) {
768 in[0] = new_Unknown(mode_M);
772 in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
775 for(ent = pset_first(accessed_entities); ent; ent = pset_next(accessed_entities)) {
776 /* Whit this loop we iterate all accessed entities from this call and collect
777 * all memory edges, that we must sync.*/
778 ent_vnum = GET_ENT_VNUM(ent);
780 key_call.call = call;
781 value_call = set_find(val_arr[ent_vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
784 value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
786 if(val_arr[ent_vnum].access_type <= 3) {
787 /* This scalar's address wasn't stored in this block.*/
788 switch(value_call->access_type) {
790 case ptr_access_none :
791 /* In this case we have nothing to do.*/
794 case ptr_access_read:
795 case ptr_access_write:
797 /* All this cases must be traded equal.*/
799 for(leave = pset_first(value_ent->leaves); leave; leave = pset_next(value_ent->leaves)){
800 /* All this memory edges must be synced.*/
801 add_mem_edge(val_arr, GET_IRN_VNUM(leave), &in, &accessed_leaves_vnum);
803 /* We update the memory state of this leave.*/
804 if(value_call->access_type != ptr_access_read)
805 val_arr[GET_IRN_VNUM(leave)].mem_edge_state = new_mem_state;
814 /* We must update the global memory state.*/
815 val_arr[env->gl_mem_vnum].mem_edge_state = new_mem_state;
817 if(ARR_LEN(in) == 1) {
818 /* we must set the call memory to gobale momory*/
819 set_Call_mem(call,in[0]);
822 /* We add this call node to the call fix list..*/
823 add_ls_to_fixlist(call, env->gl_mem_vnum, env);
826 /* We create the sync and set it as memory predecessor of the call node.*/
827 sync = new_r_Sync(current_ir_graph, call_blk, ARR_LEN(in), in);
828 set_Call_mem(call, sync);
830 if(ARR_LEN(accessed_leaves_vnum))
831 /* We add this sync node to the sync's fix list.*/
832 add_sync_to_fixlist(sync, accessed_leaves_vnum, env);
837 /* The function split the memory edge.*/
838 static void split_memory_edge(ir_node *irn, void *ctx) {
841 ir_node *sel, *irn_blk;
843 sels_t key_sels, *value_sels;
844 value_arr_entry_t *val_arr;
845 pset *accessed_entities;
849 op = get_irn_op(irn);
854 irn_blk = get_nodes_block(irn);
856 if (Block_not_block_visited(irn_blk)) {
857 /* We sync first the stored scalar address in this block.*/
858 mark_Block_block_visited(irn_blk);
859 sync_stored_scalars(irn_blk, env);
862 if(op == op_Load || op == op_Store)
864 split_ls_mem_edge(irn, env);
867 if (op == op_Phi && get_irn_mode(irn) == mode_M) {
869 * found a memory Phi: Here, we must create new Phi nodes
871 split_phi_mem_edge(irn, env);
875 /* We save in this set all entities,
876 * that are accessed from this call node.*/
877 accessed_entities = new_pset(ent_cmp, 8);
878 val_arr = get_irn_link(get_nodes_block(irn));
880 for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
881 sel = get_Call_param(irn, i);
882 if(get_irn_op(sel) == op_Sel) {
884 value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
887 if(value_sels != NULL && val_arr[GET_ENT_VNUM(value_sels->ent)].access_type <= 3)
888 /* We save in this set all accessed entities from this call node whit
889 * access none, read, write or rw..*/
890 pset_insert(accessed_entities, value_sels->ent, HASH_PTR(value_sels->ent));
893 split_call_mem_edge(env, irn, accessed_entities);
900 * searches through blocks beginning from block for value
901 * vnum and return it.
903 static ir_node *find_value(ir_node *block, unsigned vnum)
905 value_arr_entry_t *val_arr;
909 if (Block_not_block_visited(block)) {
910 mark_Block_block_visited(block);
912 val_arr = get_irn_link(block);
914 if (val_arr[vnum].mem_edge_state)
915 return val_arr[vnum].mem_edge_state;
917 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
918 ir_node *pred = get_Block_cfgpred(block, i);
920 res = find_value(get_nodes_block(pred), vnum);
929 * fix the Load/Store or Call list
931 static void fix_ls(env_t *env)
934 ir_node *irn, *block, *pred, *val;
938 for (l = env->fix_ls; l; l = get_irn_link(irn)) {
941 op = get_irn_op(irn);
942 block = get_nodes_block(irn);
943 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
944 pred = get_Block_cfgpred(block, i);
945 pred = get_nodes_block(pred);
947 inc_irg_block_visited(current_ir_graph);
948 val = find_value(pred, l->vnum);
955 set_Store_mem(irn, val);
958 set_Load_mem(irn, val);
960 set_Call_mem(irn, val);
967 static void fix_phis(env_t *env)
970 ir_node *phi, *block, *pred, *val;
973 for (l = env->fix_phis; l; l = get_irn_link(phi)) {
976 block = get_nodes_block(phi);
977 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
979 pred = get_Block_cfgpred(block, i);
980 pred = get_nodes_block(pred);
982 inc_irg_block_visited(current_ir_graph);
983 val = find_value(pred, l->vnum);
986 set_irn_n(phi, i, val);
995 static void fix_syncs(env_t *env)
997 syncs_fixlist_entry_t *l;
998 ir_node *sync, *block, *pred, *val;
1002 for (l = env->fix_syncs; l; l = get_irn_link(sync)) {
1006 /* The sync block must have one predecessor, when it
1007 have unknown nodes as predecessor.*/
1008 block = get_nodes_block(sync);
1009 pred = get_Block_cfgpred(block, 0);
1010 pred = get_nodes_block(pred);
1012 /* We first repair the global memory edge at the first position of sync predecessors.*/
1013 if(get_irn_op(get_irn_n(sync, 0)) == op_Unknown) {
1014 inc_irg_block_visited(current_ir_graph);
1015 val = find_value(pred, env->gl_mem_vnum);
1016 set_irn_n(sync, 0, val);
1019 for (i = get_irn_arity(sync) - 1; i >= 1; --i) {
1020 /* We repair the leaves*/
1021 if(get_irn_op(get_irn_n(sync, i)) == op_Unknown) {
1022 inc_irg_block_visited(current_ir_graph);
1023 val = find_value(pred, l->accessed_vnum[k++]);
1024 set_irn_n(sync, i, val);
1029 /* For the end node we must sync all memory edges.*/
1030 static void sync_mem_edges(env_t *env) {
1032 value_arr_entry_t *val_arr;
1033 ir_node **in, *sync, *Return, *Return_blk;
1034 int i, vnum, vnum_state;
1036 Return = get_Block_cfgpred(get_irg_end_block(current_ir_graph), 0);
1037 Return_blk = get_nodes_block(Return);
1038 val_arr = get_irn_link(Return_blk);
1041 for(i = 0; i <= env->gl_mem_vnum; i++)
1042 /* we get the current state of non saved scalars.*/
1043 if(val_arr[i].access_type <= 3)
1047 /* We allocate the memory, that we need for the successors of the sync.*/
1048 in = malloc(sizeof(ir_node*) *vnum_state);
1049 /* The global memory edge is the first predecessor of this sync node.*/
1050 if(val_arr[env->gl_mem_vnum].mem_edge_state == NULL) {
1051 /* We must search through blocks for this memory state.*/
1052 inc_irg_block_visited(current_ir_graph);
1053 in[0] = find_value(Return_blk, env->gl_mem_vnum);
1056 in[0] = val_arr[env->gl_mem_vnum].mem_edge_state;
1059 for(i = 1, vnum = 0; vnum < env->gl_mem_vnum; vnum++) {
1061 if(val_arr[vnum].access_type > 3)
1062 /* this scalar was saved and we must not sync it memory edge.*/
1065 if(val_arr[vnum].mem_edge_state == NULL) {
1066 /* We must search through blocks for this memory state.*/
1067 inc_irg_block_visited(current_ir_graph);
1068 in[i] = find_value(Return_blk, vnum);
1071 in[i] = val_arr[vnum].mem_edge_state;
1075 //assert(i < env->nvals && "Our nvals algorithm is baggy." );
1077 sync = new_r_Sync(current_ir_graph, Return_blk, vnum_state, in);
1078 set_Return_mem(Return, sync);
1084 * Walker: allocate the value array for every block.
1086 static void alloc_value_arr(ir_node *block, void *ctx)
1090 value_arr_entry_t *var_arr = obstack_alloc(&env->obst, sizeof(value_arr_entry_t) *(env->nvals + set_count(env->set_ent) + 1));
1092 /* the value array is empty at start */
1093 memset(var_arr, 0, sizeof(value_arr_entry_t) * (env->nvals + set_count(env->set_ent) + 1));
1094 set_irn_link(block, var_arr);
1095 /* We set the block value number state to optimal and later we update this.*/
1096 var_arr[env->vnum_state].access_type = env->nvals;
1098 if(get_irg_start_block(current_ir_graph) == block)
1099 for(i = (env->nvals + set_count(env->set_ent)) ; i >=0; i--)
1100 var_arr[i].mem_edge_state = get_irg_initial_mem(current_ir_graph);
1104 /* Analyze call nodes to get information, if they store the address of a scalar. */
1105 static void analyse_calls(ir_node *irn, void *ctx) {
1108 unsigned int acces_type;
1110 ir_node *param, *call_ptr, *blk;
1113 sels_t key_sels, *value_sels;
1114 call_access_t key_call, *value_call;
1115 value_arr_entry_t *val_arr;
1116 ent_leaves_t key_ent, *value_ent;
1118 if(get_irn_op(irn) != op_Call)
1121 for ( i = get_Call_n_params(irn) - 1; i >= 0; i--) {
1122 param = get_Call_param(irn, i);
1123 if(get_irn_op(param) == op_Sel) {
1125 key_sels.sel = param;
1126 value_sels = set_find(env->set_sels, &key_sels, sizeof(key_sels), HASH_PTR(key_sels.sel));
1127 if(value_sels != NULL ) {
1128 /* We have found a call, that have as parameter a sel from our set_sels.*/
1129 call_ptr = get_Call_ptr(irn);
1130 op = get_irn_op(call_ptr);
1132 if(op == op_SymConst && get_SymConst_kind(call_ptr) == symconst_addr_ent)
1133 meth_ent = get_SymConst_entity(call_ptr);
1136 /* we get the access type for our sel.*/
1137 acces_type = get_method_param_access(meth_ent, i);
1138 /* we save the access type and this call in the array allocated for this block.
1139 * The value number of this entity get us the position in the array to save this
1140 * information. Why we expect more calls as one we allocate a set.*/
1141 vnum = GET_ENT_VNUM(value_sels->ent);
1142 blk = get_nodes_block(irn);
1143 val_arr = get_irn_link(blk);
1145 if(val_arr[vnum].access_type > 3)
1146 /* The address of this entity have been stored.*/
1149 if(val_arr[vnum].calls == NULL)
1150 /* for this entity i have found the firs call in this block and we must allocate the set.*/
1151 val_arr[vnum].calls = new_set(call_cmp, 8);
1153 /* This call performs anything with the scalar and we must mark it.*/
1154 key_call.call = irn;
1155 key_call.access_type = acces_type;
1156 value_call = set_insert(val_arr[vnum].calls, &key_call, sizeof(key_call), HASH_PTR(key_call.call));
1158 if(value_call->access_type < acces_type)
1159 /* this case tread, when a call access an entity more at once.
1160 * Than we must save the highest access type.*/
1161 value_call->access_type = acces_type;
1163 if(acces_type > 3) {
1164 /* This call save the address of our scalar and we can't
1165 * use the scalars of this entity for optimization as from now.
1167 val_arr[vnum].access_type = acces_type;
1168 /* We must update our scalars number.*/
1169 key_ent.ent = value_sels->ent;
1170 value_ent = set_find(env->set_ent, &key_ent, sizeof(key_ent), HASH_PTR(key_ent.ent));
1176 /* Update the access information of a block if a predecessor of
1177 * this black have a store access for an entity.*/
1178 static void set_block_access(ir_node *irn, void *ctx){
1180 value_arr_entry_t *val_arr, *val_arr_pred;
1181 ent_leaves_t *value_leaves;
1183 ir_node *pred, *pred_blk, *leave;
1187 val_arr = get_irn_link(irn);
1189 for( i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--) {
1190 /* We analyze the predecessors of this block to see if this block must
1192 pred = get_Block_cfgpred(irn, i);
1193 pred_blk = get_nodes_block(pred);
1194 blk_loop = get_irn_loop(pred_blk);
1196 val_arr_pred = get_irn_link(pred_blk);
1198 for(value_leaves = set_first(env->set_ent); value_leaves; value_leaves = set_next(env->set_ent)) {
1199 vnum = GET_ENT_VNUM(value_leaves->ent);
1201 if((val_arr_pred[vnum].access_type > 3) && (val_arr[vnum].access_type < 3)) {
1202 /* We have found a block for update it access and value number information.*/
1203 val_arr[vnum].access_type = val_arr_pred[vnum].access_type;
1204 /* We update the access information of all leave, that belong to
1206 for(leave = pset_first(value_leaves->leaves); leave; leave = pset_next(value_leaves->leaves))
1207 val_arr[GET_IRN_VNUM(leave)].access_type = val_arr[vnum].access_type;
1209 val_arr[env->vnum_state].access_type = val_arr_pred[env->vnum_state].access_type;
1216 static void print_block_state(ir_node *irn, void *ctx) {
1219 value_arr_entry_t *val_arr;
1220 ent_leaves_t *value_leaves;
1221 call_access_t *value_calls;
1224 val_arr = get_irn_link(irn);
1226 ir_printf("\n\nThe actual value number state of this block is: %i \n", val_arr[env->vnum_state].access_type - 1);
1228 for(value_leaves = set_first(env->set_ent); value_leaves; value_leaves = set_next(env->set_ent)) {
1229 vnum = GET_ENT_VNUM(value_leaves->ent);
1230 ir_printf("The entity %F access type in the block with nr %u is %i \n", value_leaves->ent, get_irn_node_nr(irn),
1231 val_arr[vnum].access_type);
1232 if(val_arr[vnum].calls != NULL)
1233 for(value_calls = set_first(val_arr[vnum].calls); value_calls; value_calls = set_next(val_arr[vnum].calls))
1234 ir_printf("A call with nr %i acess a element of this entity with access %u \n",
1235 get_irn_node_nr(value_calls->call), value_calls->access_type);
1240 /** Optimize the found scalar replacements.
1242 * @param sels A pset with all sels nodes,
1243 * that belong to our scalars.
1245 static void do_data_flow_scalar_replacement(set *set_ent, set *set_sels, int vnum) {
1249 obstack_init(&env.obst);
1250 env.set_ent = set_ent;
1251 env.set_sels = set_sels;
1253 env.fix_phis = NULL;
1254 env.fix_syncs = NULL;
1255 env.gl_mem_vnum = vnum - 2;
1256 env.vnum_state = vnum - 1;
1257 /* nvals are vnum - 1, why we indicate with nvals the number
1258 * of memory edges we will produce. For vnum_state we don't
1259 * need to produce a memory edge.*/
1260 env.nvals = vnum - 1;
1263 /* first step: allocate the value arrays for every block */
1264 irg_block_walk_graph(current_ir_graph, NULL, alloc_value_arr, &env);
1266 /* second step: we analyze all calls, that have as parameter scalar(s)
1267 * and we mark this calls. If the call save the address of a scalar we
1268 * mark the entity owner of this scalar as not optimizeble by now.*/
1269 irg_walk_graph(current_ir_graph, NULL, analyse_calls, &env);
1271 while(env.changes) {
1276 * third step: walk over the blocks of a graph and update
1277 * the information for the access of our scalars.
1279 irg_block_walk_graph(current_ir_graph, NULL, set_block_access, &env);
1282 /* Debug info to see if analyse_calls work properly.*/
1283 irg_block_walk_graph(current_ir_graph, NULL, print_block_state, &env);
1285 inc_irg_block_visited(current_ir_graph);
1287 * fourth step: walk over the graph blockwise in topological order
1288 * and split the memrory edge.
1290 irg_walk_blkwise_graph(current_ir_graph, NULL, split_memory_edge, &env);
1292 /* fifth step: fix all nodes, that have as predecessor Unknown.*/
1297 sync_mem_edges(&env);
1301 * Find possible scalar replacements
1303 * @param irg The current ir graph.
1305 void data_flow_scalar_replacement_opt(ir_graph *irg)
1312 ent_leaves_t key_leaves, *value_leaves;
1315 if (! get_opt_scalar_replacement())
1318 rem = current_ir_graph;
1319 set_sels = new_set(sels_cmp, 8);
1320 set_ent = new_set(ent_leaves_t_cmp, 8);
1322 /* Call algorithm that remove the critical edges of a ir graph. */
1323 remove_critical_cf_edges(irg);
1325 /* Call algorithm that computes the out edges */
1326 if (get_irg_outs_state(irg) != outs_consistent)
1327 compute_irg_outs(irg);
1329 /* Call algorithm that computes the loop information */
1330 compute_loop_info(irg);
1332 /* Find possible scalar replacements */
1333 if (find_possible_replacements(irg)) {
1335 if (get_opt_scalar_replacement_verbose()) {
1336 printf("Scalar Replacement: %s\n", get_entity_name(get_irg_entity(irg)));
1339 /* Insert in set the scalar replacements. */
1340 irg_frame = get_irg_frame(irg);
1342 for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) {
1343 ir_node *succ = get_irn_out(irg_frame, i);
1345 if (get_irn_op(succ) == op_Sel) {
1346 entity *ent = get_Sel_entity(succ);
1348 if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
1350 /* we have found a entity, that have scalars and we insert it to our set_ent*/
1351 key_leaves.ent = ent;
1352 key_leaves.leaves = new_pset(leave_cmp, 8);
1353 value_leaves = set_insert(set_ent, &key_leaves, sizeof(key_leaves), HASH_PTR(ent));
1355 /* We allocate for every leave sel a vnum.*/
1356 vnum = allocate_value_numbers(set_sels, value_leaves->leaves, ent, vnum);
1359 printf("vnumber in data flow= %i\n", vnum);
1361 /* Allocate value number for the globule memory edge.
1362 * and a value number for the value numbers state.*/
1365 /* Allocate value numbers for the entities .*/
1366 for(i = vnum,value_leaves = set_first(set_ent); value_leaves; i++, value_leaves = set_next(set_ent))
1367 SET_ENT_VNUM(value_leaves->ent, i);
1370 do_data_flow_scalar_replacement(set_ent, set_sels, vnum);