2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Dataflow driven Load/Store optimizations, uses some ideas from
24 * @author Michael Beck
39 #include "irnodemap.h"
40 #include "raw_bitset.h"
45 * Mapping an address to an densed ID.
47 typedef struct address_entry_t {
48 unsigned id; /**< The ID */
55 FLAG_KILL_LOADS = 1, /**< KILL all Loads */
56 FLAG_KILL_STORES = 2, /**< KILL all Stores */
57 FLAG_KILLED_NODE = 4, /**< this node was killed */
58 FLAG_EXCEPTION = 8, /**< this node has exception flow */
59 FLAG_IGNORE = 16, /**< ignore this node (volatile or other) */
60 /** this memop KILLS all addresses */
61 FLAG_KILL_ALL = FLAG_KILL_LOADS|FLAG_KILL_STORES
65 * A value: This represents a value stored at a given address in
66 * memory. Do not confuse with values from value numbering.
68 typedef struct value_t value_t;
70 ir_node *address; /**< the address of this value */
71 ir_node *value; /**< the value itself */
72 ir_mode *mode; /**< the mode of the value */
73 unsigned id; /**< address id */
77 * A memop describes an memory-related operation.
78 * These are Loads/Store and all other ops that might modify
79 * memory (Calls, CopyB) or causing exceptions.
81 typedef struct memop_t memop_t;
83 value_t value; /**< the value of this memop: only defined for Load/Store */
84 ir_node *node; /**< the memory op itself */
85 ir_node *mem; /**< the memory FROM this node */
86 ir_node *replace; /**< the replacement node if this memop is replaced */
87 memop_t *next; /**< links to the next memory op in the block in forward order. */
88 memop_t *prev; /**< links to the previous memory op in the block in forward order. */
89 unsigned flags; /**< memop flags */
93 * Additional data for every basic block.
95 typedef struct block_t block_t;
97 memop_t *memop_forward; /**< topologically sorted list of memory ops in this block */
98 memop_t *memop_backward; /**< last memop in the list */
99 unsigned *avail_out; /**< out-set of available addresses */
100 memop_t **id_2_memop_avail; /**< maps avail address ids to memops */
101 unsigned *anticL_in; /**< in-set of anticipated Load addresses */
102 memop_t **id_2_memop; /**< maps address ids to memops */
103 ir_node *block; /**< the associated block */
104 block_t *forward_next; /**< next block entry for forward iteration */
105 block_t *backward_next; /**< next block entry for backward iteration */
106 memop_t *avail; /**< used locally for the avail map */
109 #define get_block_entry(block) ((block_t *)get_irn_link(block))
112 * Metadata for this pass.
114 typedef struct ldst_env_t {
115 struct obstack obst; /**< obstack for temporary data */
116 ir_nodemap_t adr_map; /**< Map addresses to */
117 block_t *forward; /**< Inverse post-order list of all blocks Start->End */
118 block_t *backward; /**< Inverse post-order list of all blocks End->Start */
119 ir_node *start_bl; /**< start block of the current graph */
120 unsigned *curr_set; /**< current set of addresses */
121 unsigned curr_adr_id; /**< number for address mapping */
122 unsigned n_mem_ops; /**< number of memory operations (Loads/Stores) */
123 unsigned rbs_size; /**< size of all bitsets in bytes */
124 int changed; /**< Flags for changed graph state */
129 static firm_dbg_module_t *dbg;
131 /* the one and only environment */
135 * Dumps the block list.
137 * @param ldst environment
139 static void dump_block_list(ldst_env *env) {
144 for (entry = env->forward; entry != NULL; entry = entry->forward_next) {
145 DB((dbg, LEVEL_2, "%+F {", entry->block));
148 for (op = entry->memop_forward; op != NULL; op = op->next) {
150 DB((dbg, LEVEL_2, "\n\t"));
151 } DB((dbg, LEVEL_2, "%+F", op->node));
152 if ((op->flags & FLAG_KILL_ALL) == FLAG_KILL_ALL)
153 DB((dbg, LEVEL_2, "X"));
154 else if (op->flags & FLAG_KILL_LOADS)
155 DB((dbg, LEVEL_2, "L"));
156 else if (op->flags & FLAG_KILL_STORES)
157 DB((dbg, LEVEL_2, "S"));
158 DB((dbg, LEVEL_2, ", "));
162 DB((dbg, LEVEL_2, "\n}\n\n"));
167 * Dumps the current set.
169 * @param bl current block
170 * @param s name of the set
172 static void dump_curr(block_t *bl, const char *s) {
174 unsigned end = env.n_mem_ops * 2 - 1;
177 DB((dbg, LEVEL_2, "%s[%+F] = {", s, bl->block));
179 for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
180 memop_t *op = bl->id_2_memop[pos];
183 DB((dbg, LEVEL_2, "\n\t"));
185 DB((dbg, LEVEL_2, "<%+F, %+F>, ", op->value.address, op->value.value));
188 DB((dbg, LEVEL_2, "\n}\n"));
192 #define dump_block_list()
193 #define dump_curr(bl, s)
194 #endif /* DEBUG_libfirm */
197 * Walk over the memory edges from definition to users.
199 * @param irn start node
200 * @param pre pre walker function
201 * @param post post walker function
202 * @param ctx context parameter for the walker functions
204 static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx) {
208 mark_irn_visited(irn);
213 mode = get_irn_mode(irn);
214 if (mode == mode_M) {
215 /* every successor uses memory */
216 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
217 ir_node *succ = get_irn_out(irn, i);
219 if (! irn_visited(succ))
220 walk_memory(succ, pre, post, ctx);
222 } else if (mode == mode_T) {
223 /* only some Proj's uses memory */
224 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
225 ir_node *proj = get_irn_out(irn, i);
227 if (get_irn_mode(proj) == mode_M && ! irn_visited(proj))
228 walk_memory(proj, pre, post, ctx);
236 * Walks over all memory nodes of a graph.
239 * @param pre pre walker function
240 * @param post post walker function
241 * @param ctx context parameter for the walker functions
243 static void walk_memory_irg(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *ctx) {
244 inc_irg_visited(irg);
246 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
249 * there are two possible sources for memory: initial_mem and nomem
250 * we ignore nomem as this should NOT change the memory
252 walk_memory(get_irg_initial_mem(irg), pre, post, ctx);
254 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
258 * Block walker: allocate an block entry for every block.
260 static void prepare_blocks(ir_node *block, void *ctx) {
261 block_t *entry = obstack_alloc(&env.obst, sizeof(*entry));
265 entry->memop_forward = NULL;
266 entry->memop_backward = NULL;
267 entry->avail_out = NULL;
268 entry->id_2_memop_avail = NULL;
269 entry->anticL_in = NULL;
270 entry->id_2_memop = NULL;
271 entry->block = block;
272 entry->forward_next = env.forward;
273 entry->backward_next = NULL;
275 set_irn_link(block, entry);
277 /* create the list in inverse order */
282 * Block walker: create backward links for the memops of a block.
284 static void collect_backward(ir_node *block, void *ctx) {
285 block_t *entry = get_block_entry(block);
289 entry->backward_next = env.backward;
291 /* create the list in inverse order */
292 env.backward = entry;
294 /* create backward links for all memory ops */
296 for (op = entry->memop_forward; op != NULL; op = op->next) {
300 entry->memop_backward = last;
306 * @param irn the IR-node representing the memop
308 static memop_t *alloc_memop(ir_node *irn) {
309 memop_t *m = obstack_alloc(&env.obst, sizeof(*m));
311 m->value.address = NULL;
312 m->value.value = NULL;
313 m->value.mode = NULL;
324 * Register an address and allocate an ID for it.
326 * @param adr the IR-node representing the address
328 static unsigned register_address(ir_node *adr) {
329 address_entry *entry = ir_nodemap_get(&env.adr_map, adr);
333 entry = obstack_alloc(&env.obst, sizeof(*entry));
335 entry->id = env.curr_adr_id++;
336 ir_nodemap_insert(&env.adr_map, adr, entry);
342 * Return the memory properties of a call node.
344 * @param call the call node
346 * return a bitset of mtp_property_const and mtp_property_pure
348 static unsigned get_Call_memory_properties(ir_node *call) {
349 ir_type *call_tp = get_Call_type(call);
350 unsigned prop = get_method_additional_properties(call_tp);
352 /* check first the call type */
353 if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
354 /* try the called entity */
355 ir_node *ptr = get_Call_ptr(call);
357 if (is_Global(ptr)) {
358 ir_entity *ent = get_Global_entity(ptr);
360 prop = get_entity_additional_properties(ent);
363 return prop & (mtp_property_const|mtp_property_pure);
367 * Update a memop for a Load.
371 static void update_Load_memop(memop_t *m) {
373 ir_node *load = m->node;
374 ir_node *adr = get_Load_ptr(load);
376 if (get_Load_volatility(load) == volatility_is_volatile)
377 m->flags |= FLAG_IGNORE;
379 m->value.address = adr;
381 for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
382 ir_node *proj = get_irn_out(load, i);
384 switch (get_Proj_proj(proj)) {
386 m->value.value = proj;
387 m->value.mode = get_irn_mode(proj);
389 case pn_Load_X_except:
390 m->flags |= FLAG_EXCEPTION;
398 if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) {
399 /* only create an address if this node is NOT killed immediately or ignored */
400 m->value.id = register_address(adr);
403 /* no user, KILL it */
404 m->flags |= FLAG_KILLED_NODE;
409 * Update a memop for a Store.
413 static void update_Store_memop(memop_t *m) {
415 ir_node *store = m->node;
416 ir_node *adr = get_Store_ptr(store);
418 if (get_Store_volatility(store) == volatility_is_volatile) {
419 m->flags |= FLAG_IGNORE;
421 /* only create an address if this node is NOT ignored */
422 m->value.id = register_address(adr);
426 m->value.address = adr;
428 for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
429 ir_node *proj = get_irn_out(store, i);
431 switch (get_Proj_proj(proj)) {
432 case pn_Store_X_except:
433 m->flags |= FLAG_EXCEPTION;
440 m->value.value = get_Store_value(store);
441 m->value.mode = get_irn_mode(m->value.value);
445 * Update a memop for a Call.
449 static void update_Call_memop(memop_t *m) {
450 ir_node *call = m->node;
451 unsigned prop = get_Call_memory_properties(call);
454 if (prop & mtp_property_const) {
455 /* A constant call did NOT use memory at all, we
456 can kick it from the list. */
457 } else if (prop & mtp_property_pure) {
458 /* pure calls READ memory */
459 m->flags = FLAG_KILL_STORES;
461 m->flags = FLAG_KILL_ALL;
463 for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
464 ir_node *proj = get_irn_out(call, i);
466 switch (get_Proj_proj(proj)) {
467 case pn_Call_X_except:
468 m->flags |= FLAG_EXCEPTION;
470 case pn_Call_M_regular:
478 * Update a memop for a Div/Mod/Quot/DivMod.
482 static void update_DivOp_memop(memop_t *m) {
483 ir_node *div = m->node;
486 for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
487 ir_node *proj = get_irn_out(div, i);
489 switch (get_Proj_proj(proj)) {
490 case pn_Generic_X_except:
491 m->flags |= FLAG_EXCEPTION;
493 case pn_Generic_M_regular:
501 * Memory walker: collect all memory ops and build topological lists.
503 static void collect_memops(ir_node *irn, void *ctx) {
510 /* we can safely ignore ProjM's except the initial memory */
511 if (irn != get_irg_initial_mem(current_ir_graph))
515 op = alloc_memop(irn);
516 block = get_nodes_block(irn);
517 entry = get_block_entry(block);
520 /* Phis must be always placed first */
521 op->next = entry->memop_forward;
522 entry->memop_forward = op;
523 if (entry->memop_backward == NULL)
524 entry->memop_backward = op;
526 switch (get_irn_opcode(irn)) {
528 update_Load_memop(op);
531 update_Store_memop(op);
534 update_Call_memop(op);
546 /* we can those to find the memory edge */
552 update_DivOp_memop(op);
556 /* TODO: handle some builtins */
558 /* unsupported operation */
559 op->flags = FLAG_KILL_ALL;
563 /* all other should be placed last */
564 if (entry->memop_backward == NULL) {
565 entry->memop_forward = entry->memop_backward = op;
567 entry->memop_backward->next = op;
568 entry->memop_backward = op;
574 * Find an address in the current set.
576 * @param bl the block
577 * @param value the value to be searched for
579 static memop_t *find_address(const block_t *bl, const value_t *value) {
580 if (rbitset_is_set(env.curr_set, value->id)) {
581 memop_t *res = bl->id_2_memop[value->id];
583 if (res->value.mode == value->mode)
585 /* allow hidden casts */
586 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
587 get_mode_arithmetic(value->mode) == irma_twos_complement &&
588 get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
595 * Find an address in the avail_out set.
597 * @param bl the block
598 * @param value the value to be searched for
600 static memop_t *find_address_avail(const block_t *bl, const value_t *value) {
601 if (rbitset_is_set(bl->avail_out, value->id)) {
602 memop_t *res = bl->id_2_memop_avail[value->id];
604 if (res->value.mode == value->mode)
606 /* allow hidden casts */
607 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
608 get_mode_arithmetic(value->mode) == irma_twos_complement &&
609 get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
616 * Kill all Loads from the current set.
618 * @param bl the current block
620 static void kill_all_loads(block_t *bl) {
622 unsigned end = env.n_mem_ops * 2 - 1;
624 for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
625 memop_t *op = bl->id_2_memop[pos];
627 if (! is_Store(op->node))
628 rbitset_clear(env.curr_set, pos);
633 * Kill all Stores from the current set.
635 * @param bl the current block
637 static void kill_all_stores(block_t *bl) {
639 unsigned end = env.n_mem_ops * 2 - 1;
641 for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
642 memop_t *op = bl->id_2_memop[pos];
644 if (is_Store(op->node))
645 rbitset_clear(env.curr_set, pos);
650 * Kill all addresses from the current set.
652 static void kill_all(void) {
653 rbitset_clear_all(env.curr_set, env.rbs_size);
656 rbitset_set(env.curr_set, env.rbs_size - 1);
661 * Kill Stores that are not alias free due to a Load value from the current set.
663 * @param bl the block
664 * @param value the Load value
666 static void kill_stores(block_t *bl, const value_t *value) {
668 unsigned end = env.n_mem_ops * 2 - 1;
670 for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
671 memop_t *op = bl->id_2_memop[pos];
673 if (is_Store(op->node)) {
674 if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
675 op->value.address, op->value.mode)) {
676 rbitset_clear(env.curr_set, pos);
677 bl->id_2_memop[pos] = NULL;
684 * Kill memops that are not alias free due to a Store value from the current set.
686 * @param bl the block
687 * @param value the Store value
689 static void kill_memops(block_t *bl, const value_t *value) {
691 unsigned end = env.n_mem_ops * 2 - 1;
693 for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
694 memop_t *op = bl->id_2_memop[pos];
696 if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
697 op->value.address, op->value.mode)) {
698 rbitset_clear(env.curr_set, pos);
699 bl->id_2_memop[pos] = NULL;
705 * Add the value of a memop to the current set.
707 * @param bl the block
708 * @param op the memory op
710 static void add_memop(block_t *bl, memop_t *op) {
711 rbitset_set(env.curr_set, op->value.id);
712 bl->id_2_memop[op->value.id] = op;
716 * Add the value of a memop to the avail_out set.
718 * @param bl the block
719 * @param op the memory op
721 static void add_memop_avail(block_t *bl, memop_t *op) {
722 rbitset_set(bl->avail_out, op->value.id);
723 bl->id_2_memop_avail[op->value.id] = op;
727 * find a definition for a value in the given block.
729 * @param block the block
730 * @param value the value
732 * @return the definition
734 static ir_node *find_definition(ir_node *block, const value_t *value) {
735 ir_node *def_bl = get_nodes_block(value->value);
740 if (block_dominates(def_bl, block))
743 /* no: we need a new Phi */
744 n = get_Block_n_cfgpreds(block);
747 block = get_Block_cfgpred_block(block, 0);
748 n = get_Block_n_cfgpreds(block);
749 mop = find_address(get_block_entry(block), value);
755 NEW_ARR_A(ir_node *, in, n);
756 for (i = n - 1; i >= 0; --i) {
757 ir_node *pred_bl = get_Block_cfgpred_block(block, i);
758 mop = find_address(get_block_entry(pred_bl), value);
759 in[i] = find_definition(pred_bl, &mop->value);
762 phi = new_r_Phi(current_ir_graph, block, n, in, value->mode);
763 DB((dbg, LEVEL_2, "Created new Phi %+F for value %+F in block %+F\n", phi, value->value, block));
768 * Mark a Load memop to be replace by a definition
770 * @param op the Load memop
772 static void mark_replace_load(memop_t *op, ir_node *def) {
774 op->flags |= FLAG_KILLED_NODE;
779 * Mark a Store memop to be removed.
781 * @param op the Store memop
783 static void mark_remove_store(memop_t *op) {
784 op->flags |= FLAG_KILLED_NODE;
788 #define BYTE_SIZE(x) (((x) + 7) >> 3)
791 * Do forward dataflow analysis on a given block to calculate the avail_out set.
793 * @param bl the block
795 * @return non-zero if the set has changed since last iteration
797 static int forward_avail(block_t *bl) {
801 ir_node *pred = get_Block_cfgpred_block(bl->block, 0);
802 block_t *pred_bl = get_block_entry(pred);
804 rbitset_cpy(env.curr_set, pred_bl->avail_out, env.rbs_size);
806 n = get_Block_n_cfgpreds(bl->block);
810 /* more than one predecessors, calculate the join */
811 for (i = n - 1; i > 0; --i) {
812 ir_node *pred = get_Block_cfgpred_block(bl->block, i);
813 block_t *pred_bl = get_block_entry(pred);
815 rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
818 /* sure that all values are in the map */
819 for (pos = env.rbs_size - 1; pos >= 0; --pos) {
820 if (! rbitset_is_set(env.curr_set, pos))
821 bl->id_2_memop[pos] = NULL;
823 for (i = n - 1; i >= 0; --i) {
824 ir_node *pred = get_Block_cfgpred_block(bl->block, i);
825 block_t *pred_bl = get_block_entry(pred);
827 if (pred_bl->id_2_memop[pos] != NULL) {
828 bl->id_2_memop[pos] = pred_bl->id_2_memop[pos];
835 /* only one predecessor, simply copy the map */
836 memcpy(bl->id_2_memop, pred_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
839 dump_curr(bl, "Avail_in");
841 for (op = bl->memop_forward; op != NULL; op = op->next) {
842 switch (get_irn_opcode(op->node)) {
850 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
851 /* do we have this already? */
852 memop_t *other = find_address(bl, &op->value);
854 if (is_Store(other->node)) {
856 DB((dbg, LEVEL_1, "RAW %+F %+F\n", op->node, other->node));
859 DB((dbg, LEVEL_1, "RAR %+F %+F\n", op->node, other->node));
861 def = find_definition(bl->block, &other->value);
862 mark_replace_load(op, def);
865 kill_stores(bl, &op->value);
871 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
872 /* do we have this store already */
873 memop_t *other = find_address(bl, &op->value);
875 if (is_Store(other->node)) {
877 DB((dbg, LEVEL_1, "WAW %+F %+F\n", op->node, other->node));
878 mark_remove_store(other);
879 /* FIXME: a Load might be get freed due to this killed store */
880 } else if (other->value.value == op->value.value) {
882 DB((dbg, LEVEL_1, "WAR %+F %+F\n", op->node, other->node));
883 mark_remove_store(op);
885 /* we overwrite the value that was loaded */
890 kill_memops(bl, &op->value);
896 switch (op->flags & (FLAG_KILL_LOADS|FLAG_KILL_STORES)) {
897 case FLAG_KILL_LOADS|FLAG_KILL_STORES:
900 case FLAG_KILL_LOADS:
903 case FLAG_KILL_STORES:
911 dump_curr(bl, "Avail_out");
912 if (!rbitset_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
914 rbitset_cpy(bl->avail_out, env.curr_set, env.rbs_size);
921 * Do backward dataflow analysis on a given block to calculate the antic set
922 * of Loaded addresses.
924 * @param bl the block
926 * @return non-zero if the set has changed since last iteration
928 static int backward_antic(block_t *bl) {
930 ir_node *succ = get_Block_cfg_out(bl->block, 0);
931 block_t *succ_bl = get_block_entry(succ);
934 rbitset_cpy(env.curr_set, succ_bl->anticL_in, env.rbs_size);
935 memcpy(bl->id_2_memop, succ_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
937 n = get_Block_n_cfg_outs(bl->block);
941 for (i = n - 1; i > 0; --i) {
942 ir_node *succ = get_Block_cfg_out(bl->block, i);
943 block_t *succ_bl = get_block_entry(succ);
945 rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size);
950 /* cleanup: kill those Loads which address is not available */
951 for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
952 memop_t *op = succ_bl->id_2_memop[pos];
953 ir_node *ptr = get_Load_ptr(op->node);
954 ir_node *ptr_bl = get_nodes_block(ptr);
956 if (!block_dominates(ptr_bl, bl->block))
957 rbitset_clear(env.curr_set, pos);
961 dump_curr(bl, "AnticL_out");
963 for (op = bl->memop_backward; op != NULL; op = op->prev) {
964 switch (get_irn_opcode(op->node)) {
972 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
978 if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
979 /* a Store: check which memops must be killed */
980 kill_memops(bl, &op->value);
984 switch (op->flags & (FLAG_KILL_LOADS|FLAG_KILL_STORES)) {
985 case FLAG_KILL_LOADS|FLAG_KILL_STORES:
988 case FLAG_KILL_LOADS:
991 case FLAG_KILL_STORES:
999 dump_curr(bl, "AnticL_in");
1000 if (! rbitset_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
1002 rbitset_cpy(bl->anticL_in, env.curr_set, env.rbs_size);
1009 * Replace a Load memop by a already known value.
1011 * @param op the Load memop
1013 static void replace_load(memop_t *op) {
1014 ir_node *load = op->node;
1015 ir_node *def = skip_Id(op->replace);
1020 DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, is_Proj(def) ? get_Proj_pred(def) : def));
1022 if (op->flags & FLAG_EXCEPTION) {
1023 /* bad: this node is unused and executed for exception only */
1024 DB((dbg, LEVEL_1, "Unused %+F executed for exception only ...\n", load));
1027 DB((dbg, LEVEL_1, "Killing unused %+F\n", load));
1029 for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
1030 ir_node *proj = get_irn_out(load, i);
1032 switch (get_Proj_proj(proj)) {
1034 exchange(proj, get_Load_mem(load));
1037 mode = get_irn_mode(proj);
1038 if (get_irn_mode(def) != mode) {
1040 dbg_info *db = get_irn_dbg_info(load);
1041 ir_node *block = get_nodes_block(proj);
1042 def = new_rd_Conv(db, current_ir_graph, block, def, mode);
1044 exchange(proj, def);
1046 case pn_Load_X_except:
1047 exchange(proj, new_Bad());
1049 case pn_Load_X_regular:
1050 exchange(proj, new_r_Jmp(current_ir_graph, get_nodes_block(load)));
1053 panic("Unknown Proj from Load");
1059 * Remove a Store memop.
1061 * @param op the Store memop
1063 static void remove_store(memop_t *op) {
1064 ir_node *store = op->node;
1067 DB((dbg, LEVEL_1, "Removing %+F\n", store));
1068 for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
1069 ir_node *proj = get_irn_out(store, i);
1071 switch (get_Proj_proj(proj)) {
1073 exchange(proj, get_Store_mem(store));
1075 case pn_Store_X_except:
1076 exchange(proj, new_Bad());
1078 case pn_Store_X_regular:
1079 exchange(proj, new_r_Jmp(current_ir_graph, get_nodes_block(store)));
1082 panic("Unknown Proj from Store");
1089 * Do all necessary replacements for a given block.
1091 * @param bl the block
1093 static void do_replacements(block_t *bl) {
1096 for (op = bl->memop_forward; op != NULL; op = op->next) {
1097 if (op->flags & FLAG_KILLED_NODE) {
1098 switch (get_irn_opcode(op->node)) {
1111 * Calculate the Avail_out sets for all basic blocks.
1113 static void calcAvail(void) {
1117 /* calculate avail_out */
1118 DB((dbg, LEVEL_2, "Calculate Avail_out\n"));
1121 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1125 /* over all blocks in reverse post order, skip the start block */
1126 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1127 need_iter |= forward_avail(bl);
1130 } while (need_iter);
1132 /* copy the content of the id_2_memop map into the id_2_memop_avail map
1133 as it must be preserved for later use */
1134 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1135 memop_t **t = bl->id_2_memop_avail;
1137 bl->id_2_memop_avail = bl->id_2_memop;
1140 DB((dbg, LEVEL_2, "Get avail set after %d iterations\n\n", i));
1144 * Calculate the Antic_in sets for all basic blocks.
1146 static void calcAntic(void) {
1149 /* calculate antic_out */
1150 DB((dbg, LEVEL_2, "Calculate Antic_in\n"));
1155 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1159 /* over all blocks in reverse post order */
1160 for (bl = env.backward->backward_next; bl != NULL; bl = bl->backward_next) {
1161 need_iter |= backward_antic(bl);
1164 } while (need_iter);
1165 DB((dbg, LEVEL_2, "Get anticipated Load set after %d iterations\n", i));
1169 * Return the node representing the last memory in a block.
1171 * @param bl the block
1173 static ir_node *find_first_memory(block_t *bl) {
1175 if (bl->memop_forward != NULL) {
1176 return bl->memop_forward->node;
1178 /* if there is NO memory in this block, go to the post dominator */
1179 bl = get_block_entry(get_Block_ipostdom(bl->block));
1184 * Return the node representing the last memory in a block.
1186 * @param bl the block
1188 static ir_node *find_last_memory(block_t *bl) {
1190 if (bl->memop_backward != NULL) {
1191 return bl->memop_backward->mem;
1193 /* if there is NO memory in this block, go to the dominator */
1194 bl = get_block_entry(get_Block_idom(bl->block));
1199 * Reroute the memory. Reroute all users of old memory
1200 * to a new memory IR-node.
1202 * @param omem the old memory IR-node
1203 * @param nmem the new memory IR-node
1205 static void reroute_mem(ir_node *omem, ir_node *nmem) {
1208 for (i = get_irn_n_outs(omem) - 1; i >= 0; --i) {
1210 ir_node *succ = get_irn_out_ex(omem, i, &n_pos);
1212 set_irn_n(succ, n_pos, nmem);
1215 /* all edges formally point to omem now point to nmem */
1216 nmem->out = omem->out;
1222 static void insert_Load(ir_node *block, void *ctx) {
1223 int *new_stuff = ctx;
1225 int i, n = get_Block_n_cfgpreds(block);
1227 unsigned end = env.n_mem_ops * 2 - 1;
1232 bl = get_block_entry(block);
1234 for (pos = rbitset_next(bl->anticL_in, pos, 1); pos != end; pos = rbitset_next(bl->anticL_in, pos + 1, 1)) {
1235 memop_t *op = bl->id_2_memop[pos];
1238 assert(is_Load(op->node));
1240 if (op->flags & FLAG_KILLED_NODE)
1244 for (i = n - 1; i >= 0; --i) {
1245 ir_node *pred = get_Block_cfgpred_block(block, i);
1246 block_t *pred_bl = get_block_entry(pred);
1247 memop_t *e = find_address_avail(pred_bl, &op->value);
1250 ir_node *block = get_nodes_block(op->value.address);
1251 if (! block_dominates(block, pred)) {
1252 /* cannot place a copy here */
1256 pred_bl->avail = NULL;
1263 ir_mode *mode = op->value.mode;
1266 NEW_ARR_A(ir_node *, in, n);
1268 for (i = n - 1; i >= 0; --i) {
1269 ir_node *pred = get_Block_cfgpred_block(block, i);
1270 block_t *pred_bl = get_block_entry(pred);
1272 if (pred_bl->avail == NULL) {
1273 /* create a new Load here and make to make it fully redundant */
1274 dbg_info *db = get_irn_dbg_info(op->node);
1275 ir_node *last_mem = find_last_memory(pred_bl);
1276 ir_node *load, *def;
1279 load = new_rd_Load(db, current_ir_graph, pred, last_mem, op->value.address, mode, cons_none);
1280 def = new_r_Proj(current_ir_graph, pred, load, mode, pn_Load_res);
1281 DB((dbg, LEVEL_1, "Created new %+F for party redundant %+F\n", load, op->node));
1283 new_op = alloc_memop(load);
1284 new_op->mem = new_r_Proj(current_ir_graph, pred, load, mode_M, pn_Load_M);
1285 new_op->value.address = op->value.address;
1286 new_op->value.id = op->value.id;
1287 new_op->value.mode = mode;
1288 new_op->value.value = def;
1290 new_op->prev = pred_bl->memop_backward;
1291 pred_bl->memop_backward = new_op;
1293 /* We have add a new last memory op in pred block.
1294 If pred had already a last mem, reroute all memory
1296 if (get_nodes_block(last_mem) == pred) {
1297 reroute_mem(last_mem, new_op->mem);
1300 /* we added this load at the end, so it will be avail anyway */
1301 add_memop_avail(pred_bl, new_op);
1302 pred_bl->avail = new_op;
1304 in[i] = pred_bl->avail->value.value;
1306 phi = new_r_Phi(current_ir_graph, block, n, in, mode);
1307 mark_replace_load(op, phi);
1310 if (get_nodes_block(op->node) == block) {
1311 /* The redundant node was in the current block:
1312 In that case, DO NOT update avail_out. If it was NOT
1313 avail although it is executed in this bLock, it is killed by a later
1317 /* The redundant node is NOT in the current block and anticipated.
1318 This can only happen IFF nothings kills the Load in the current block,
1319 so it will be avail in the next iteration.
1321 add_memop_avail(bl, op);
1323 /* TODO propagate it downwards */
1330 * Insert Loads upwards.
1332 static void insert_Loads_upwards(void) {
1335 /* calculate antic_out */
1336 DB((dbg, LEVEL_2, "Inserting Loads"));
1339 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1342 dom_tree_walk_irg(current_ir_graph, insert_Load, NULL, &need_iter);
1344 } while (need_iter);
1345 DB((dbg, LEVEL_2, "Finished Load inserting after %d iterations\n", i));
1348 int opt_ldst(ir_graph *irg) {
1350 ir_graph *rem = current_ir_graph;
1352 current_ir_graph = irg;
1354 FIRM_DBG_REGISTER(dbg, "firm.opt.ldst");
1356 DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
1358 /* we need landing pads */
1359 remove_critical_cf_edges(irg);
1361 if (get_opt_alias_analysis()) {
1362 assure_irg_entity_usage_computed(irg);
1363 assure_irp_globals_entity_usage_computed();
1366 obstack_init(&env.obst);
1367 ir_nodemap_init(&env.adr_map);
1370 env.backward = NULL;
1371 env.curr_adr_id = 0;
1374 env.start_bl = get_irg_start_block(irg);
1377 assure_irg_outs(irg);
1379 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1381 /* first step: allocate block entries: produces an
1382 inverse post-order list for the CFG */
1383 irg_out_block_walk(get_irg_start_block(irg), NULL, prepare_blocks, NULL);
1385 /* second step: find and sort all memory ops */
1386 walk_memory_irg(irg, collect_memops, NULL, NULL);
1388 if (env.n_mem_ops == 0) {
1393 /* create the backward links */
1394 irg_block_walk_graph(irg, NULL, collect_backward, NULL);
1396 /* check that we really start with the start / end block */
1397 assert(env.forward->block == env.start_bl);
1398 assert(env.backward->block == get_irg_end_block(irg));
1400 /* create address sets: we know that 2 * n_mem_ops - 1 is an upper bound for all possible addresses */
1401 env.rbs_size = 2 * env.n_mem_ops;
1403 /* create the current set */
1404 env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1405 rbitset_set(env.curr_set, env.rbs_size - 1);
1407 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
1408 /* set sentinel bits */
1409 bl->avail_out = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1410 rbitset_set(bl->avail_out, env.rbs_size - 1);
1412 bl->id_2_memop_avail = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
1413 memset(bl->id_2_memop_avail, 0, env.rbs_size * sizeof(bl->id_2_memop[0]));
1415 bl->anticL_in = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1416 rbitset_set(bl->anticL_in, env.rbs_size - 1);
1418 bl->id_2_memop = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
1419 memset(bl->id_2_memop, 0, env.rbs_size * sizeof(bl->id_2_memop[0]));
1422 // dump_block_list(&env);
1427 insert_Loads_upwards();
1430 /* over all blocks in reverse post order */
1431 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
1432 do_replacements(bl);
1435 set_irg_outs_inconsistent(irg);
1436 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
1440 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1441 ir_nodemap_destroy(&env.adr_map);
1442 obstack_free(&env.obst, NULL);
1444 current_ir_graph = rem;
1446 return env.changed != 0;