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 *end_bl; /**< end block of the current graph */
122 unsigned *curr_set; /**< current set of addresses */
123 memop_t **curr_id_2_memop; /**< current map of address ids to memops */
124 unsigned curr_adr_id; /**< number for address mapping */
125 unsigned n_mem_ops; /**< number of memory operations (Loads/Stores) */
126 size_t rbs_size; /**< size of all bitsets in bytes */
127 int max_cfg_preds; /**< maximum number of block cfg predecessors */
128 int changed; /**< Flags for changed graph state */
130 ir_node **id_2_address; /**< maps an id to the used address */
134 /* the one and only environment */
139 static firm_dbg_module_t *dbg;
142 * Dumps the block list.
144 * @param ldst environment
146 static void dump_block_list(ldst_env *env)
152 for (entry = env->forward; entry != NULL; entry = entry->forward_next) {
153 DB((dbg, LEVEL_2, "%+F {", entry->block));
156 for (op = entry->memop_forward; op != NULL; op = op->next) {
158 DB((dbg, LEVEL_2, "\n\t"));
160 DB((dbg, LEVEL_2, "%+F", op->node));
161 if ((op->flags & FLAG_KILL_ALL) == FLAG_KILL_ALL)
162 DB((dbg, LEVEL_2, "X"));
163 else if (op->flags & FLAG_KILL_ALL)
164 DB((dbg, LEVEL_2, "K"));
165 DB((dbg, LEVEL_2, ", "));
169 DB((dbg, LEVEL_2, "\n}\n\n"));
174 * Dumps the current set.
176 * @param bl current block
177 * @param s name of the set
179 static void dump_curr(block_t *bl, const char *s)
181 size_t end = env.rbs_size - 1;
185 DB((dbg, LEVEL_2, "%s[%+F] = {", s, bl->block));
187 for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
188 memop_t *op = env.curr_id_2_memop[pos];
191 DB((dbg, LEVEL_2, "\n\t"));
194 DB((dbg, LEVEL_2, "<%+F, %+F>, ", op->value.address, op->value.value));
197 DB((dbg, LEVEL_2, "\n}\n"));
201 static void dump_block_list(ldst_env *env)
205 static void dump_curr(block_t *bl, const char *s)
210 #endif /* DEBUG_libfirm */
212 /** Get the block entry for a block node */
213 static block_t *get_block_entry(const ir_node *block)
215 assert(is_Block(block));
217 return (block_t*)get_irn_link(block);
220 /** Get the memop entry for a memory operation node */
221 static memop_t *get_irn_memop(const ir_node *irn)
223 assert(! is_Block(irn));
224 return (memop_t*)get_irn_link(irn);
228 * Walk over the memory edges from definition to users.
229 * This ensures, that even operation without memory output are found.
231 * @param irn start node
232 * @param pre pre walker function
233 * @param post post walker function
234 * @param ctx context parameter for the walker functions
236 static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx)
240 mark_irn_visited(irn);
245 mode = get_irn_mode(irn);
246 if (mode == mode_M) {
247 /* every successor uses memory */
248 for (unsigned i = get_irn_n_outs(irn); i-- > 0; ) {
249 ir_node *succ = get_irn_out(irn, i);
251 if (! irn_visited(succ))
252 walk_memory(succ, pre, post, ctx);
254 } else if (mode == mode_T) {
255 /* only some Proj's uses memory */
256 for (unsigned i = get_irn_n_outs(irn); i-- > 0; ) {
257 ir_node *proj = get_irn_out(irn, i);
259 if (get_irn_mode(proj) == mode_M && ! irn_visited(proj))
260 walk_memory(proj, pre, post, ctx);
268 * Walks over all memory nodes of a graph.
271 * @param pre pre walker function
272 * @param post post walker function
273 * @param ctx context parameter for the walker functions
275 static void walk_memory_irg(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *ctx)
277 inc_irg_visited(irg);
279 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
282 * there are two possible sources for memory: initial_mem and nomem
283 * we ignore nomem as this should NOT change the memory
285 walk_memory(get_irg_initial_mem(irg), pre, post, ctx);
287 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
291 * Register an address and allocate a (sparse, 0..n) ID for it.
293 * @param adr the IR-node representing the address
295 * @return the allocated id
297 static unsigned register_address(ir_node *adr)
299 address_entry *entry;
303 if (is_Confirm(adr)) {
304 adr = get_Confirm_value(adr);
308 entry = ir_nodehashmap_get(address_entry, &env.adr_map, adr);
312 entry = OALLOC(&env.obst, address_entry);
314 entry->id = env.curr_adr_id++;
315 ir_nodehashmap_insert(&env.adr_map, adr, entry);
317 DB((dbg, LEVEL_3, "ADDRESS %+F has ID %u\n", adr, entry->id));
319 ARR_APP1(ir_node *, env.id_2_address, adr);
327 * translate an address through a Phi node into a given predecessor
330 * @param address the address
331 * @param block the block
332 * @param pos the position of the predecessor in block
334 static ir_node *phi_translate(ir_node *address, const ir_node *block, int pos)
336 if (is_Phi(address) && get_nodes_block(address) == block)
337 address = get_Phi_pred(address, pos);
342 * Walker: allocate an block entry for every block
343 * and register all potential addresses.
345 static void prepare_blocks(ir_node *irn, void *ctx)
350 block_t *entry = OALLOC(&env.obst, block_t);
353 entry->memop_forward = NULL;
354 entry->memop_backward = NULL;
355 entry->avail_out = NULL;
356 entry->id_2_memop_avail = NULL;
357 entry->anticL_in = NULL;
358 entry->id_2_memop_antic = NULL;
360 entry->forward_next = NULL;
361 entry->backward_next = NULL;
363 entry->trans_results = NULL;
364 set_irn_link(irn, entry);
366 set_Block_phis(irn, NULL);
368 /* use block marks to track unreachable blocks */
369 set_Block_mark(irn, 0);
371 n = get_Block_n_cfgpreds(irn);
372 if (n > env.max_cfg_preds)
373 env.max_cfg_preds = n;
375 ir_mode *mode = get_irn_mode(irn);
377 if (mode_is_reference(mode)) {
379 * Register ALL possible addresses: this is overkill yet but
380 * simpler then doing it for all possible translated addresses
381 * (which would be sufficient in the moment.
383 (void)register_address(irn);
389 * Post-Walker, link in all Phi's
391 static void link_phis(ir_node *irn, void *ctx)
396 ir_node *block = get_nodes_block(irn);
397 add_Block_phi(block, irn);
402 * Block walker: creates the inverse post-order list for the CFG.
404 static void inverse_post_order(ir_node *block, void *ctx)
406 block_t *entry = get_block_entry(block);
410 /* mark this block IS reachable from start */
411 set_Block_mark(block, 1);
413 /* create the list in inverse order */
414 entry->forward_next = env.forward;
417 /* remember the first visited (last in list) entry, needed for later */
418 if (env.backward == NULL)
419 env.backward = entry;
423 * Block walker: create backward links for the memops of a block.
425 static void collect_backward(ir_node *block, void *ctx)
427 block_t *entry = get_block_entry(block);
433 * Do NOT link in the end block yet. We want it to be
434 * the first in the list. This is NOT guaranteed by the walker
435 * if we have endless loops.
437 if (block != env.end_bl) {
438 entry->backward_next = env.backward;
440 /* create the list in inverse order */
441 env.backward = entry;
444 /* create backward links for all memory ops */
446 for (op = entry->memop_forward; op != NULL; op = op->next) {
450 entry->memop_backward = last;
456 * @param irn the IR-node representing the memop or NULL
457 * if this is a translated (virtual) memop
459 * @return the allocated memop
461 static memop_t *alloc_memop(ir_node *irn)
463 memop_t *m = OALLOC(&env.obst, memop_t);
465 m->value.address = NULL;
466 m->value.value = NULL;
467 m->value.mode = NULL;
475 memset(m->projs, 0, sizeof(m->projs));
478 set_irn_link(irn, m);
483 * Create a memop for a Phi-replacement.
485 * @param op the memop to clone
486 * @param phi the Phi-node representing the new value
488 static memop_t *clone_memop_phi(memop_t *op, ir_node *phi)
490 memop_t *m = OALLOC(&env.obst, memop_t);
492 m->value = op->value;
493 m->value.value = phi;
500 set_irn_link(phi, m);
505 * Return the memory properties of a call node.
507 * @param call the call node
509 * return a bitset of mtp_property_const and mtp_property_pure
511 static unsigned get_Call_memory_properties(ir_node *call)
513 ir_type *call_tp = get_Call_type(call);
514 unsigned prop = get_method_additional_properties(call_tp);
516 /* check first the call type */
517 if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
518 /* try the called entity */
519 ir_node *ptr = get_Call_ptr(call);
521 if (is_SymConst_addr_ent(ptr)) {
522 ir_entity *ent = get_SymConst_entity(ptr);
524 prop = get_entity_additional_properties(ent);
527 return prop & (mtp_property_const|mtp_property_pure);
531 * Returns an entity if the address ptr points to a constant one.
533 * @param ptr the address
535 * @return an entity or NULL
537 static ir_entity *find_constant_entity(ir_node *ptr)
540 if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
541 return get_SymConst_entity(ptr);
542 } else if (is_Sel(ptr)) {
543 ir_entity *ent = get_Sel_entity(ptr);
544 ir_type *tp = get_entity_owner(ent);
546 /* Do not fiddle with polymorphism. */
547 if (is_Class_type(get_entity_owner(ent)) &&
548 ((get_entity_n_overwrites(ent) != 0) ||
549 (get_entity_n_overwrittenby(ent) != 0) ) )
552 if (is_Array_type(tp)) {
556 for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
558 ir_tarval *tlower, *tupper;
559 ir_node *index = get_Sel_index(ptr, i);
560 ir_tarval *tv = computed_value(index);
562 /* check if the index is constant */
563 if (tv == tarval_bad)
566 bound = get_array_lower_bound(tp, i);
567 tlower = computed_value(bound);
568 bound = get_array_upper_bound(tp, i);
569 tupper = computed_value(bound);
571 if (tlower == tarval_bad || tupper == tarval_bad)
574 if (tarval_cmp(tv, tlower) == ir_relation_less)
576 if (tarval_cmp(tupper, tv) == ir_relation_less)
579 /* ok, bounds check finished */
583 if (get_entity_linkage(ent) == IR_LINKAGE_CONSTANT)
587 ptr = get_Sel_ptr(ptr);
588 } else if (is_Add(ptr)) {
589 ir_node *l = get_Add_left(ptr);
590 ir_node *r = get_Add_right(ptr);
592 if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
594 else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l))
599 /* for now, we support only one addition, reassoc should fold all others */
600 if (! is_SymConst(ptr) && !is_Sel(ptr))
602 } else if (is_Sub(ptr)) {
603 ir_node *l = get_Sub_left(ptr);
604 ir_node *r = get_Sub_right(ptr);
606 if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
610 /* for now, we support only one subtraction, reassoc should fold all others */
611 if (! is_SymConst(ptr) && !is_Sel(ptr))
619 * Return the Selection index of a Sel node from dimension n
621 static long get_Sel_array_index_long(ir_node *n, int dim)
623 ir_node *index = get_Sel_index(n, dim);
624 return get_tarval_long(get_Const_tarval(index));
627 typedef struct path_entry {
629 struct path_entry *next;
633 static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next)
635 path_entry entry, *p;
636 ir_entity *ent, *field;
637 ir_initializer_t *initializer;
643 if (is_SymConst(ptr)) {
645 ent = get_SymConst_entity(ptr);
646 initializer = get_entity_initializer(ent);
647 for (p = next; p != NULL;) {
648 if (initializer->kind != IR_INITIALIZER_COMPOUND)
650 n = get_initializer_compound_n_entries(initializer);
651 tp = get_entity_type(ent);
653 if (is_Array_type(tp)) {
654 ent = get_array_element_entity(tp);
659 initializer = get_initializer_compound_value(initializer, 0);
665 initializer = get_initializer_compound_value(initializer, p->index);
670 tp = get_entity_type(ent);
671 while (is_Array_type(tp)) {
672 ent = get_array_element_entity(tp);
673 tp = get_entity_type(ent);
675 n = get_initializer_compound_n_entries(initializer);
678 initializer = get_initializer_compound_value(initializer, 0);
681 switch (initializer->kind) {
682 case IR_INITIALIZER_CONST:
683 return get_initializer_const_value(initializer);
684 case IR_INITIALIZER_TARVAL:
685 case IR_INITIALIZER_NULL:
689 } else if (is_Sel(ptr)) {
690 entry.ent = field = get_Sel_entity(ptr);
691 tp = get_entity_owner(field);
692 if (is_Array_type(tp)) {
693 assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
694 entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
696 size_t i, n_members = get_compound_n_members(tp);
697 for (i = 0; i < n_members; ++i) {
698 if (get_compound_member(tp, i) == field)
701 if (i >= n_members) {
702 /* not found: should NOT happen */
707 return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry);
708 } else if (is_Add(ptr)) {
713 ir_node *l = get_Add_left(ptr);
714 ir_node *r = get_Add_right(ptr);
717 tv = get_Const_tarval(r);
720 tv = get_Const_tarval(l);
724 mode = get_tarval_mode(tv);
726 /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
728 field = get_Sel_entity(ptr);
730 field = get_SymConst_entity(ptr);
733 /* count needed entries */
735 for (ent = field;;) {
736 tp = get_entity_type(ent);
737 if (! is_Array_type(tp))
739 ent = get_array_element_entity(tp);
742 /* should be at least ONE entry */
746 /* allocate the right number of entries */
747 NEW_ARR_A(path_entry, p, pos);
751 for (ent = field;;) {
753 ir_tarval *sz, *tv_index, *tlower, *tupper;
757 tp = get_entity_type(ent);
758 if (! is_Array_type(tp))
760 ent = get_array_element_entity(tp);
762 p[pos].next = &p[pos + 1];
764 size = get_type_size_bytes(get_entity_type(ent));
765 sz = new_tarval_from_long(size, mode);
767 tv_index = tarval_div(tv, sz);
768 tv = tarval_mod(tv, sz);
770 if (tv_index == tarval_bad || tv == tarval_bad)
773 assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
774 bound = get_array_lower_bound(tp, 0);
775 tlower = computed_value(bound);
776 bound = get_array_upper_bound(tp, 0);
777 tupper = computed_value(bound);
779 if (tlower == tarval_bad || tupper == tarval_bad)
782 if (tarval_cmp(tv_index, tlower) == ir_relation_less)
784 if (tarval_cmp(tupper, tv_index) == ir_relation_less)
787 /* ok, bounds check finished */
788 index = get_tarval_long(tv_index);
789 p[pos].index = index;
792 if (! tarval_is_null(tv)) {
793 /* hmm, wrong access */
796 p[pos - 1].next = next;
797 return rec_find_compound_ent_value(ptr, p);
798 } else if (is_Sub(ptr)) {
799 ir_node *l = get_Sub_left(ptr);
800 ir_node *r = get_Sub_right(ptr);
803 tv = get_Const_tarval(r);
810 static ir_node *find_compound_ent_value(ir_node *ptr)
812 return rec_find_compound_ent_value(ptr, NULL);
816 * Mark a Load memop to be replace by a definition
818 * @param op the Load memop
820 static void mark_replace_load(memop_t *op, ir_node *def)
823 op->flags |= FLAG_KILLED_NODE;
828 * Mark a Store memop to be removed.
830 * @param op the Store memop
832 static void mark_remove_store(memop_t *op)
834 op->flags |= FLAG_KILLED_NODE;
839 * Update a memop for a Load.
843 static void update_Load_memop(memop_t *m)
845 ir_node *load = m->node;
849 if (get_Load_volatility(load) == volatility_is_volatile)
850 m->flags |= FLAG_IGNORE;
852 ptr = get_Load_ptr(load);
854 m->value.address = ptr;
856 for (unsigned i = get_irn_n_outs(load); i-- > 0; ) {
857 ir_node *proj = get_irn_out(load, i);
860 /* beware of keep edges */
864 pn = get_Proj_proj(proj);
868 m->value.value = proj;
869 m->value.mode = get_irn_mode(proj);
871 case pn_Load_X_except:
872 m->flags |= FLAG_EXCEPTION;
877 case pn_Load_X_regular:
880 panic("Unsupported Proj from Load %+F", proj);
884 /* check if we can determine the entity that will be loaded */
885 ent = find_constant_entity(ptr);
887 if (ent != NULL && get_entity_visibility(ent) != ir_visibility_external) {
888 /* a static allocation that is not external: there should be NO exception
889 * when loading even if we cannot replace the load itself. */
890 ir_node *value = NULL;
892 /* no exception, clear the m fields as it might be checked later again */
893 if (m->projs[pn_Load_X_except]) {
894 ir_graph *irg = get_irn_irg(ptr);
895 exchange(m->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
896 m->projs[pn_Load_X_except] = NULL;
897 m->flags &= ~FLAG_EXCEPTION;
900 if (m->projs[pn_Load_X_regular]) {
901 exchange(m->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
902 m->projs[pn_Load_X_regular] = NULL;
906 if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT) {
907 if (ent->initializer) {
908 /* new style initializer */
909 value = find_compound_ent_value(ptr);
912 value = can_replace_load_by_const(load, value);
916 /* we completely replace the load by this value */
917 DB((dbg, LEVEL_1, "Replacing Load %+F by constant %+F\n", m->node, value));
918 mark_replace_load(m, value);
923 if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) {
924 /* only create an address if this node is NOT killed immediately or ignored */
925 m->value.id = register_address(ptr);
928 /* no user, KILL it */
929 mark_replace_load(m, NULL);
934 * Update a memop for a Store.
938 static void update_Store_memop(memop_t *m)
940 ir_node *store = m->node;
941 ir_node *adr = get_Store_ptr(store);
943 if (get_Store_volatility(store) == volatility_is_volatile) {
944 m->flags |= FLAG_IGNORE;
946 /* only create an address if this node is NOT ignored */
947 m->value.id = register_address(adr);
951 m->value.address = adr;
953 for (unsigned i = get_irn_n_outs(store); i-- > 0; ) {
954 ir_node *proj = get_irn_out(store, i);
957 /* beware of keep edges */
961 pn = get_Proj_proj(proj);
964 case pn_Store_X_except:
965 m->flags |= FLAG_EXCEPTION;
970 case pn_Store_X_regular:
973 panic("Unsupported Proj from Store %+F", proj);
976 m->value.value = get_Store_value(store);
977 m->value.mode = get_irn_mode(m->value.value);
981 * Update a memop for a Call.
985 static void update_Call_memop(memop_t *m)
987 ir_node *call = m->node;
988 unsigned prop = get_Call_memory_properties(call);
990 if (prop & mtp_property_const) {
991 /* A constant call did NOT use memory at all, we
992 can kick it from the list. */
993 } else if (prop & mtp_property_pure) {
994 /* pure calls READ memory */
997 m->flags = FLAG_KILL_ALL;
999 for (unsigned i = get_irn_n_outs(call); i-- > 0; ) {
1000 ir_node *proj = get_irn_out(call, i);
1002 /* beware of keep edges */
1006 switch (get_Proj_proj(proj)) {
1007 case pn_Call_X_except:
1008 m->flags |= FLAG_EXCEPTION;
1018 * Update a memop for a Div/Mod.
1020 * @param m the memop
1022 static void update_Div_memop(memop_t *m)
1024 ir_node *div = m->node;
1026 for (unsigned i = get_irn_n_outs(div); i-- > 0; ) {
1027 ir_node *proj = get_irn_out(div, i);
1029 /* beware of keep edges */
1033 switch (get_Proj_proj(proj)) {
1034 case pn_Div_X_except:
1035 m->flags |= FLAG_EXCEPTION;
1044 static void update_Mod_memop(memop_t *m)
1046 ir_node *div = m->node;
1048 for (unsigned i = get_irn_n_outs(div); i-- > 0; ) {
1049 ir_node *proj = get_irn_out(div, i);
1051 /* beware of keep edges */
1055 switch (get_Proj_proj(proj)) {
1056 case pn_Mod_X_except:
1057 m->flags |= FLAG_EXCEPTION;
1067 * Update a memop for a Phi.
1069 * @param m the memop
1071 static void update_Phi_memop(memop_t *m)
1073 /* the Phi is its own mem */
1078 * Memory walker: collect all memory ops and build topological lists.
1080 static void collect_memops(ir_node *irn, void *ctx)
1088 /* we can safely ignore ProjM's except the initial memory */
1089 ir_graph *irg = get_irn_irg(irn);
1090 if (irn != get_irg_initial_mem(irg))
1094 op = alloc_memop(irn);
1095 block = get_nodes_block(irn);
1096 entry = get_block_entry(block);
1099 update_Phi_memop(op);
1100 /* Phis must be always placed first */
1101 op->next = entry->memop_forward;
1102 entry->memop_forward = op;
1103 if (entry->memop_backward == NULL)
1104 entry->memop_backward = op;
1106 switch (get_irn_opcode(irn)) {
1108 update_Load_memop(op);
1111 update_Store_memop(op);
1114 update_Call_memop(op);
1121 /* initial memory */
1126 /* we can those to find the memory edge */
1129 update_Div_memop(op);
1132 update_Mod_memop(op);
1136 /* TODO: handle some builtins */
1138 /* unsupported operation */
1139 op->flags = FLAG_KILL_ALL;
1143 /* all other should be placed last */
1144 if (entry->memop_backward == NULL) {
1145 entry->memop_forward = entry->memop_backward = op;
1147 entry->memop_backward->next = op;
1148 entry->memop_backward = op;
1154 * Find an address in the current set.
1156 * @param value the value to be searched for
1158 * @return a memop for the value or NULL if the value does
1159 * not exists in the set or cannot be converted into
1160 * the requested mode
1162 static memop_t *find_address(const value_t *value)
1164 if (rbitset_is_set(env.curr_set, value->id)) {
1165 memop_t *res = env.curr_id_2_memop[value->id];
1167 if (res->value.mode == value->mode)
1169 /* allow hidden casts */
1170 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
1171 get_mode_arithmetic(value->mode) == irma_twos_complement &&
1172 get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
1179 * Find an address in the avail_out set.
1181 * @param bl the block
1183 static memop_t *find_address_avail(const block_t *bl, unsigned id, const ir_mode *mode)
1185 if (rbitset_is_set(bl->avail_out, id)) {
1186 memop_t *res = bl->id_2_memop_avail[id];
1188 if (res->value.mode == mode)
1190 /* allow hidden casts */
1191 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
1192 get_mode_arithmetic(mode) == irma_twos_complement &&
1193 get_mode_size_bits(res->value.mode) == get_mode_size_bits(mode))
1200 * Kill all addresses from the current set.
1202 static void kill_all(void)
1204 rbitset_clear_all(env.curr_set, env.rbs_size);
1207 rbitset_set(env.curr_set, env.rbs_size - 1);
1211 * Kill memops that are not alias free due to a Store value from the current set.
1213 * @param value the Store value
1215 static void kill_memops(const value_t *value)
1217 size_t end = env.rbs_size - 1;
1220 for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
1221 memop_t *op = env.curr_id_2_memop[pos];
1223 if (ir_no_alias != get_alias_relation(value->address, value->mode,
1224 op->value.address, op->value.mode)) {
1225 rbitset_clear(env.curr_set, pos);
1226 env.curr_id_2_memop[pos] = NULL;
1227 DB((dbg, LEVEL_2, "KILLING %+F because of possible alias address %+F\n", op->node, value->address));
1233 * Add the value of a memop to the current set.
1235 * @param op the memory op
1237 static void add_memop(memop_t *op)
1239 rbitset_set(env.curr_set, op->value.id);
1240 env.curr_id_2_memop[op->value.id] = op;
1244 * Add the value of a memop to the avail_out set.
1246 * @param bl the block
1247 * @param op the memory op
1249 static void add_memop_avail(block_t *bl, memop_t *op)
1251 rbitset_set(bl->avail_out, op->value.id);
1252 bl->id_2_memop_avail[op->value.id] = op;
1256 * Check, if we can convert a value of one mode to another mode
1257 * without changing the representation of bits.
1259 * @param from the original mode
1260 * @param to the destination mode
1262 static int can_convert_to(const ir_mode *from, const ir_mode *to)
1264 if (get_mode_arithmetic(from) == irma_twos_complement &&
1265 get_mode_arithmetic(to) == irma_twos_complement &&
1266 get_mode_size_bits(from) == get_mode_size_bits(to))
1272 * Add a Conv to the requested mode if needed.
1274 * @param irn the IR-node to convert
1275 * @param mode the destination mode
1277 * @return the possible converted node or NULL
1278 * if the conversion is not possible
1280 static ir_node *conv_to(ir_node *irn, ir_mode *mode)
1282 ir_mode *other = get_irn_mode(irn);
1283 if (other != mode) {
1284 /* different modes: check if conversion is possible without changing the bits */
1285 if (can_convert_to(other, mode)) {
1286 ir_node *block = get_nodes_block(irn);
1287 return new_r_Conv(block, irn, mode);
1289 /* otherwise not possible ... yet */
1296 * Update the address of an value if this address was a load result
1297 * and the load is killed now.
1299 * @param value the value whose address is updated
1301 static void update_address(value_t *value)
1303 if (is_Proj(value->address)) {
1304 ir_node *load = get_Proj_pred(value->address);
1306 if (is_Load(load)) {
1307 const memop_t *op = get_irn_memop(load);
1309 if (op->flags & FLAG_KILLED_NODE)
1310 value->address = op->replace;
1316 * Do forward dataflow analysis on the given block and calculate the
1317 * GEN and KILL in the current (avail) set.
1319 * @param bl the block
1321 static void calc_gen_kill_avail(block_t *bl)
1326 for (op = bl->memop_forward; op != NULL; op = op->next) {
1327 switch (get_irn_opcode(op->node)) {
1335 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
1336 /* do we have this already? */
1339 update_address(&op->value);
1340 other = find_address(&op->value);
1341 if (other != NULL && other != op) {
1342 def = conv_to(other->value.value, op->value.mode);
1344 #ifdef DEBUG_libfirm
1345 if (is_Store(other->node)) {
1347 DB((dbg, LEVEL_1, "RAW %+F <- %+F(%+F)\n", op->node, def, other->node));
1350 DB((dbg, LEVEL_1, "RAR %+F <- %+F(%+F)\n", op->node, def, other->node));
1353 mark_replace_load(op, def);
1354 /* do NOT change the memop table */
1358 /* add this value */
1363 if (! (op->flags & FLAG_KILLED_NODE)) {
1364 /* do we have this store already */
1367 update_address(&op->value);
1368 other = find_address(&op->value);
1369 if (other != NULL) {
1370 if (is_Store(other->node)) {
1371 if (op != other && !(other->flags & FLAG_IGNORE) &&
1372 get_nodes_block(other->node) == get_nodes_block(op->node)) {
1374 * A WAW in the same block we can kick the first store.
1375 * This is a shortcut: we know that the second Store will be anticipated
1378 DB((dbg, LEVEL_1, "WAW %+F <- %+F\n", other->node, op->node));
1379 mark_remove_store(other);
1380 /* FIXME: a Load might be get freed due to this killed store */
1382 } else if (other->value.value == op->value.value && !(op->flags & FLAG_IGNORE)) {
1384 DB((dbg, LEVEL_1, "WAR %+F <- %+F\n", op->node, other->node));
1385 mark_remove_store(op);
1386 /* do NOT change the memop table */
1390 /* KILL all possible aliases */
1391 kill_memops(&op->value);
1392 /* add this value */
1397 if (op->flags & FLAG_KILL_ALL)
1404 * Do forward dataflow analysis on a given block to calculate the avail_out set
1405 * for this block only.
1407 * @param block the block
1409 static void forward_avail(block_t *bl)
1411 /* fill the data from the current block */
1412 env.curr_id_2_memop = bl->id_2_memop_avail;
1413 env.curr_set = bl->avail_out;
1415 calc_gen_kill_avail(bl);
1416 dump_curr(bl, "Avail_out");
1420 * Do backward dataflow analysis on a given block to calculate the antic set
1421 * of Loaded addresses.
1423 * @param bl the block
1425 * @return non-zero if the set has changed since last iteration
1427 static int backward_antic(block_t *bl)
1430 ir_node *block = bl->block;
1431 int n = get_Block_n_cfg_outs(block);
1434 ir_node *succ = get_Block_cfg_out(block, 0);
1435 block_t *succ_bl = get_block_entry(succ);
1436 int pred_pos = get_Block_cfgpred_pos(succ, block);
1437 size_t end = env.rbs_size - 1;
1442 if (bl->trans_results == NULL) {
1443 /* allocate the translate cache */
1444 bl->trans_results = OALLOCNZ(&env.obst, memop_t*, env.curr_adr_id);
1447 /* check for partly redundant values */
1448 for (pos = rbitset_next(succ_bl->anticL_in, 0, 1);
1450 pos = rbitset_next(succ_bl->anticL_in, pos + 1, 1)) {
1452 * do Phi-translation here: Note that at this point the nodes are
1453 * not changed, so we can safely cache the results.
1454 * However: Loads of Load results ARE bad, because we have no way
1455 to translate them yet ...
1457 memop_t *op = bl->trans_results[pos];
1459 /* not yet translated */
1460 ir_node *adr, *trans_adr;
1462 op = succ_bl->id_2_memop_antic[pos];
1463 adr = op->value.address;
1465 trans_adr = phi_translate(adr, succ, pred_pos);
1466 if (trans_adr != adr) {
1467 /* create a new entry for the translated one */
1470 new_op = alloc_memop(NULL);
1471 new_op->value.address = trans_adr;
1472 new_op->value.id = register_address(trans_adr);
1473 new_op->value.mode = op->value.mode;
1474 new_op->node = op->node; /* we need the node to decide if Load/Store */
1475 new_op->flags = op->flags;
1477 bl->trans_results[pos] = new_op;
1481 env.curr_id_2_memop[op->value.id] = op;
1482 rbitset_set(env.curr_set, op->value.id);
1485 ir_node *succ = get_Block_cfg_out(block, 0);
1486 block_t *succ_bl = get_block_entry(succ);
1489 rbitset_copy(env.curr_set, succ_bl->anticL_in, env.rbs_size);
1490 memcpy(env.curr_id_2_memop, succ_bl->id_2_memop_antic, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
1492 /* Hmm: probably we want kill merges of Loads ans Stores here */
1493 for (i = n - 1; i > 0; --i) {
1494 ir_node *succ = get_Block_cfg_out(bl->block, i);
1495 block_t *succ_bl = get_block_entry(succ);
1497 rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size);
1500 /* block ends with a noreturn call */
1504 dump_curr(bl, "AnticL_out");
1506 for (op = bl->memop_backward; op != NULL; op = op->prev) {
1507 switch (get_irn_opcode(op->node)) {
1515 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
1521 if (! (op->flags & FLAG_KILLED_NODE)) {
1522 /* a Store: check which memops must be killed */
1523 kill_memops(&op->value);
1527 if (op->flags & FLAG_KILL_ALL)
1532 memcpy(bl->id_2_memop_antic, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
1533 if (! rbitsets_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
1535 rbitset_copy(bl->anticL_in, env.curr_set, env.rbs_size);
1536 dump_curr(bl, "AnticL_in*");
1539 dump_curr(bl, "AnticL_in");
1544 * Replace a Load memop by a already known value.
1546 * @param op the Load memop
1548 static void replace_load(memop_t *op)
1550 ir_node *load = op->node;
1551 ir_node *def = skip_Id(op->replace);
1556 DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, is_Proj(def) ? get_Proj_pred(def) : def));
1558 if (op->flags & FLAG_EXCEPTION) {
1559 /* bad: this node is unused and executed for exception only */
1560 DB((dbg, LEVEL_1, "Unused %+F executed for exception only ...\n", load));
1563 DB((dbg, LEVEL_1, "Killing unused %+F\n", load));
1566 if (op->mem != NULL) {
1567 /* in rare cases a Load might have NO memory */
1568 exchange(op->mem, get_Load_mem(load));
1570 proj = op->projs[pn_Load_res];
1572 mode = get_irn_mode(proj);
1573 if (get_irn_mode(def) != mode) {
1575 dbg_info *db = get_irn_dbg_info(load);
1576 ir_node *block = get_nodes_block(proj);
1577 def = new_rd_Conv(db, block, def, mode);
1579 exchange(proj, def);
1581 proj = op->projs[pn_Load_X_except];
1583 ir_graph *irg = get_irn_irg(load);
1584 exchange(proj, new_r_Bad(irg, mode_X));
1586 proj = op->projs[pn_Load_X_regular];
1588 exchange(proj, new_r_Jmp(get_nodes_block(load)));
1593 * Remove a Store memop.
1595 * @param op the Store memop
1597 static void remove_store(memop_t *op)
1599 ir_node *store = op->node;
1602 DB((dbg, LEVEL_1, "Removing %+F\n", store));
1604 if (op->mem != NULL) {
1605 /* in rare cases a Store might have no memory */
1606 exchange(op->mem, get_Store_mem(store));
1608 proj = op->projs[pn_Store_X_except];
1610 ir_graph *irg = get_irn_irg(store);
1611 exchange(proj, new_r_Bad(irg, mode_X));
1613 proj = op->projs[pn_Store_X_regular];
1615 exchange(proj, new_r_Jmp(get_nodes_block(store)));
1621 * Do all necessary replacements for a given block.
1623 * @param bl the block
1625 static void do_replacements(block_t *bl)
1629 for (op = bl->memop_forward; op != NULL; op = op->next) {
1630 if (op->flags & FLAG_KILLED_NODE) {
1631 switch (get_irn_opcode(op->node)) {
1644 * Calculate the Avail_out sets for all basic blocks.
1646 static void calcAvail(void)
1648 memop_t **tmp_memop = env.curr_id_2_memop;
1649 unsigned *tmp_set = env.curr_set;
1652 /* calculate avail_out */
1653 DB((dbg, LEVEL_2, "Calculate Avail_out\n"));
1655 /* iterate over all blocks in in any order, skip the start block */
1656 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1660 /* restore the current sets */
1661 env.curr_id_2_memop = tmp_memop;
1662 env.curr_set = tmp_set;
1666 * Calculate the Antic_in sets for all basic blocks.
1668 static void calcAntic(void)
1672 /* calculate antic_out */
1673 DB((dbg, LEVEL_2, "Calculate Antic_in\n"));
1678 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1682 /* over all blocks in reverse post order */
1683 for (bl = env.backward->backward_next; bl != NULL; bl = bl->backward_next) {
1684 need_iter |= backward_antic(bl);
1687 } while (need_iter);
1688 DB((dbg, LEVEL_2, "Get anticipated Load set after %d iterations\n", i));
1692 * Return the node representing the last memory in a block.
1694 * @param bl the block
1696 static ir_node *find_last_memory(block_t *bl)
1699 if (bl->memop_backward != NULL) {
1700 return bl->memop_backward->mem;
1702 /* if there is NO memory in this block, go to the dominator */
1703 bl = get_block_entry(get_Block_idom(bl->block));
1708 * Reroute all memory users of old memory
1709 * to a new memory IR-node.
1711 * @param omem the old memory IR-node
1712 * @param nmem the new memory IR-node
1714 static void reroute_all_mem_users(ir_node *omem, ir_node *nmem)
1716 for (unsigned i = get_irn_n_outs(omem); i-- > 0; ) {
1718 ir_node *user = get_irn_out_ex(omem, i, &n_pos);
1720 set_irn_n(user, n_pos, nmem);
1723 /* all edges previously point to omem now point to nmem */
1724 nmem->o.out = omem->o.out;
1728 * Reroute memory users of old memory that are dominated by a given block
1729 * to a new memory IR-node.
1731 * @param omem the old memory IR-node
1732 * @param nmem the new memory IR-node
1733 * @param pass_bl the block the memory must pass
1735 static void reroute_mem_through(ir_node *omem, ir_node *nmem, ir_node *pass_bl)
1737 unsigned n = get_irn_n_outs(omem);
1738 ir_def_use_edges *new_out = OALLOCF(&env.obst, ir_def_use_edges, edges, n);
1741 for (unsigned i = 0; i < n; ++i) {
1743 ir_node *user = get_irn_out_ex(omem, i, &n_pos);
1744 ir_node *use_bl = get_nodes_block(user);
1748 use_bl = get_Block_cfgpred_block(use_bl, n_pos);
1750 if (block_dominates(pass_bl, use_bl)) {
1751 /* found an user that is dominated */
1752 new_out->edges[j].pos = n_pos;
1753 new_out->edges[j].use = user;
1756 set_irn_n(user, n_pos, nmem);
1759 new_out->n_edges = j;
1761 /* Modify the out structure: we create a new out edge array on our
1762 temporary obstack here. This should be no problem, as we invalidate the
1763 edges at the end either. */
1764 /* first entry is used for the length */
1765 nmem->o.out = new_out;
1769 * insert Loads, making partly redundant Loads fully redundant
1771 static int insert_Load(block_t *bl)
1773 ir_node *block = bl->block;
1774 int i, n = get_Block_n_cfgpreds(block);
1775 size_t end = env.rbs_size - 1;
1777 DB((dbg, LEVEL_3, "processing %+F\n", block));
1780 /* might still happen for an unreachable block (end for instance) */
1788 NEW_ARR_A(ir_node *, ins, n);
1790 rbitset_set_all(env.curr_set, env.rbs_size);
1792 /* More than one predecessors, calculate the join for all avail_outs ignoring unevaluated
1793 Blocks. These put in Top anyway. */
1794 for (i = n - 1; i >= 0; --i) {
1795 ir_node *pred = skip_Proj(get_Block_cfgpred(block, i));
1796 ir_node *blk = get_nodes_block(pred);
1799 pred_bl = get_block_entry(blk);
1800 rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
1802 if (is_Load(pred) || is_Store(pred)) {
1803 /* We reached this block by an exception from a Load or Store:
1804 * the memop creating the exception was NOT completed than, kill it
1806 memop_t *exc_op = get_irn_memop(pred);
1807 rbitset_clear(env.curr_set, exc_op->value.id);
1812 * Ensure that all values are in the map: build Phi's if necessary:
1813 * Note: the last bit is the sentinel and ALWAYS set, so end with -2.
1815 for (pos = 0; pos < env.rbs_size - 1; ++pos) {
1816 if (! rbitset_is_set(env.curr_set, pos))
1817 env.curr_id_2_memop[pos] = NULL;
1820 memop_t *first = NULL;
1821 ir_mode *mode = NULL;
1823 for (i = 0; i < n; ++i) {
1824 ir_node *pred = get_Block_cfgpred_block(bl->block, i);
1825 block_t *pred_bl = get_block_entry(pred);
1827 memop_t *mop = pred_bl->id_2_memop_avail[pos];
1828 if (first == NULL) {
1830 ins[0] = first->value.value;
1831 mode = get_irn_mode(ins[0]);
1833 /* no Phi needed so far */
1834 env.curr_id_2_memop[pos] = first;
1836 ins[i] = conv_to(mop->value.value, mode);
1837 if (ins[i] != ins[0]) {
1838 if (ins[i] == NULL) {
1839 /* conversion failed */
1840 env.curr_id_2_memop[pos] = NULL;
1841 rbitset_clear(env.curr_set, pos);
1850 ir_node *phi = new_r_Phi(bl->block, n, ins, mode);
1851 memop_t *phiop = alloc_memop(phi);
1853 phiop->value = first->value;
1854 phiop->value.value = phi;
1856 /* no need to link it in, as it is a DATA phi */
1858 env.curr_id_2_memop[pos] = phiop;
1860 DB((dbg, LEVEL_3, "Created new %+F on merging value for address %+F\n", phi, first->value.address));
1865 /* only one predecessor, simply copy the map */
1866 ir_node *pred = get_Block_cfgpred_block(bl->block, 0);
1867 block_t *pred_bl = get_block_entry(pred);
1869 rbitset_copy(env.curr_set, pred_bl->avail_out, env.rbs_size);
1871 memcpy(env.curr_id_2_memop, pred_bl->id_2_memop_avail, env.rbs_size * sizeof(bl->id_2_memop_avail[0]));
1877 /* check for partly redundant values */
1878 for (pos = rbitset_next(bl->anticL_in, 0, 1);
1880 pos = rbitset_next(bl->anticL_in, pos + 1, 1)) {
1881 memop_t *op = bl->id_2_memop_antic[pos];
1882 int have_some, all_same;
1885 if (rbitset_is_set(env.curr_set, pos)) {
1890 assert(is_Load(op->node));
1892 DB((dbg, LEVEL_3, "anticipated %+F\n", op->node));
1897 for (i = n - 1; i >= 0; --i) {
1898 ir_node *pred = get_Block_cfgpred_block(block, i);
1899 block_t *pred_bl = get_block_entry(pred);
1900 ir_mode *mode = op->value.mode;
1904 adr = phi_translate(op->value.address, block, i);
1905 DB((dbg, LEVEL_3, ".. using address %+F in pred %d\n", adr, i));
1906 e = find_address_avail(pred_bl, register_address(adr), mode);
1908 ir_node *ef_block = get_nodes_block(adr);
1909 if (! block_dominates(ef_block, pred)) {
1910 /* cannot place a copy here */
1912 DB((dbg, LEVEL_3, "%+F cannot be moved into predecessor %+F\n", op->node, pred));
1915 DB((dbg, LEVEL_3, "%+F is not available in predecessor %+F\n", op->node, pred));
1916 pred_bl->avail = NULL;
1919 if (e->value.mode != mode && !can_convert_to(e->value.mode, mode)) {
1920 /* cannot create a Phi due to different modes */
1926 DB((dbg, LEVEL_3, "%+F is available for %+F in predecessor %+F\n", e->node, op->node, pred));
1929 else if (first != e->node)
1933 if (have_some && !all_same) {
1934 ir_mode *mode = op->value.mode;
1938 NEW_ARR_A(ir_node *, in, n);
1940 for (i = n - 1; i >= 0; --i) {
1941 ir_node *pred = get_Block_cfgpred_block(block, i);
1942 block_t *pred_bl = get_block_entry(pred);
1944 if (pred_bl->avail == NULL) {
1945 /* create a new Load here and make to make it fully redundant */
1946 dbg_info *db = get_irn_dbg_info(op->node);
1947 ir_node *last_mem = find_last_memory(pred_bl);
1948 ir_node *load, *def, *adr;
1951 assert(last_mem != NULL);
1952 adr = phi_translate(op->value.address, block, i);
1953 load = new_rd_Load(db, pred, last_mem, adr, mode, cons_none);
1954 def = new_r_Proj(load, mode, pn_Load_res);
1955 DB((dbg, LEVEL_1, "Created new %+F in %+F for party redundant %+F\n", load, pred, op->node));
1957 new_op = alloc_memop(load);
1958 new_op->mem = new_r_Proj(load, mode_M, pn_Load_M);
1959 new_op->value.address = adr;
1960 new_op->value.id = op->value.id;
1961 new_op->value.mode = mode;
1962 new_op->value.value = def;
1964 new_op->projs[pn_Load_M] = new_op->mem;
1965 new_op->projs[pn_Load_res] = def;
1967 new_op->prev = pred_bl->memop_backward;
1968 if (pred_bl->memop_backward != NULL)
1969 pred_bl->memop_backward->next = new_op;
1971 pred_bl->memop_backward = new_op;
1973 if (pred_bl->memop_forward == NULL)
1974 pred_bl->memop_forward = new_op;
1976 if (get_nodes_block(last_mem) == pred) {
1977 /* We have add a new last memory op in pred block.
1978 If pred had already a last mem, reroute all memory
1980 reroute_all_mem_users(last_mem, new_op->mem);
1982 /* reroute only those memory going through the pre block */
1983 reroute_mem_through(last_mem, new_op->mem, pred);
1986 /* we added this load at the end, so it will be avail anyway */
1987 add_memop_avail(pred_bl, new_op);
1988 pred_bl->avail = new_op;
1990 in[i] = conv_to(pred_bl->avail->value.value, mode);
1992 phi = new_r_Phi(block, n, in, mode);
1993 DB((dbg, LEVEL_1, "Created new %+F in %+F for now redundant %+F\n", phi, block, op->node));
1995 phi_op = clone_memop_phi(op, phi);
2001 /* recalculate avail by gen and kill */
2002 calc_gen_kill_avail(bl);
2004 /* always update the map after gen/kill, as values might have been changed due to RAR/WAR/WAW */
2005 memcpy(bl->id_2_memop_avail, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
2007 if (!rbitsets_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
2008 /* the avail set has changed */
2009 rbitset_copy(bl->avail_out, env.curr_set, env.rbs_size);
2010 dump_curr(bl, "Avail_out*");
2013 dump_curr(bl, "Avail_out");
2018 * Insert Loads upwards.
2020 static void insert_Loads_upwards(void)
2025 /* recalculate antic_out and insert Loads */
2026 DB((dbg, LEVEL_2, "Inserting Loads\n"));
2030 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
2034 /* over all blocks in reverse post order, skip the start block */
2035 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
2036 need_iter |= insert_Load(bl);
2039 } while (need_iter);
2041 DB((dbg, LEVEL_2, "Finished Load inserting after %d iterations\n", i));
2044 void opt_ldst(ir_graph *irg)
2048 FIRM_DBG_REGISTER(dbg, "firm.opt.ldst");
2050 DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
2052 assure_irg_properties(irg,
2053 IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES /* we need landing pads */
2054 | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE
2055 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
2056 | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
2057 | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
2059 if (get_opt_alias_analysis()) {
2060 assure_irp_globals_entity_usage_computed();
2063 obstack_init(&env.obst);
2064 ir_nodehashmap_init(&env.adr_map);
2067 env.backward = NULL;
2068 env.curr_adr_id = 0;
2070 env.max_cfg_preds = 0;
2072 env.end_bl = get_irg_end_block(irg);
2073 #ifdef DEBUG_libfirm
2074 env.id_2_address = NEW_ARR_F(ir_node *, 0);
2077 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
2079 /* first step: allocate block entries. Note that some blocks might be
2080 unreachable here. Using the normal walk ensures that ALL blocks are initialized. */
2081 irg_walk_graph(irg, prepare_blocks, link_phis, NULL);
2083 /* produce an inverse post-order list for the CFG: this links only reachable
2085 ir_node *const start_block = get_irg_start_block(irg);
2086 irg_out_block_walk(start_block, NULL, inverse_post_order, NULL);
2088 if (! get_Block_mark(env.end_bl)) {
2090 * The end block is NOT reachable due to endless loops
2091 * or no_return calls.
2092 * Place the end block last.
2093 * env.backward points to the last block in the list for this purpose.
2095 env.backward->forward_next = get_block_entry(env.end_bl);
2097 set_Block_mark(env.end_bl, 1);
2100 /* second step: find and sort all memory ops */
2101 walk_memory_irg(irg, collect_memops, NULL, NULL);
2103 #ifdef DEBUG_libfirm
2104 /* check that the backward map is correct */
2105 assert((unsigned)ARR_LEN(env.id_2_address) == env.curr_adr_id);
2108 if (env.n_mem_ops == 0) {
2113 /* create the backward links. */
2114 env.backward = NULL;
2115 irg_block_walk_graph(irg, NULL, collect_backward, NULL);
2117 /* link the end block in */
2118 bl = get_block_entry(env.end_bl);
2119 bl->backward_next = env.backward;
2122 /* check that we really start with the start / end block */
2123 assert(env.forward->block == start_block);
2124 assert(env.backward->block == env.end_bl);
2126 /* create address sets: for now, only the existing addresses are allowed plus one
2127 needed for the sentinel */
2128 env.rbs_size = env.curr_adr_id + 1;
2130 /* create the current set */
2131 env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2132 rbitset_set(env.curr_set, env.rbs_size - 1);
2133 env.curr_id_2_memop = NEW_ARR_DZ(memop_t*, &env.obst, env.rbs_size);
2135 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2136 /* set sentinel bits */
2137 bl->avail_out = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2138 rbitset_set(bl->avail_out, env.rbs_size - 1);
2140 bl->id_2_memop_avail = NEW_ARR_DZ(memop_t*, &env.obst, env.rbs_size);
2142 bl->anticL_in = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2143 rbitset_set(bl->anticL_in, env.rbs_size - 1);
2145 bl->id_2_memop_antic = NEW_ARR_DZ(memop_t*, &env.obst, env.rbs_size);
2148 (void) dump_block_list;
2153 insert_Loads_upwards();
2156 /* over all blocks in reverse post order */
2157 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2158 do_replacements(bl);
2161 /* not only invalidate but free them. We might allocate new out arrays
2162 on our obstack which will be deleted yet. */
2163 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_CONTROL_FLOW);
2166 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL);
2169 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
2170 ir_nodehashmap_destroy(&env.adr_map);
2171 obstack_free(&env.obst, NULL);
2173 #ifdef DEBUG_libfirm
2174 DEL_ARR_F(env.id_2_address);
2178 ir_graph_pass_t *opt_ldst_pass(const char *name)
2180 return def_graph_pass(name ? name : "ldst_df", opt_ldst);