11 #include "irnodeset.h"
17 #define OPTIMISE_LOAD_AFTER_LOAD
20 #define UNIMPLEMENTED abort();
23 DEBUG_ONLY(static firm_dbg_module_t *dbg);
26 static struct obstack obst;
27 static size_t count_addrs;
28 static ir_node** addrs;
31 static void AddressCollector(ir_node* node, void* env)
33 ir_nodeset_t* addrs_set = env;
36 addr = get_Load_ptr(node);
37 } else if (is_Store(node)) {
38 addr = get_Store_ptr(node);
42 ir_nodeset_insert(addrs_set, addr);
46 /* Collects all unique addresses used by load and store nodes of a graph and
47 * puts them into an array for later use */
48 static void CollectAddresses(ir_graph* irg)
50 ir_nodeset_t addrs_set;
52 ir_nodeset_init(&addrs_set);
53 irg_walk_graph(irg, AddressCollector, NULL, &addrs_set);
55 count_addrs = ir_nodeset_size(&addrs_set);
56 DB((dbg, LEVEL_1, "===> %+F uses %u unique addresses\n", irg, (uint)count_addrs));
57 if (count_addrs != 0) {
58 ir_nodeset_iterator_t addr_iter;
61 addrs = NEW_ARR_D(ir_node*, &obst, count_addrs);
62 ir_nodeset_iterator_init(&addr_iter, &addrs_set);
63 for (i = 0; i < count_addrs; i++) {
64 ir_node* addr = ir_nodeset_iterator_next(&addr_iter);
66 set_irn_link(addr, (void*)(uintptr_t)i);
68 DB((dbg, LEVEL_2, "===> Collected unique symbolic address %+F\n", addr));
74 static void AliasSetAdder(ir_node* block, void* env)
76 ir_nodeset_t* alias_set;
79 alias_set = NEW_ARR_D(ir_nodeset_t, &obst, count_addrs);
80 for (i = 0; i < count_addrs; i++) {
81 ir_nodeset_init(&alias_set[i]);
83 set_irn_link(block, alias_set);
87 static void SetStartAddressesTop(ir_graph* irg)
91 ir_nodeset_t* start_addrs;
94 initial_mem = get_irg_initial_mem(irg);
95 start_block = get_irg_start_block(irg);
96 start_addrs = get_irn_link(start_block);
97 for (i = 0; i < count_addrs; i++) {
98 ir_nodeset_insert(&start_addrs[i], initial_mem);
100 mark_Block_block_visited(start_block);
104 static void AliasSetDestroyer(ir_node* block, void* env)
106 ir_nodeset_t* alias_set = get_irn_link(block);
109 for (i = 0; i < count_addrs; i++) {
110 ir_nodeset_destroy(&alias_set[i]);
115 static ir_alias_relation AliasTest(ir_graph* irg, ir_node* addr, ir_mode* mode, ir_node* other)
120 if (is_Proj(other)) other = get_Proj_pred(other);
122 if (is_Load(other)) {
123 other_addr = get_Load_ptr(other);
124 } else if (is_Store(other)) {
125 other_addr = get_Store_ptr(other);
130 other_mode = get_irn_mode(other);
131 return get_alias_relation(irg, addr, mode, other_addr, other_mode);
135 static int WalkMem(ir_graph* irg, ir_node* node, ir_node* last_block);
138 static void WalkMemPhi(ir_graph* irg, ir_node* block, ir_node* phi)
140 size_t n = get_Phi_n_preds(phi);
144 ir_nodeset_t* thissets;
146 for (i = 0; i < n; i++) {
147 WalkMem(irg, get_Phi_pred(phi, i), block);
150 thissets = get_irn_link(block);
151 NEW_ARR_A(ir_node*, in, n);
152 for (j = 0; j < count_addrs; j++) {
155 for (i = 0; i < n; i++) {
156 ir_nodeset_t* predsets = get_irn_link(get_nodes_block(get_Phi_pred(phi, i)));
157 size_t size = ir_nodeset_size(&predsets[j]);
158 ir_nodeset_iterator_t iter;
160 ir_nodeset_iterator_init(&iter, &predsets[j]);
163 } else if (size == 1) {
164 in[i] = ir_nodeset_iterator_next(&iter);
169 NEW_ARR_A(ir_node*, sync_in, size);
170 for (k = 0; k < size; k++) {
171 sync_in[k] = ir_nodeset_iterator_next(&iter);
173 in[i] = new_r_Sync(irg, get_Block_cfgpred_block(block, i), size, sync_in);
176 new_phi = new_r_Phi(irg, block, n, in, mode_M);
177 ir_nodeset_insert(&thissets[j], new_phi);
180 exchange(phi, new_Bad());
184 static void PlaceLoad(ir_graph* irg, ir_node* block, ir_node* load, ir_node* memory)
186 ir_node* addr = get_Load_ptr(load);
187 size_t addr_idx = (size_t)(uintptr_t)get_irn_link(addr);
188 ir_nodeset_t* interfere_sets = get_irn_link(block);
189 ir_nodeset_t* interfere_set = &interfere_sets[addr_idx];
190 size_t size = ir_nodeset_size(interfere_set);
191 ir_nodeset_iterator_t interfere_iter;
195 ir_nodeset_iterator_init(&interfere_iter, interfere_set);
197 ir_node* after = ir_nodeset_iterator_next(&interfere_iter);
198 if (is_Proj(after)) {
199 ir_node* pred = get_Proj_pred(after);
201 #ifdef OPTIMISE_LOAD_AFTER_LOAD
202 if (get_Load_ptr(pred) == addr && get_Load_mode(pred) == get_Load_mode(load)) {
203 exchange(load, pred);
207 after = get_Load_mem(pred);
210 DB((dbg, LEVEL_3, "===> %+F must be executed after %+F\n", load, after));
211 set_Load_mem(load, after);
216 NEW_ARR_A(ir_node*, after_set, size);
217 for (i = 0; i < size; i++) {
218 ir_node* mem = ir_nodeset_iterator_next(&interfere_iter);
220 ir_node* pred = get_Proj_pred(mem);
222 #ifdef OPTIMISE_LOAD_AFTER_LOAD
223 if (get_Load_ptr(pred) == addr && get_Load_mode(pred) == get_Load_mode(load)) {
224 exchange(load, pred);
228 mem = get_Load_mem(pred);
232 sync = new_r_Sync(irg, block, size, after_set);
234 set_Load_mem(load, sync);
237 for (i = 0; i < count_addrs; i++) {
238 ir_mode* mode = get_Load_mode(load);
239 ir_node* other_addr = addrs[i];
240 ir_mode* other_mode = mode; // XXX second mode is nonsense
241 ir_alias_relation rel = get_alias_relation(irg, addr, mode, other_addr, other_mode);
244 DB((dbg, LEVEL_3, "===> Testing for alias between %+F and %+F. Relation is %d\n", addr, other_addr, rel));
245 if (rel == no_alias) {
248 DB((dbg, LEVEL_3, "===> %+F potentially aliases address %+F\n", load, other_addr));
250 ir_nodeset_iterator_init(&interfere_iter, &interfere_sets[i]);
251 while ((other_node = ir_nodeset_iterator_next(&interfere_iter)) != NULL) {
252 if (is_Proj(other_node) && is_Load(get_Proj_pred(other_node))) continue;
253 if (AliasTest(irg, addr, mode, other_node) != no_alias) {
254 DB((dbg, LEVEL_3, "===> Removing %+F from execute-after set of %+F due to %+F\n", other_node, addrs[i], load));
255 ir_nodeset_remove_iterator(&interfere_sets[i], &interfere_iter);
259 ir_nodeset_insert(&interfere_sets[i], memory);
264 static void PlaceStore(ir_graph* irg, ir_node* block, ir_node* store, ir_node* memory)
266 ir_node* addr = get_Store_ptr(store);
267 size_t addr_idx = (size_t)(uintptr_t)get_irn_link(addr);
268 ir_nodeset_t* interfere_sets = get_irn_link(block);
269 ir_nodeset_t* interfere_set = &interfere_sets[addr_idx];
270 size_t size = ir_nodeset_size(interfere_set);
271 ir_nodeset_iterator_t interfere_iter;
275 ir_nodeset_iterator_init(&interfere_iter, interfere_set);
277 ir_node* after = ir_nodeset_iterator_next(&interfere_iter);
278 DB((dbg, LEVEL_3, "===> %+F must be executed after %+F\n", store, after));
279 set_Store_mem(store, after);
284 NEW_ARR_A(ir_node*, after_set, size);
285 for (i = 0; i < size; i++) {
286 after_set[i] = ir_nodeset_iterator_next(&interfere_iter);
287 sync = new_r_Sync(irg, block, size, after_set);
289 set_Store_mem(store, sync);
292 for (i = 0; i < count_addrs; i++) {
293 ir_mode* mode = get_irn_mode(get_Store_value(store));
294 ir_node* other_addr = addrs[i];
295 ir_mode* other_mode = mode; // XXX second mode is nonsense
296 ir_alias_relation rel = get_alias_relation(irg, addr, mode, other_addr, other_mode);
299 DB((dbg, LEVEL_3, "===> Testing for alias between %+F and %+F. Relation is %d\n", addr, other_addr, rel));
300 if (rel == no_alias) {
303 DB((dbg, LEVEL_3, "===> %+F potentially aliases address %+F\n", store, other_addr));
305 ir_nodeset_iterator_init(&interfere_iter, &interfere_sets[i]);
306 while ((other_node = ir_nodeset_iterator_next(&interfere_iter)) != NULL) {
307 if (AliasTest(irg, addr, mode, other_node) != no_alias) {
308 DB((dbg, LEVEL_3, "===> Removing %+F from execute-after set of %+F due to %+F\n", other_node, addrs[i], store));
309 ir_nodeset_remove_iterator(&interfere_sets[i], &interfere_iter);
313 ir_nodeset_insert(&interfere_sets[i], memory);
318 static int WalkMem(ir_graph* irg, ir_node* node, ir_node* last_block)
320 int block_change = 0;
321 ir_node* block = get_nodes_block(node);
323 ir_node* memory = node;
324 ir_nodeset_t* addr_sets;
326 if (block != last_block) {
328 if (Block_not_block_visited(block)) {
329 mark_Block_block_visited(block);
331 DB((dbg, LEVEL_2, "===> Hit already visited block at %+F\n", node));
337 if (is_Proj(node)) node = get_Proj_pred(node);
340 WalkMemPhi(irg, block, node);
342 } else if (is_Sync(node)) {
344 } else if (is_Return(node)) {
345 pred = get_Return_mem(node);
347 pred = get_fragile_op_mem(node);
350 if (WalkMem(irg, pred, block)) {
351 // There was a block change
352 DB((dbg, LEVEL_3, "===> There is a block change before %+F\n", node));
353 if (get_Block_n_cfgpreds(block) == 1) {
354 // Just one predecessor, inherit its alias sets
355 ir_nodeset_t* predsets = get_irn_link(get_nodes_block(pred));
356 ir_nodeset_t* thissets = get_irn_link(block);
359 DB((dbg, LEVEL_3, "===> Copying the only predecessor's address sets\n"));
361 for (i = 0; i < count_addrs; i++) {
362 ir_nodeset_iterator_t prediter;
365 ir_nodeset_iterator_init(&prediter, &predsets[i]);
366 while ((addr = ir_nodeset_iterator_next(&prediter)) != NULL) {
367 ir_nodeset_insert(&thissets[i], addr);
373 DB((dbg, LEVEL_3, "===> Detotalising %+F\n", node));
375 addr_sets = get_irn_link(block);
378 PlaceLoad(irg, block, node, memory);
379 } else if (is_Store(node)) {
380 PlaceStore(irg, block, node, memory);
382 ir_nodeset_t sync_set;
385 ir_nodeset_iterator_t sync_set_iter;
388 DB((dbg, LEVEL_3, "===> Fallback: %+F aliases everything\n", node));
390 ir_nodeset_init(&sync_set);
391 for (i = 0; i < count_addrs; i++) {
392 ir_nodeset_iterator_t iter;
395 ir_nodeset_iterator_init(&iter, &addr_sets[i]);
396 while ((mem = ir_nodeset_iterator_next(&iter)) != NULL) {
397 ir_nodeset_insert(&sync_set, mem);
401 sync_arity = ir_nodeset_size(&sync_set);
402 ir_nodeset_iterator_init(&sync_set_iter, &sync_set);
403 if (sync_arity == 1) {
404 after = ir_nodeset_iterator_next(&sync_set_iter);
408 NEW_ARR_A(ir_node*, sync_in, sync_arity);
409 for (i = 0; i < sync_arity; i++) {
410 sync_in[i] = ir_nodeset_iterator_next(&sync_set_iter);
412 after = new_r_Sync(irg, block, sync_arity, sync_in);
414 set_irn_n(node, 0, after); // XXX unnice way to set the memory input
416 for (i = 0; i < count_addrs; i++) {
417 ir_nodeset_iterator_t iter;
418 ir_nodeset_iterator_init(&iter, &addr_sets[i]);
419 while (ir_nodeset_iterator_next(&iter) != NULL) {
420 ir_nodeset_remove_iterator(&addr_sets[i], &iter);
422 ir_nodeset_insert(&addr_sets[i], memory);
430 static void Detotalise(ir_graph* irg)
432 ir_node* end_block = get_irg_end_block(irg);
433 size_t npreds = get_Block_n_cfgpreds(end_block);
436 for (i = 0; i < npreds; i++) {
437 ir_node* pred = get_Block_cfgpred(end_block, i);
438 assert(is_Return(pred));
439 DB((dbg, LEVEL_2, "===> Starting memory walk at %+F\n", pred));
440 WalkMem(irg, pred, NULL);
445 static void AddSyncPreds(ir_nodeset_t* preds, ir_node* sync)
447 size_t n = get_Sync_n_preds(sync);
450 for (i = 0; i < n; i++) {
451 ir_node* pred = get_Sync_pred(sync, i);
453 AddSyncPreds(preds, pred);
455 ir_nodeset_insert(preds, pred);
461 static void NormaliseSync(ir_node* node, void* env)
464 ir_nodeset_iterator_t iter;
469 if (!is_Sync(node)) return;
471 ir_nodeset_init(&preds);
472 AddSyncPreds(&preds, node);
474 count_preds = ir_nodeset_size(&preds);
475 if (count_preds != get_Sync_n_preds(node)) {
476 NEW_ARR_A(ir_node*, in, count_preds);
477 ir_nodeset_iterator_init(&iter, &preds);
478 for (i = 0; i < count_preds; i++) {
479 ir_node* pred = ir_nodeset_iterator_next(&iter);
480 assert(pred != NULL);
483 set_irn_in(node, count_preds, in);
486 ir_nodeset_destroy(&preds);
490 void opt_ldst2(ir_graph* irg)
492 FIRM_DBG_REGISTER(dbg, "firm.opt.ldst2");
493 DB((dbg, LEVEL_1, "===> Performing load/store optimisation on %+F\n", irg));
495 normalize_one_return(irg);
499 if (1 /* XXX */ || get_opt_alias_analysis()) {
500 assure_irg_address_taken_computed(irg);
501 assure_irp_globals_address_taken_computed();
505 CollectAddresses(irg);
506 if (count_addrs == 0) return;
508 irg_block_walk_graph(irg, AliasSetAdder, NULL, NULL);
509 inc_irg_block_visited(irg);
510 SetStartAddressesTop(irg);
513 irg_block_walk_graph(irg, AliasSetDestroyer, NULL, NULL);
514 obstack_free(&obst, NULL);
516 normalize_proj_nodes(irg);
517 irg_walk_graph(irg, NormaliseSync, NULL, NULL);
518 optimize_graph_df(irg);
519 irg_walk_graph(irg, NormaliseSync, NULL, NULL);