2 * Copyright (C) 1995-2011 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 Dataflow driven Load/Store optimizations, uses some ideas from
24 * @author Michael Beck
39 #include "iroptimize.h"
40 #include "irnodehashmap.h"
41 #include "raw_bitset.h"
46 /* maximum number of output Proj's */
47 #define MAX_PROJ ((long)pn_Load_max > (long)pn_Store_max ? (long)pn_Load_max : (long)pn_Store_max)
50 * Mapping an address to an dense ID.
52 typedef struct address_entry_t {
53 unsigned id; /**< The ID */
60 FLAG_KILL_ALL = 1, /**< KILL all addresses */
61 FLAG_KILLED_NODE = 2, /**< this node was killed */
62 FLAG_EXCEPTION = 4, /**< this node has exception flow */
63 FLAG_IGNORE = 8, /**< ignore this node (volatile or other) */
67 * A value: This represents a value stored at a given address in
68 * memory. Do not confuse with values from value numbering.
70 typedef struct value_t value_t;
72 ir_node *address; /**< the address of this value */
73 ir_node *value; /**< the value itself */
74 ir_mode *mode; /**< the mode of the value */
75 unsigned id; /**< address id */
79 * A memop describes an memory-related operation.
80 * These are Loads/Store and all other ops that might modify
81 * memory (Calls, CopyB) or causing exceptions.
83 typedef struct memop_t memop_t;
85 value_t value; /**< the value of this memop: only defined for Load/Store */
86 ir_node *node; /**< the memory op itself */
87 ir_node *mem; /**< the memory FROM this node */
88 ir_node *replace; /**< the replacement node if this memop is replaced */
89 memop_t *next; /**< links to the next memory op in the block in forward order. */
90 memop_t *prev; /**< links to the previous memory op in the block in forward order. */
91 unsigned flags; /**< memop flags */
92 ir_node *projs[MAX_PROJ+1]; /**< Projs of this memory op */
96 * Additional data for every basic block.
98 typedef struct block_t block_t;
100 memop_t *memop_forward; /**< topologically sorted list of memory ops in this block */
101 memop_t *memop_backward; /**< last memop in the list */
102 unsigned *avail_out; /**< out-set of available addresses */
103 memop_t **id_2_memop_avail; /**< maps avail address ids to memops */
104 unsigned *anticL_in; /**< in-set of anticipated Load addresses */
105 memop_t **id_2_memop_antic; /**< maps anticipated address ids to memops */
106 ir_node *block; /**< the associated block */
107 block_t *forward_next; /**< next block entry for forward iteration */
108 block_t *backward_next; /**< next block entry for backward iteration */
109 memop_t *avail; /**< used locally for the avail map */
110 memop_t **trans_results; /**< used to cached translated nodes due antic calculation. */
114 * Metadata for this pass.
116 typedef struct ldst_env_t {
117 struct obstack obst; /**< obstack for temporary data */
118 ir_nodehashmap_t adr_map; /**< Map addresses to */
119 block_t *forward; /**< Inverse post-order list of all blocks Start->End */
120 block_t *backward; /**< Inverse post-order list of all blocks End->Start */
121 ir_node *start_bl; /**< start block of the current graph */
122 ir_node *end_bl; /**< end block of the current graph */
123 unsigned *curr_set; /**< current set of addresses */
124 memop_t **curr_id_2_memop; /**< current map of address ids to memops */
125 unsigned curr_adr_id; /**< number for address mapping */
126 unsigned n_mem_ops; /**< number of memory operations (Loads/Stores) */
127 size_t rbs_size; /**< size of all bitsets in bytes */
128 int max_cfg_preds; /**< maximum number of block cfg predecessors */
129 int changed; /**< Flags for changed graph state */
131 ir_node **id_2_address; /**< maps an id to the used address */
135 /* the one and only environment */
140 static firm_dbg_module_t *dbg;
143 * Dumps the block list.
145 * @param ldst environment
147 static void dump_block_list(ldst_env *env)
153 for (entry = env->forward; entry != NULL; entry = entry->forward_next) {
154 DB((dbg, LEVEL_2, "%+F {", entry->block));
157 for (op = entry->memop_forward; op != NULL; op = op->next) {
159 DB((dbg, LEVEL_2, "\n\t"));
161 DB((dbg, LEVEL_2, "%+F", op->node));
162 if ((op->flags & FLAG_KILL_ALL) == FLAG_KILL_ALL)
163 DB((dbg, LEVEL_2, "X"));
164 else if (op->flags & FLAG_KILL_ALL)
165 DB((dbg, LEVEL_2, "K"));
166 DB((dbg, LEVEL_2, ", "));
170 DB((dbg, LEVEL_2, "\n}\n\n"));
172 } /* dump_block_list */
175 * Dumps the current set.
177 * @param bl current block
178 * @param s name of the set
180 static void dump_curr(block_t *bl, const char *s)
182 size_t end = env.rbs_size - 1;
186 DB((dbg, LEVEL_2, "%s[%+F] = {", s, bl->block));
188 for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
189 memop_t *op = env.curr_id_2_memop[pos];
192 DB((dbg, LEVEL_2, "\n\t"));
195 DB((dbg, LEVEL_2, "<%+F, %+F>, ", op->value.address, op->value.value));
198 DB((dbg, LEVEL_2, "\n}\n"));
202 static void dump_block_list(ldst_env *env)
206 static void dump_curr(block_t *bl, const char *s)
211 #endif /* DEBUG_libfirm */
213 /** Get the block entry for a block node */
214 static block_t *get_block_entry(const ir_node *block)
216 assert(is_Block(block));
218 return (block_t*)get_irn_link(block);
219 } /* get_block_entry */
221 /** Get the memop entry for a memory operation node */
222 static memop_t *get_irn_memop(const ir_node *irn)
224 assert(! is_Block(irn));
225 return (memop_t*)get_irn_link(irn);
226 } /* get_irn_memop */
229 * Walk over the memory edges from definition to users.
230 * This ensures, that even operation without memory output are found.
232 * @param irn start node
233 * @param pre pre walker function
234 * @param post post walker function
235 * @param ctx context parameter for the walker functions
237 static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx)
242 mark_irn_visited(irn);
247 mode = get_irn_mode(irn);
248 if (mode == mode_M) {
249 /* every successor uses memory */
250 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
251 ir_node *succ = get_irn_out(irn, i);
253 if (! irn_visited(succ))
254 walk_memory(succ, pre, post, ctx);
256 } else if (mode == mode_T) {
257 /* only some Proj's uses memory */
258 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
259 ir_node *proj = get_irn_out(irn, i);
261 if (get_irn_mode(proj) == mode_M && ! irn_visited(proj))
262 walk_memory(proj, pre, post, ctx);
270 * Walks over all memory nodes of a graph.
273 * @param pre pre walker function
274 * @param post post walker function
275 * @param ctx context parameter for the walker functions
277 static void walk_memory_irg(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *ctx)
279 inc_irg_visited(irg);
281 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
284 * there are two possible sources for memory: initial_mem and nomem
285 * we ignore nomem as this should NOT change the memory
287 walk_memory(get_irg_initial_mem(irg), pre, post, ctx);
289 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
290 } /* walk_memory_irg */
293 * Register an address and allocate a (sparse, 0..n) ID for it.
295 * @param adr the IR-node representing the address
297 * @return the allocated id
299 static unsigned register_address(ir_node *adr)
301 address_entry *entry;
303 /* skip Confirms and Casts */
305 if (is_Confirm(adr)) {
306 adr = get_Confirm_value(adr);
310 adr = get_Cast_op(adr);
314 entry = (address_entry*)ir_nodehashmap_get(&env.adr_map, adr);
318 entry = OALLOC(&env.obst, address_entry);
320 entry->id = env.curr_adr_id++;
321 ir_nodehashmap_insert(&env.adr_map, adr, entry);
323 DB((dbg, LEVEL_3, "ADDRESS %+F has ID %u\n", adr, entry->id));
325 ARR_APP1(ir_node *, env.id_2_address, adr);
329 } /* register_address */
333 * translate an address through a Phi node into a given predecessor
336 * @param address the address
337 * @param block the block
338 * @param pos the position of the predecessor in block
340 static ir_node *phi_translate(ir_node *address, const ir_node *block, int pos)
342 if (is_Phi(address) && get_nodes_block(address) == block)
343 address = get_Phi_pred(address, pos);
345 } /* phi_translate */
348 * Walker: allocate an block entry for every block
349 * and register all potential addresses.
351 static void prepare_blocks(ir_node *irn, void *ctx)
356 block_t *entry = OALLOC(&env.obst, block_t);
359 entry->memop_forward = NULL;
360 entry->memop_backward = NULL;
361 entry->avail_out = NULL;
362 entry->id_2_memop_avail = NULL;
363 entry->anticL_in = NULL;
364 entry->id_2_memop_antic = NULL;
366 entry->forward_next = NULL;
367 entry->backward_next = NULL;
369 entry->trans_results = NULL;
370 set_irn_link(irn, entry);
372 set_Block_phis(irn, NULL);
374 /* use block marks to track unreachable blocks */
375 set_Block_mark(irn, 0);
377 n = get_Block_n_cfgpreds(irn);
378 if (n > env.max_cfg_preds)
379 env.max_cfg_preds = n;
381 ir_mode *mode = get_irn_mode(irn);
383 if (mode_is_reference(mode)) {
385 * Register ALL possible addresses: this is overkill yet but
386 * simpler then doing it for all possible translated addresses
387 * (which would be sufficient in the moment.
389 (void)register_address(irn);
392 } /* prepare_blocks */
395 * Post-Walker, link in all Phi's
397 static void link_phis(ir_node *irn, void *ctx)
402 ir_node *block = get_nodes_block(irn);
403 add_Block_phi(block, irn);
408 * Block walker: creates the inverse post-order list for the CFG.
410 static void inverse_post_order(ir_node *block, void *ctx)
412 block_t *entry = get_block_entry(block);
416 /* mark this block IS reachable from start */
417 set_Block_mark(block, 1);
419 /* create the list in inverse order */
420 entry->forward_next = env.forward;
423 /* remember the first visited (last in list) entry, needed for later */
424 if (env.backward == NULL)
425 env.backward = entry;
426 } /* inverse_post_order */
429 * Block walker: create backward links for the memops of a block.
431 static void collect_backward(ir_node *block, void *ctx)
433 block_t *entry = get_block_entry(block);
439 * Do NOT link in the end block yet. We want it to be
440 * the first in the list. This is NOT guaranteed by the walker
441 * if we have endless loops.
443 if (block != env.end_bl) {
444 entry->backward_next = env.backward;
446 /* create the list in inverse order */
447 env.backward = entry;
450 /* create backward links for all memory ops */
452 for (op = entry->memop_forward; op != NULL; op = op->next) {
456 entry->memop_backward = last;
457 } /* collect_backward */
462 * @param irn the IR-node representing the memop or NULL
463 * if this is a translated (virtual) memop
465 * @return the allocated memop
467 static memop_t *alloc_memop(ir_node *irn)
469 memop_t *m = OALLOC(&env.obst, memop_t);
471 m->value.address = NULL;
472 m->value.value = NULL;
473 m->value.mode = NULL;
481 memset(m->projs, 0, sizeof(m->projs));
484 set_irn_link(irn, m);
489 * Create a memop for a Phi-replacement.
491 * @param op the memop to clone
492 * @param phi the Phi-node representing the new value
494 static memop_t *clone_memop_phi(memop_t *op, ir_node *phi)
496 memop_t *m = OALLOC(&env.obst, memop_t);
498 m->value = op->value;
499 m->value.value = phi;
506 set_irn_link(phi, m);
508 } /* clone_memop_phi */
511 * Return the memory properties of a call node.
513 * @param call the call node
515 * return a bitset of mtp_property_const and mtp_property_pure
517 static unsigned get_Call_memory_properties(ir_node *call)
519 ir_type *call_tp = get_Call_type(call);
520 unsigned prop = get_method_additional_properties(call_tp);
522 /* check first the call type */
523 if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
524 /* try the called entity */
525 ir_node *ptr = get_Call_ptr(call);
527 if (is_SymConst_addr_ent(ptr)) {
528 ir_entity *ent = get_SymConst_entity(ptr);
530 prop = get_entity_additional_properties(ent);
533 return prop & (mtp_property_const|mtp_property_pure);
534 } /* get_Call_memory_properties */
537 * Returns an entity if the address ptr points to a constant one.
539 * @param ptr the address
541 * @return an entity or NULL
543 static ir_entity *find_constant_entity(ir_node *ptr)
546 if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
547 return get_SymConst_entity(ptr);
548 } else if (is_Sel(ptr)) {
549 ir_entity *ent = get_Sel_entity(ptr);
550 ir_type *tp = get_entity_owner(ent);
552 /* Do not fiddle with polymorphism. */
553 if (is_Class_type(get_entity_owner(ent)) &&
554 ((get_entity_n_overwrites(ent) != 0) ||
555 (get_entity_n_overwrittenby(ent) != 0) ) )
558 if (is_Array_type(tp)) {
562 for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
564 ir_tarval *tlower, *tupper;
565 ir_node *index = get_Sel_index(ptr, i);
566 ir_tarval *tv = computed_value(index);
568 /* check if the index is constant */
569 if (tv == tarval_bad)
572 bound = get_array_lower_bound(tp, i);
573 tlower = computed_value(bound);
574 bound = get_array_upper_bound(tp, i);
575 tupper = computed_value(bound);
577 if (tlower == tarval_bad || tupper == tarval_bad)
580 if (tarval_cmp(tv, tlower) == ir_relation_less)
582 if (tarval_cmp(tupper, tv) == ir_relation_less)
585 /* ok, bounds check finished */
589 if (get_entity_linkage(ent) == IR_LINKAGE_CONSTANT)
593 ptr = get_Sel_ptr(ptr);
594 } else if (is_Add(ptr)) {
595 ir_node *l = get_Add_left(ptr);
596 ir_node *r = get_Add_right(ptr);
598 if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
600 else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l))
605 /* for now, we support only one addition, reassoc should fold all others */
606 if (! is_SymConst(ptr) && !is_Sel(ptr))
608 } else if (is_Sub(ptr)) {
609 ir_node *l = get_Sub_left(ptr);
610 ir_node *r = get_Sub_right(ptr);
612 if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
616 /* for now, we support only one subtraction, reassoc should fold all others */
617 if (! is_SymConst(ptr) && !is_Sel(ptr))
622 } /* find_constant_entity */
625 * Return the Selection index of a Sel node from dimension n
627 static long get_Sel_array_index_long(ir_node *n, int dim)
629 ir_node *index = get_Sel_index(n, dim);
630 assert(is_Const(index));
631 return get_tarval_long(get_Const_tarval(index));
632 } /* get_Sel_array_index_long */
635 * Returns the accessed component graph path for an
636 * node computing an address.
638 * @param ptr the node computing the address
639 * @param depth current depth in steps upward from the root
642 static compound_graph_path *rec_get_accessed_path(ir_node *ptr, size_t depth)
644 compound_graph_path *res = NULL;
645 ir_entity *root, *field, *ent;
646 size_t path_len, pos, idx;
650 if (is_SymConst(ptr)) {
651 /* a SymConst. If the depth is 0, this is an access to a global
652 * entity and we don't need a component path, else we know
653 * at least its length.
655 assert(get_SymConst_kind(ptr) == symconst_addr_ent);
656 root = get_SymConst_entity(ptr);
657 res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
658 } else if (is_Sel(ptr)) {
659 /* it's a Sel, go up until we find the root */
660 res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
664 /* fill up the step in the path at the current position */
665 field = get_Sel_entity(ptr);
666 path_len = get_compound_graph_path_length(res);
667 pos = path_len - depth - 1;
668 set_compound_graph_path_node(res, pos, field);
670 if (is_Array_type(get_entity_owner(field))) {
671 assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
672 set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
674 } else if (is_Add(ptr)) {
679 ir_node *l = get_Add_left(ptr);
680 ir_node *r = get_Add_right(ptr);
681 if (is_Const(r) && get_irn_mode(l) == get_irn_mode(ptr)) {
683 tv = get_Const_tarval(r);
686 tv = get_Const_tarval(l);
690 mode = get_tarval_mode(tv);
693 /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
695 field = get_Sel_entity(ptr);
697 field = get_SymConst_entity(ptr);
700 for (ent = field;;) {
702 ir_tarval *sz, *tv_index, *tlower, *tupper;
705 tp = get_entity_type(ent);
706 if (! is_Array_type(tp))
708 ent = get_array_element_entity(tp);
709 size = get_type_size_bytes(get_entity_type(ent));
710 sz = new_tarval_from_long(size, mode);
712 tv_index = tarval_div(tmp, sz);
713 tmp = tarval_mod(tmp, sz);
715 if (tv_index == tarval_bad || tmp == tarval_bad)
718 assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
719 bound = get_array_lower_bound(tp, 0);
720 tlower = computed_value(bound);
721 bound = get_array_upper_bound(tp, 0);
722 tupper = computed_value(bound);
724 if (tlower == tarval_bad || tupper == tarval_bad)
727 if (tarval_cmp(tv_index, tlower) == ir_relation_less)
729 if (tarval_cmp(tupper, tv_index) == ir_relation_less)
732 /* ok, bounds check finished */
735 if (! tarval_is_null(tmp)) {
736 /* access to some struct/union member */
740 /* should be at least ONE array */
744 res = rec_get_accessed_path(ptr, depth + idx);
748 path_len = get_compound_graph_path_length(res);
749 pos = path_len - depth - idx;
751 for (ent = field;;) {
753 ir_tarval *sz, *tv_index;
756 tp = get_entity_type(ent);
757 if (! is_Array_type(tp))
759 ent = get_array_element_entity(tp);
760 set_compound_graph_path_node(res, pos, ent);
762 size = get_type_size_bytes(get_entity_type(ent));
763 sz = new_tarval_from_long(size, mode);
765 tv_index = tarval_div(tv, sz);
766 tv = tarval_mod(tv, sz);
768 /* worked above, should work again */
769 assert(tv_index != tarval_bad && tv != tarval_bad);
771 /* bounds already checked above */
772 index = get_tarval_long(tv_index);
773 set_compound_graph_path_array_index(res, pos, index);
776 } else if (is_Sub(ptr)) {
777 ir_node *l = get_Sub_left(ptr);
778 ir_node *r = get_Sub_right(ptr);
781 tv = get_Const_tarval(r);
786 } /* rec_get_accessed_path */
789 * Returns an access path or NULL. The access path is only
790 * valid, if the graph is in phase_high and _no_ address computation is used.
792 static compound_graph_path *get_accessed_path(ir_node *ptr)
794 compound_graph_path *gr = rec_get_accessed_path(ptr, 0);
796 } /* get_accessed_path */
798 typedef struct path_entry {
800 struct path_entry *next;
804 static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next)
806 path_entry entry, *p;
807 ir_entity *ent, *field;
808 ir_initializer_t *initializer;
814 if (is_SymConst(ptr)) {
816 ent = get_SymConst_entity(ptr);
817 initializer = get_entity_initializer(ent);
818 for (p = next; p != NULL;) {
819 if (initializer->kind != IR_INITIALIZER_COMPOUND)
821 n = get_initializer_compound_n_entries(initializer);
822 tp = get_entity_type(ent);
824 if (is_Array_type(tp)) {
825 ent = get_array_element_entity(tp);
830 initializer = get_initializer_compound_value(initializer, 0);
836 initializer = get_initializer_compound_value(initializer, p->index);
841 tp = get_entity_type(ent);
842 while (is_Array_type(tp)) {
843 ent = get_array_element_entity(tp);
844 tp = get_entity_type(ent);
846 n = get_initializer_compound_n_entries(initializer);
849 initializer = get_initializer_compound_value(initializer, 0);
852 switch (initializer->kind) {
853 case IR_INITIALIZER_CONST:
854 return get_initializer_const_value(initializer);
855 case IR_INITIALIZER_TARVAL:
856 case IR_INITIALIZER_NULL:
860 } else if (is_Sel(ptr)) {
861 entry.ent = field = get_Sel_entity(ptr);
862 tp = get_entity_owner(field);
863 if (is_Array_type(tp)) {
864 assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
865 entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
867 size_t i, n_members = get_compound_n_members(tp);
868 for (i = 0; i < n_members; ++i) {
869 if (get_compound_member(tp, i) == field)
872 if (i >= n_members) {
873 /* not found: should NOT happen */
878 return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry);
879 } else if (is_Add(ptr)) {
884 ir_node *l = get_Add_left(ptr);
885 ir_node *r = get_Add_right(ptr);
888 tv = get_Const_tarval(r);
891 tv = get_Const_tarval(l);
895 mode = get_tarval_mode(tv);
897 /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
899 field = get_Sel_entity(ptr);
901 field = get_SymConst_entity(ptr);
904 /* count needed entries */
906 for (ent = field;;) {
907 tp = get_entity_type(ent);
908 if (! is_Array_type(tp))
910 ent = get_array_element_entity(tp);
913 /* should be at least ONE entry */
917 /* allocate the right number of entries */
918 NEW_ARR_A(path_entry, p, pos);
922 for (ent = field;;) {
924 ir_tarval *sz, *tv_index, *tlower, *tupper;
928 tp = get_entity_type(ent);
929 if (! is_Array_type(tp))
931 ent = get_array_element_entity(tp);
933 p[pos].next = &p[pos + 1];
935 size = get_type_size_bytes(get_entity_type(ent));
936 sz = new_tarval_from_long(size, mode);
938 tv_index = tarval_div(tv, sz);
939 tv = tarval_mod(tv, sz);
941 if (tv_index == tarval_bad || tv == tarval_bad)
944 assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
945 bound = get_array_lower_bound(tp, 0);
946 tlower = computed_value(bound);
947 bound = get_array_upper_bound(tp, 0);
948 tupper = computed_value(bound);
950 if (tlower == tarval_bad || tupper == tarval_bad)
953 if (tarval_cmp(tv_index, tlower) == ir_relation_less)
955 if (tarval_cmp(tupper, tv_index) == ir_relation_less)
958 /* ok, bounds check finished */
959 index = get_tarval_long(tv_index);
960 p[pos].index = index;
963 if (! tarval_is_null(tv)) {
964 /* hmm, wrong access */
967 p[pos - 1].next = next;
968 return rec_find_compound_ent_value(ptr, p);
969 } else if (is_Sub(ptr)) {
970 ir_node *l = get_Sub_left(ptr);
971 ir_node *r = get_Sub_right(ptr);
974 tv = get_Const_tarval(r);
979 } /* rec_find_compound_ent_value */
981 static ir_node *find_compound_ent_value(ir_node *ptr)
983 return rec_find_compound_ent_value(ptr, NULL);
984 } /* find_compound_ent_value */
987 * Mark a Load memop to be replace by a definition
989 * @param op the Load memop
991 static void mark_replace_load(memop_t *op, ir_node *def)
994 op->flags |= FLAG_KILLED_NODE;
996 } /* mark_replace_load */
999 * Mark a Store memop to be removed.
1001 * @param op the Store memop
1003 static void mark_remove_store(memop_t *op)
1005 op->flags |= FLAG_KILLED_NODE;
1007 } /* mark_remove_store */
1010 * Update a memop for a Load.
1012 * @param m the memop
1014 static void update_Load_memop(memop_t *m)
1017 ir_node *load = m->node;
1021 if (get_Load_volatility(load) == volatility_is_volatile)
1022 m->flags |= FLAG_IGNORE;
1024 ptr = get_Load_ptr(load);
1026 m->value.address = ptr;
1028 for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
1029 ir_node *proj = get_irn_out(load, i);
1032 /* beware of keep edges */
1036 pn = get_Proj_proj(proj);
1037 m->projs[pn] = proj;
1040 m->value.value = proj;
1041 m->value.mode = get_irn_mode(proj);
1043 case pn_Load_X_except:
1044 m->flags |= FLAG_EXCEPTION;
1049 case pn_Load_X_regular:
1052 panic("Unsupported Proj from Load %+F", proj);
1056 /* check if we can determine the entity that will be loaded */
1057 ent = find_constant_entity(ptr);
1059 if (ent != NULL && get_entity_visibility(ent) != ir_visibility_external) {
1060 /* a static allocation that is not external: there should be NO exception
1061 * when loading even if we cannot replace the load itself. */
1062 ir_node *value = NULL;
1064 /* no exception, clear the m fields as it might be checked later again */
1065 if (m->projs[pn_Load_X_except]) {
1066 ir_graph *irg = get_irn_irg(ptr);
1067 exchange(m->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
1068 m->projs[pn_Load_X_except] = NULL;
1069 m->flags &= ~FLAG_EXCEPTION;
1072 if (m->projs[pn_Load_X_regular]) {
1073 exchange(m->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1074 m->projs[pn_Load_X_regular] = NULL;
1078 if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT) {
1079 if (ent->initializer) {
1080 /* new style initializer */
1081 value = find_compound_ent_value(ptr);
1082 } else if (entity_has_compound_ent_values(ent)) {
1083 /* old style initializer */
1084 compound_graph_path *path = get_accessed_path(ptr);
1087 assert(is_proper_compound_graph_path(path, get_compound_graph_path_length(path)-1));
1089 value = get_compound_ent_value_by_path(ent, path);
1090 DB((dbg, LEVEL_1, " Constant access at %F%F resulted in %+F\n", ent, path, value));
1091 free_compound_graph_path(path);
1095 value = can_replace_load_by_const(load, value);
1098 if (value != NULL) {
1099 /* we completely replace the load by this value */
1100 DB((dbg, LEVEL_1, "Replacing Load %+F by constant %+F\n", m->node, value));
1101 mark_replace_load(m, value);
1106 if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) {
1107 /* only create an address if this node is NOT killed immediately or ignored */
1108 m->value.id = register_address(ptr);
1111 /* no user, KILL it */
1112 mark_replace_load(m, NULL);
1114 } /* update_Load_memop */
1117 * Update a memop for a Store.
1119 * @param m the memop
1121 static void update_Store_memop(memop_t *m)
1124 ir_node *store = m->node;
1125 ir_node *adr = get_Store_ptr(store);
1127 if (get_Store_volatility(store) == volatility_is_volatile) {
1128 m->flags |= FLAG_IGNORE;
1130 /* only create an address if this node is NOT ignored */
1131 m->value.id = register_address(adr);
1135 m->value.address = adr;
1137 for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
1138 ir_node *proj = get_irn_out(store, i);
1141 /* beware of keep edges */
1145 pn = get_Proj_proj(proj);
1146 m->projs[pn] = proj;
1148 case pn_Store_X_except:
1149 m->flags |= FLAG_EXCEPTION;
1154 case pn_Store_X_regular:
1157 panic("Unsupported Proj from Store %+F", proj);
1160 m->value.value = get_Store_value(store);
1161 m->value.mode = get_irn_mode(m->value.value);
1162 } /* update_Store_memop */
1165 * Update a memop for a Call.
1167 * @param m the memop
1169 static void update_Call_memop(memop_t *m)
1171 ir_node *call = m->node;
1172 unsigned prop = get_Call_memory_properties(call);
1175 if (prop & mtp_property_const) {
1176 /* A constant call did NOT use memory at all, we
1177 can kick it from the list. */
1178 } else if (prop & mtp_property_pure) {
1179 /* pure calls READ memory */
1182 m->flags = FLAG_KILL_ALL;
1184 for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
1185 ir_node *proj = get_irn_out(call, i);
1187 /* beware of keep edges */
1191 switch (get_Proj_proj(proj)) {
1192 case pn_Call_X_except:
1193 m->flags |= FLAG_EXCEPTION;
1200 } /* update_Call_memop */
1203 * Update a memop for a Div/Mod.
1205 * @param m the memop
1207 static void update_Div_memop(memop_t *m)
1209 ir_node *div = m->node;
1212 for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
1213 ir_node *proj = get_irn_out(div, i);
1215 /* beware of keep edges */
1219 switch (get_Proj_proj(proj)) {
1220 case pn_Div_X_except:
1221 m->flags |= FLAG_EXCEPTION;
1230 static void update_Mod_memop(memop_t *m)
1232 ir_node *div = m->node;
1235 for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
1236 ir_node *proj = get_irn_out(div, i);
1238 /* beware of keep edges */
1242 switch (get_Proj_proj(proj)) {
1243 case pn_Mod_X_except:
1244 m->flags |= FLAG_EXCEPTION;
1254 * Update a memop for a Phi.
1256 * @param m the memop
1258 static void update_Phi_memop(memop_t *m)
1260 /* the Phi is its own mem */
1262 } /* update_Phi_memop */
1265 * Memory walker: collect all memory ops and build topological lists.
1267 static void collect_memops(ir_node *irn, void *ctx)
1275 /* we can safely ignore ProjM's except the initial memory */
1276 ir_graph *irg = get_irn_irg(irn);
1277 if (irn != get_irg_initial_mem(irg))
1281 op = alloc_memop(irn);
1282 block = get_nodes_block(irn);
1283 entry = get_block_entry(block);
1286 update_Phi_memop(op);
1287 /* Phis must be always placed first */
1288 op->next = entry->memop_forward;
1289 entry->memop_forward = op;
1290 if (entry->memop_backward == NULL)
1291 entry->memop_backward = op;
1293 switch (get_irn_opcode(irn)) {
1295 update_Load_memop(op);
1298 update_Store_memop(op);
1301 update_Call_memop(op);
1308 /* initial memory */
1313 /* we can those to find the memory edge */
1316 update_Div_memop(op);
1319 update_Mod_memop(op);
1323 /* TODO: handle some builtins */
1325 /* unsupported operation */
1326 op->flags = FLAG_KILL_ALL;
1330 /* all other should be placed last */
1331 if (entry->memop_backward == NULL) {
1332 entry->memop_forward = entry->memop_backward = op;
1334 entry->memop_backward->next = op;
1335 entry->memop_backward = op;
1338 } /* collect_memops */
1341 * Find an address in the current set.
1343 * @param value the value to be searched for
1345 * @return a memop for the value or NULL if the value does
1346 * not exists in the set or cannot be converted into
1347 * the requested mode
1349 static memop_t *find_address(const value_t *value)
1351 if (rbitset_is_set(env.curr_set, value->id)) {
1352 memop_t *res = env.curr_id_2_memop[value->id];
1354 if (res->value.mode == value->mode)
1356 /* allow hidden casts */
1357 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
1358 get_mode_arithmetic(value->mode) == irma_twos_complement &&
1359 get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
1363 } /* find_address */
1366 * Find an address in the avail_out set.
1368 * @param bl the block
1370 static memop_t *find_address_avail(const block_t *bl, unsigned id, const ir_mode *mode)
1372 if (rbitset_is_set(bl->avail_out, id)) {
1373 memop_t *res = bl->id_2_memop_avail[id];
1375 if (res->value.mode == mode)
1377 /* allow hidden casts */
1378 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
1379 get_mode_arithmetic(mode) == irma_twos_complement &&
1380 get_mode_size_bits(res->value.mode) == get_mode_size_bits(mode))
1384 } /* find_address_avail */
1387 * Kill all addresses from the current set.
1389 static void kill_all(void)
1391 rbitset_clear_all(env.curr_set, env.rbs_size);
1394 rbitset_set(env.curr_set, env.rbs_size - 1);
1398 * Kill memops that are not alias free due to a Store value from the current set.
1400 * @param value the Store value
1402 static void kill_memops(const value_t *value)
1404 size_t end = env.rbs_size - 1;
1407 for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
1408 memop_t *op = env.curr_id_2_memop[pos];
1410 if (ir_no_alias != get_alias_relation(value->address, value->mode,
1411 op->value.address, op->value.mode)) {
1412 rbitset_clear(env.curr_set, pos);
1413 env.curr_id_2_memop[pos] = NULL;
1414 DB((dbg, LEVEL_2, "KILLING %+F because of possible alias address %+F\n", op->node, value->address));
1420 * Add the value of a memop to the current set.
1422 * @param op the memory op
1424 static void add_memop(memop_t *op)
1426 rbitset_set(env.curr_set, op->value.id);
1427 env.curr_id_2_memop[op->value.id] = op;
1431 * Add the value of a memop to the avail_out set.
1433 * @param bl the block
1434 * @param op the memory op
1436 static void add_memop_avail(block_t *bl, memop_t *op)
1438 rbitset_set(bl->avail_out, op->value.id);
1439 bl->id_2_memop_avail[op->value.id] = op;
1440 } /* add_memop_avail */
1443 * Check, if we can convert a value of one mode to another mode
1444 * without changing the representation of bits.
1446 * @param from the original mode
1447 * @param to the destination mode
1449 static int can_convert_to(const ir_mode *from, const ir_mode *to)
1451 if (get_mode_arithmetic(from) == irma_twos_complement &&
1452 get_mode_arithmetic(to) == irma_twos_complement &&
1453 get_mode_size_bits(from) == get_mode_size_bits(to))
1456 } /* can_convert_to */
1459 * Add a Conv to the requested mode if needed.
1461 * @param irn the IR-node to convert
1462 * @param mode the destination mode
1464 * @return the possible converted node or NULL
1465 * if the conversion is not possible
1467 static ir_node *conv_to(ir_node *irn, ir_mode *mode)
1469 ir_mode *other = get_irn_mode(irn);
1470 if (other != mode) {
1471 /* different modes: check if conversion is possible without changing the bits */
1472 if (can_convert_to(other, mode)) {
1473 ir_node *block = get_nodes_block(irn);
1474 return new_r_Conv(block, irn, mode);
1476 /* otherwise not possible ... yet */
1483 * Update the address of an value if this address was a load result
1484 * and the load is killed now.
1486 * @param value the value whose address is updated
1488 static void update_address(value_t *value)
1490 if (is_Proj(value->address)) {
1491 ir_node *load = get_Proj_pred(value->address);
1493 if (is_Load(load)) {
1494 const memop_t *op = get_irn_memop(load);
1496 if (op->flags & FLAG_KILLED_NODE)
1497 value->address = op->replace;
1500 } /* update_address */
1503 * Do forward dataflow analysis on the given block and calculate the
1504 * GEN and KILL in the current (avail) set.
1506 * @param bl the block
1508 static void calc_gen_kill_avail(block_t *bl)
1513 for (op = bl->memop_forward; op != NULL; op = op->next) {
1514 switch (get_irn_opcode(op->node)) {
1522 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
1523 /* do we have this already? */
1526 update_address(&op->value);
1527 other = find_address(&op->value);
1528 if (other != NULL && other != op) {
1529 def = conv_to(other->value.value, op->value.mode);
1531 #ifdef DEBUG_libfirm
1532 if (is_Store(other->node)) {
1534 DB((dbg, LEVEL_1, "RAW %+F <- %+F(%+F)\n", op->node, def, other->node));
1537 DB((dbg, LEVEL_1, "RAR %+F <- %+F(%+F)\n", op->node, def, other->node));
1540 mark_replace_load(op, def);
1541 /* do NOT change the memop table */
1545 /* add this value */
1550 if (! (op->flags & FLAG_KILLED_NODE)) {
1551 /* do we have this store already */
1554 update_address(&op->value);
1555 other = find_address(&op->value);
1556 if (other != NULL) {
1557 if (is_Store(other->node)) {
1558 if (op != other && !(other->flags & FLAG_IGNORE) &&
1559 get_nodes_block(other->node) == get_nodes_block(op->node)) {
1561 * A WAW in the same block we can kick the first store.
1562 * This is a shortcut: we know that the second Store will be anticipated
1565 DB((dbg, LEVEL_1, "WAW %+F <- %+F\n", other->node, op->node));
1566 mark_remove_store(other);
1567 /* FIXME: a Load might be get freed due to this killed store */
1569 } else if (other->value.value == op->value.value && !(op->flags & FLAG_IGNORE)) {
1571 DB((dbg, LEVEL_1, "WAR %+F <- %+F\n", op->node, other->node));
1572 mark_remove_store(op);
1573 /* do NOT change the memop table */
1577 /* KILL all possible aliases */
1578 kill_memops(&op->value);
1579 /* add this value */
1584 if (op->flags & FLAG_KILL_ALL)
1588 } /* calc_gen_kill_avail */
1590 #define BYTE_SIZE(x) (((x) + 7) >> 3)
1593 * Do forward dataflow analysis on a given block to calculate the avail_out set
1594 * for this block only.
1596 * @param block the block
1598 static void forward_avail(block_t *bl)
1600 /* fill the data from the current block */
1601 env.curr_id_2_memop = bl->id_2_memop_avail;
1602 env.curr_set = bl->avail_out;
1604 calc_gen_kill_avail(bl);
1605 dump_curr(bl, "Avail_out");
1606 } /* forward_avail */
1609 * Do backward dataflow analysis on a given block to calculate the antic set
1610 * of Loaded addresses.
1612 * @param bl the block
1614 * @return non-zero if the set has changed since last iteration
1616 static int backward_antic(block_t *bl)
1619 ir_node *block = bl->block;
1620 int n = get_Block_n_cfg_outs(block);
1623 ir_node *succ = get_Block_cfg_out(block, 0);
1624 block_t *succ_bl = get_block_entry(succ);
1625 int pred_pos = get_Block_cfgpred_pos(succ, block);
1626 size_t end = env.rbs_size - 1;
1631 if (bl->trans_results == NULL) {
1632 /* allocate the translate cache */
1633 bl->trans_results = OALLOCNZ(&env.obst, memop_t*, env.curr_adr_id);
1636 /* check for partly redundant values */
1637 for (pos = rbitset_next(succ_bl->anticL_in, 0, 1);
1639 pos = rbitset_next(succ_bl->anticL_in, pos + 1, 1)) {
1641 * do Phi-translation here: Note that at this point the nodes are
1642 * not changed, so we can safely cache the results.
1643 * However: Loads of Load results ARE bad, because we have no way
1644 to translate them yet ...
1646 memop_t *op = bl->trans_results[pos];
1648 /* not yet translated */
1649 ir_node *adr, *trans_adr;
1651 op = succ_bl->id_2_memop_antic[pos];
1652 adr = op->value.address;
1654 trans_adr = phi_translate(adr, succ, pred_pos);
1655 if (trans_adr != adr) {
1656 /* create a new entry for the translated one */
1659 new_op = alloc_memop(NULL);
1660 new_op->value.address = trans_adr;
1661 new_op->value.id = register_address(trans_adr);
1662 new_op->value.mode = op->value.mode;
1663 new_op->node = op->node; /* we need the node to decide if Load/Store */
1664 new_op->flags = op->flags;
1666 bl->trans_results[pos] = new_op;
1670 env.curr_id_2_memop[op->value.id] = op;
1671 rbitset_set(env.curr_set, op->value.id);
1674 ir_node *succ = get_Block_cfg_out(block, 0);
1675 block_t *succ_bl = get_block_entry(succ);
1678 rbitset_copy(env.curr_set, succ_bl->anticL_in, env.rbs_size);
1679 memcpy(env.curr_id_2_memop, succ_bl->id_2_memop_antic, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
1681 /* Hmm: probably we want kill merges of Loads ans Stores here */
1682 for (i = n - 1; i > 0; --i) {
1683 ir_node *succ = get_Block_cfg_out(bl->block, i);
1684 block_t *succ_bl = get_block_entry(succ);
1686 rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size);
1689 /* block ends with a noreturn call */
1693 dump_curr(bl, "AnticL_out");
1695 for (op = bl->memop_backward; op != NULL; op = op->prev) {
1696 switch (get_irn_opcode(op->node)) {
1704 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
1710 if (! (op->flags & FLAG_KILLED_NODE)) {
1711 /* a Store: check which memops must be killed */
1712 kill_memops(&op->value);
1716 if (op->flags & FLAG_KILL_ALL)
1721 memcpy(bl->id_2_memop_antic, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
1722 if (! rbitsets_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
1724 rbitset_copy(bl->anticL_in, env.curr_set, env.rbs_size);
1725 dump_curr(bl, "AnticL_in*");
1728 dump_curr(bl, "AnticL_in");
1730 } /* backward_antic */
1733 * Replace a Load memop by a already known value.
1735 * @param op the Load memop
1737 static void replace_load(memop_t *op)
1739 ir_node *load = op->node;
1740 ir_node *def = skip_Id(op->replace);
1745 DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, is_Proj(def) ? get_Proj_pred(def) : def));
1747 if (op->flags & FLAG_EXCEPTION) {
1748 /* bad: this node is unused and executed for exception only */
1749 DB((dbg, LEVEL_1, "Unused %+F executed for exception only ...\n", load));
1752 DB((dbg, LEVEL_1, "Killing unused %+F\n", load));
1755 if (op->mem != NULL) {
1756 /* in rare cases a Load might have NO memory */
1757 exchange(op->mem, get_Load_mem(load));
1759 proj = op->projs[pn_Load_res];
1761 mode = get_irn_mode(proj);
1762 if (get_irn_mode(def) != mode) {
1764 dbg_info *db = get_irn_dbg_info(load);
1765 ir_node *block = get_nodes_block(proj);
1766 def = new_rd_Conv(db, block, def, mode);
1768 exchange(proj, def);
1770 proj = op->projs[pn_Load_X_except];
1772 ir_graph *irg = get_irn_irg(load);
1773 exchange(proj, new_r_Bad(irg, mode_X));
1775 proj = op->projs[pn_Load_X_regular];
1777 exchange(proj, new_r_Jmp(get_nodes_block(load)));
1779 } /* replace_load */
1782 * Remove a Store memop.
1784 * @param op the Store memop
1786 static void remove_store(memop_t *op)
1788 ir_node *store = op->node;
1791 DB((dbg, LEVEL_1, "Removing %+F\n", store));
1793 if (op->mem != NULL) {
1794 /* in rare cases a Store might have no memory */
1795 exchange(op->mem, get_Store_mem(store));
1797 proj = op->projs[pn_Store_X_except];
1799 ir_graph *irg = get_irn_irg(store);
1800 exchange(proj, new_r_Bad(irg, mode_X));
1802 proj = op->projs[pn_Store_X_regular];
1804 exchange(proj, new_r_Jmp(get_nodes_block(store)));
1806 } /* remove_store */
1810 * Do all necessary replacements for a given block.
1812 * @param bl the block
1814 static void do_replacements(block_t *bl)
1818 for (op = bl->memop_forward; op != NULL; op = op->next) {
1819 if (op->flags & FLAG_KILLED_NODE) {
1820 switch (get_irn_opcode(op->node)) {
1830 } /* do_replacements */
1833 * Calculate the Avail_out sets for all basic blocks.
1835 static void calcAvail(void)
1837 memop_t **tmp_memop = env.curr_id_2_memop;
1838 unsigned *tmp_set = env.curr_set;
1841 /* calculate avail_out */
1842 DB((dbg, LEVEL_2, "Calculate Avail_out\n"));
1844 /* iterate over all blocks in in any order, skip the start block */
1845 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1849 /* restore the current sets */
1850 env.curr_id_2_memop = tmp_memop;
1851 env.curr_set = tmp_set;
1855 * Calculate the Antic_in sets for all basic blocks.
1857 static void calcAntic(void)
1861 /* calculate antic_out */
1862 DB((dbg, LEVEL_2, "Calculate Antic_in\n"));
1867 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1871 /* over all blocks in reverse post order */
1872 for (bl = env.backward->backward_next; bl != NULL; bl = bl->backward_next) {
1873 need_iter |= backward_antic(bl);
1876 } while (need_iter);
1877 DB((dbg, LEVEL_2, "Get anticipated Load set after %d iterations\n", i));
1881 * Return the node representing the last memory in a block.
1883 * @param bl the block
1885 static ir_node *find_last_memory(block_t *bl)
1888 if (bl->memop_backward != NULL) {
1889 return bl->memop_backward->mem;
1891 /* if there is NO memory in this block, go to the dominator */
1892 bl = get_block_entry(get_Block_idom(bl->block));
1894 } /* find_last_memory */
1897 * Reroute all memory users of old memory
1898 * to a new memory IR-node.
1900 * @param omem the old memory IR-node
1901 * @param nmem the new memory IR-node
1903 static void reroute_all_mem_users(ir_node *omem, ir_node *nmem)
1907 for (i = get_irn_n_outs(omem) - 1; i >= 0; --i) {
1909 ir_node *user = get_irn_out_ex(omem, i, &n_pos);
1911 set_irn_n(user, n_pos, nmem);
1914 /* all edges previously point to omem now point to nmem */
1915 nmem->out = omem->out;
1916 } /* reroute_all_mem_users */
1919 * Reroute memory users of old memory that are dominated by a given block
1920 * to a new memory IR-node.
1922 * @param omem the old memory IR-node
1923 * @param nmem the new memory IR-node
1924 * @param pass_bl the block the memory must pass
1926 static void reroute_mem_through(ir_node *omem, ir_node *nmem, ir_node *pass_bl)
1928 int i, j, n = get_irn_n_outs(omem);
1929 ir_def_use_edge *edges = NEW_ARR_D(ir_def_use_edge, &env.obst, n + 1);
1931 for (i = j = 0; i < n; ++i) {
1933 ir_node *user = get_irn_out_ex(omem, i, &n_pos);
1934 ir_node *use_bl = get_nodes_block(user);
1938 use_bl = get_Block_cfgpred_block(use_bl, n_pos);
1940 if (block_dominates(pass_bl, use_bl)) {
1941 /* found an user that is dominated */
1943 edges[j].pos = n_pos;
1944 edges[j].use = user;
1946 set_irn_n(user, n_pos, nmem);
1950 /* Modify the out structure: we create a new out edge array on our
1951 temporary obstack here. This should be no problem, as we invalidate the edges
1952 at the end either. */
1953 /* first entry is used for the length */
1956 } /* reroute_mem_through */
1959 * insert Loads, making partly redundant Loads fully redundant
1961 static int insert_Load(block_t *bl)
1963 ir_node *block = bl->block;
1964 int i, n = get_Block_n_cfgpreds(block);
1965 size_t end = env.rbs_size - 1;
1967 DB((dbg, LEVEL_3, "processing %+F\n", block));
1970 /* might still happen for an unreachable block (end for instance) */
1978 NEW_ARR_A(ir_node *, ins, n);
1980 rbitset_set_all(env.curr_set, env.rbs_size);
1982 /* More than one predecessors, calculate the join for all avail_outs ignoring unevaluated
1983 Blocks. These put in Top anyway. */
1984 for (i = n - 1; i >= 0; --i) {
1985 ir_node *pred = skip_Proj(get_Block_cfgpred(block, i));
1986 ir_node *blk = get_nodes_block(pred);
1989 pred_bl = get_block_entry(blk);
1990 rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
1992 if (is_Load(pred) || is_Store(pred)) {
1993 /* We reached this block by an exception from a Load or Store:
1994 * the memop creating the exception was NOT completed than, kill it
1996 memop_t *exc_op = get_irn_memop(pred);
1997 rbitset_clear(env.curr_set, exc_op->value.id);
2002 * Ensure that all values are in the map: build Phi's if necessary:
2003 * Note: the last bit is the sentinel and ALWAYS set, so end with -2.
2005 for (pos = 0; pos < env.rbs_size - 1; ++pos) {
2006 if (! rbitset_is_set(env.curr_set, pos))
2007 env.curr_id_2_memop[pos] = NULL;
2009 ir_node *pred = get_Block_cfgpred_block(bl->block, 0);
2010 block_t *pred_bl = get_block_entry(pred);
2012 memop_t *first = NULL;
2013 ir_mode *mode = NULL;
2015 for (i = 0; i < n; ++i) {
2018 pred = get_Block_cfgpred_block(bl->block, i);
2019 pred_bl = get_block_entry(pred);
2021 mop = pred_bl->id_2_memop_avail[pos];
2022 if (first == NULL) {
2024 ins[0] = first->value.value;
2025 mode = get_irn_mode(ins[0]);
2027 /* no Phi needed so far */
2028 env.curr_id_2_memop[pos] = first;
2030 ins[i] = conv_to(mop->value.value, mode);
2031 if (ins[i] != ins[0]) {
2032 if (ins[i] == NULL) {
2033 /* conversion failed */
2034 env.curr_id_2_memop[pos] = NULL;
2035 rbitset_clear(env.curr_set, pos);
2044 ir_node *phi = new_r_Phi(bl->block, n, ins, mode);
2045 memop_t *phiop = alloc_memop(phi);
2047 phiop->value = first->value;
2048 phiop->value.value = phi;
2050 /* no need to link it in, as it is a DATA phi */
2052 env.curr_id_2_memop[pos] = phiop;
2054 DB((dbg, LEVEL_3, "Created new %+F on merging value for address %+F\n", phi, first->value.address));
2059 /* only one predecessor, simply copy the map */
2060 ir_node *pred = get_Block_cfgpred_block(bl->block, 0);
2061 block_t *pred_bl = get_block_entry(pred);
2063 rbitset_copy(env.curr_set, pred_bl->avail_out, env.rbs_size);
2065 memcpy(env.curr_id_2_memop, pred_bl->id_2_memop_avail, env.rbs_size * sizeof(bl->id_2_memop_avail[0]));
2071 /* check for partly redundant values */
2072 for (pos = rbitset_next(bl->anticL_in, 0, 1);
2074 pos = rbitset_next(bl->anticL_in, pos + 1, 1)) {
2075 memop_t *op = bl->id_2_memop_antic[pos];
2076 int have_some, all_same;
2079 if (rbitset_is_set(env.curr_set, pos)) {
2084 assert(is_Load(op->node));
2086 DB((dbg, LEVEL_3, "anticipated %+F\n", op->node));
2091 for (i = n - 1; i >= 0; --i) {
2092 ir_node *pred = get_Block_cfgpred_block(block, i);
2093 block_t *pred_bl = get_block_entry(pred);
2094 ir_mode *mode = op->value.mode;
2098 adr = phi_translate(op->value.address, block, i);
2099 DB((dbg, LEVEL_3, ".. using address %+F in pred %d\n", adr, i));
2100 e = find_address_avail(pred_bl, register_address(adr), mode);
2102 ir_node *ef_block = get_nodes_block(adr);
2103 if (! block_dominates(ef_block, pred)) {
2104 /* cannot place a copy here */
2106 DB((dbg, LEVEL_3, "%+F cannot be moved into predecessor %+F\n", op->node, pred));
2109 DB((dbg, LEVEL_3, "%+F is not available in predecessor %+F\n", op->node, pred));
2110 pred_bl->avail = NULL;
2113 if (e->value.mode != mode && !can_convert_to(e->value.mode, mode)) {
2114 /* cannot create a Phi due to different modes */
2120 DB((dbg, LEVEL_3, "%+F is available for %+F in predecessor %+F\n", e->node, op->node, pred));
2123 else if (first != e->node)
2127 if (have_some && !all_same) {
2128 ir_mode *mode = op->value.mode;
2132 NEW_ARR_A(ir_node *, in, n);
2134 for (i = n - 1; i >= 0; --i) {
2135 ir_node *pred = get_Block_cfgpred_block(block, i);
2136 block_t *pred_bl = get_block_entry(pred);
2138 if (pred_bl->avail == NULL) {
2139 /* create a new Load here and make to make it fully redundant */
2140 dbg_info *db = get_irn_dbg_info(op->node);
2141 ir_node *last_mem = find_last_memory(pred_bl);
2142 ir_node *load, *def, *adr;
2145 assert(last_mem != NULL);
2146 adr = phi_translate(op->value.address, block, i);
2147 load = new_rd_Load(db, pred, last_mem, adr, mode, cons_none);
2148 def = new_r_Proj(load, mode, pn_Load_res);
2149 DB((dbg, LEVEL_1, "Created new %+F in %+F for party redundant %+F\n", load, pred, op->node));
2151 new_op = alloc_memop(load);
2152 new_op->mem = new_r_Proj(load, mode_M, pn_Load_M);
2153 new_op->value.address = adr;
2154 new_op->value.id = op->value.id;
2155 new_op->value.mode = mode;
2156 new_op->value.value = def;
2158 new_op->projs[pn_Load_M] = new_op->mem;
2159 new_op->projs[pn_Load_res] = def;
2161 new_op->prev = pred_bl->memop_backward;
2162 if (pred_bl->memop_backward != NULL)
2163 pred_bl->memop_backward->next = new_op;
2165 pred_bl->memop_backward = new_op;
2167 if (pred_bl->memop_forward == NULL)
2168 pred_bl->memop_forward = new_op;
2170 if (get_nodes_block(last_mem) == pred) {
2171 /* We have add a new last memory op in pred block.
2172 If pred had already a last mem, reroute all memory
2174 reroute_all_mem_users(last_mem, new_op->mem);
2176 /* reroute only those memory going through the pre block */
2177 reroute_mem_through(last_mem, new_op->mem, pred);
2180 /* we added this load at the end, so it will be avail anyway */
2181 add_memop_avail(pred_bl, new_op);
2182 pred_bl->avail = new_op;
2184 in[i] = conv_to(pred_bl->avail->value.value, mode);
2186 phi = new_r_Phi(block, n, in, mode);
2187 DB((dbg, LEVEL_1, "Created new %+F in %+F for now redundant %+F\n", phi, block, op->node));
2189 phi_op = clone_memop_phi(op, phi);
2195 /* recalculate avail by gen and kill */
2196 calc_gen_kill_avail(bl);
2198 /* always update the map after gen/kill, as values might have been changed due to RAR/WAR/WAW */
2199 memcpy(bl->id_2_memop_avail, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
2201 if (!rbitsets_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
2202 /* the avail set has changed */
2203 rbitset_copy(bl->avail_out, env.curr_set, env.rbs_size);
2204 dump_curr(bl, "Avail_out*");
2207 dump_curr(bl, "Avail_out");
2212 * Insert Loads upwards.
2214 static void insert_Loads_upwards(void)
2219 /* recalculate antic_out and insert Loads */
2220 DB((dbg, LEVEL_2, "Inserting Loads\n"));
2224 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
2228 /* over all blocks in reverse post order, skip the start block */
2229 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
2230 need_iter |= insert_Load(bl);
2233 } while (need_iter);
2235 DB((dbg, LEVEL_2, "Finished Load inserting after %d iterations\n", i));
2236 } /* insert_Loads_upwards */
2239 * Kill unreachable control flow.
2241 * @param irg the graph to operate on
2243 static void kill_unreachable_blocks(ir_graph *irg)
2249 NEW_ARR_A(ir_node *, ins, env.max_cfg_preds);
2251 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2252 ir_node *block = bl->block;
2255 assert(get_Block_mark(block));
2257 n = get_Block_n_cfgpreds(block);
2259 for (i = j = 0; i < n; ++i) {
2260 ir_node *pred = get_Block_cfgpred(block, i);
2266 pred_bl = get_nodes_block(skip_Proj(pred));
2267 if (! get_Block_mark(pred_bl))
2273 ir_node *phi, *next;
2275 /* some unreachable blocks detected */
2278 DB((dbg, LEVEL_1, "Killing dead block predecessors on %+F\n", block));
2280 set_irn_in(block, j, ins);
2282 /* shorten all Phi nodes */
2283 for (phi = get_Block_phis(block); phi != NULL; phi = next) {
2284 next = get_Phi_next(phi);
2286 for (i = k = 0; i < n; ++i) {
2287 ir_node *pred = get_Block_cfgpred_block(block, i);
2292 if (! get_Block_mark(pred))
2295 ins[k++] = get_Phi_pred(phi, i);
2298 exchange(phi, ins[0]);
2300 set_irn_in(phi, k, ins);
2307 /* kick keep alives */
2308 ir_node *end = get_irg_end(irg);
2309 int i, j, n = get_End_n_keepalives(end);
2311 NEW_ARR_A(ir_node *, ins, n);
2313 for (i = j = 0; i < n; ++i) {
2314 ir_node *ka = get_End_keepalive(end, i);
2322 ka_bl = get_nodes_block(skip_Proj(ka));
2323 if (get_Block_mark(ka_bl))
2327 set_End_keepalives(end, j, ins);
2331 /* this transformation do NOT invalidate the dominance */
2333 } /* kill_unreachable_blocks */
2335 int opt_ldst(ir_graph *irg)
2339 FIRM_DBG_REGISTER(dbg, "firm.opt.ldst");
2341 DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
2343 /* we need landing pads */
2344 remove_critical_cf_edges(irg);
2346 if (get_opt_alias_analysis()) {
2347 assure_irg_entity_usage_computed(irg);
2348 assure_irp_globals_entity_usage_computed();
2351 obstack_init(&env.obst);
2352 ir_nodehashmap_init(&env.adr_map);
2355 env.backward = NULL;
2356 env.curr_adr_id = 0;
2358 env.max_cfg_preds = 0;
2360 env.start_bl = get_irg_start_block(irg);
2361 env.end_bl = get_irg_end_block(irg);
2362 #ifdef DEBUG_libfirm
2363 env.id_2_address = NEW_ARR_F(ir_node *, 0);
2366 assure_irg_outs(irg);
2368 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
2370 /* first step: allocate block entries. Note that some blocks might be
2371 unreachable here. Using the normal walk ensures that ALL blocks are initialized. */
2372 irg_walk_graph(irg, prepare_blocks, link_phis, NULL);
2374 /* produce an inverse post-order list for the CFG: this links only reachable
2376 irg_out_block_walk(get_irg_start_block(irg), NULL, inverse_post_order, NULL);
2378 if (! get_Block_mark(env.end_bl)) {
2380 * The end block is NOT reachable due to endless loops
2381 * or no_return calls.
2382 * Place the end block last.
2383 * env.backward points to the last block in the list for this purpose.
2385 env.backward->forward_next = get_block_entry(env.end_bl);
2387 set_Block_mark(env.end_bl, 1);
2390 /* KILL unreachable blocks: these disturb the data flow analysis */
2391 kill_unreachable_blocks(irg);
2395 /* second step: find and sort all memory ops */
2396 walk_memory_irg(irg, collect_memops, NULL, NULL);
2398 #ifdef DEBUG_libfirm
2399 /* check that the backward map is correct */
2400 assert((unsigned)ARR_LEN(env.id_2_address) == env.curr_adr_id);
2403 if (env.n_mem_ops == 0) {
2408 /* create the backward links. */
2409 env.backward = NULL;
2410 irg_block_walk_graph(irg, NULL, collect_backward, NULL);
2412 /* link the end block in */
2413 bl = get_block_entry(env.end_bl);
2414 bl->backward_next = env.backward;
2417 /* check that we really start with the start / end block */
2418 assert(env.forward->block == env.start_bl);
2419 assert(env.backward->block == env.end_bl);
2421 /* create address sets: for now, only the existing addresses are allowed plus one
2422 needed for the sentinel */
2423 env.rbs_size = env.curr_adr_id + 1;
2425 /* create the current set */
2426 env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2427 rbitset_set(env.curr_set, env.rbs_size - 1);
2428 env.curr_id_2_memop = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
2429 memset(env.curr_id_2_memop, 0, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
2431 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2432 /* set sentinel bits */
2433 bl->avail_out = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2434 rbitset_set(bl->avail_out, env.rbs_size - 1);
2436 bl->id_2_memop_avail = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
2437 memset(bl->id_2_memop_avail, 0, env.rbs_size * sizeof(bl->id_2_memop_avail[0]));
2439 bl->anticL_in = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2440 rbitset_set(bl->anticL_in, env.rbs_size - 1);
2442 bl->id_2_memop_antic = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
2443 memset(bl->id_2_memop_antic, 0, env.rbs_size * sizeof(bl->id_2_memop_antic[0]));
2446 (void) dump_block_list;
2451 insert_Loads_upwards();
2454 /* over all blocks in reverse post order */
2455 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2456 do_replacements(bl);
2459 /* not only invalidate but free them. We might allocate new out arrays
2460 on our obstack which will be deleted yet. */
2462 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE);
2466 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
2467 ir_nodehashmap_destroy(&env.adr_map);
2468 obstack_free(&env.obst, NULL);
2470 #ifdef DEBUG_libfirm
2471 DEL_ARR_F(env.id_2_address);
2474 return env.changed != 0;
2477 ir_graph_pass_t *opt_ldst_pass(const char *name)
2479 return def_graph_pass_ret(name ? name : "ldst_df", opt_ldst);
2480 } /* opt_ldst_pass */