From b78a13deadcd14b661cea1c2a8b448cc79b06f63 Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Thu, 1 Jun 2006 17:04:22 +0000 Subject: [PATCH] handle Sync nodes [r7857] --- ir/opt/ldstopt.c | 312 ++++++++++++++++++++++++++++------------------- 1 file changed, 184 insertions(+), 128 deletions(-) diff --git a/ir/opt/ldstopt.c b/ir/opt/ldstopt.c index 2e9aeeab0..4ff2aebe0 100644 --- a/ir/opt/ldstopt.c +++ b/ir/opt/ldstopt.c @@ -2,7 +2,7 @@ * Project: libFIRM * File name: ir/opt/ldstopt.c * Purpose: load store optimizations - * Author: + * Author: Michael Beck * Created: * CVS-ID: $Id$ * Copyright: (c) 1998-2004 Universität Karlsruhe @@ -394,6 +394,136 @@ static compound_graph_path *get_accessed_path(ir_node *ptr) { return rec_get_accessed_path(ptr, 0); } +/** + * Follow the memory chain as long as there are only Loads + * and try to replace current Load or Store by a previous one. + * Note that in unreachable loops it might happen that we reach + * load again, as well as we can fall into a cycle. + * We break such cycles using a special visited flag. + * + * INC_MASTER() must be called before dive into + */ +static unsigned follow_Load_chain(ir_node *load, ir_node *curr) { + unsigned res = 0; + ldst_info_t *info = get_irn_link(load); + ir_node *pred; + ir_node *ptr = get_Load_ptr(load); + ir_node *mem = get_Load_mem(load); + ir_mode *load_mode = get_Load_mode(load); + + for (pred = curr; load != pred; pred = skip_Proj(get_Load_mem(pred))) { + ldst_info_t *pred_info = get_irn_link(pred); + + /* + * BEWARE: one might think that checking the modes is useless, because + * if the pointers are identical, they refer to the same object. + * This is only true in strong typed languages, not in C were the following + * is possible a = *(ir_type1 *)p; b = *(ir_type2 *)p ... + */ + + if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr && + get_irn_mode(get_Store_value(pred)) == load_mode) { + /* + * a Load immediately after a Store -- a read after write. + * We may remove the Load, if both Load & Store does not have an exception handler + * OR they are in the same block. In the latter case the Load cannot + * throw an exception when the previous Store was quiet. + * + * Why we need to check for Store Exception? If the Store cannot + * be executed (ROM) the exception handler might simply jump into + * the load block :-( + * We could make it a little bit better if we would know that the exception + * handler of the Store jumps directly to the end... + */ + if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) || + get_nodes_block(load) == get_nodes_block(pred)) { + ir_node *value = get_Store_value(pred); + + DBG_OPT_RAW(load, value); + if (info->projs[pn_Load_M]) + exchange(info->projs[pn_Load_M], mem); + + /* no exception */ + if (info->projs[pn_Load_X_except]) { + exchange( info->projs[pn_Load_X_except], new_Bad()); + res |= CF_CHANGED; + } + + if (info->projs[pn_Load_res]) + exchange(info->projs[pn_Load_res], value); + + return res | DF_CHANGED; + } + } + else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr && + get_Load_mode(pred) == load_mode) { + /* + * a Load after a Load -- a read after read. + * We may remove the second Load, if it does not have an exception handler + * OR they are in the same block. In the later case the Load cannot + * throw an exception when the previous Load was quiet. + * + * Here, there is no need to check if the previous Load has an exception + * hander because they would have exact the same exception... + */ + if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) { + DBG_OPT_RAR(load, pred); + + if (pred_info->projs[pn_Load_res]) { + /* we need a data proj from the previous load for this optimization */ + if (info->projs[pn_Load_res]) + exchange(info->projs[pn_Load_res], pred_info->projs[pn_Load_res]); + + if (info->projs[pn_Load_M]) + exchange(info->projs[pn_Load_M], mem); + } + else { + if (info->projs[pn_Load_res]) { + set_Proj_pred(info->projs[pn_Load_res], pred); + set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred)); + pred_info->projs[pn_Load_res] = info->projs[pn_Load_res]; + } + if (info->projs[pn_Load_M]) { + /* Actually, this if should not be necessary. Construct the Loads + properly!!! */ + exchange(info->projs[pn_Load_M], mem); + } + } + + /* no exception */ + if (info->projs[pn_Load_X_except]) { + exchange(info->projs[pn_Load_X_except], new_Bad()); + res |= CF_CHANGED; + } + + return res |= DF_CHANGED; + } + } + + /* follow only Load chains */ + if (get_irn_op(pred) != op_Load) + break; + + /* check for cycles */ + if (NODE_VISITED(pred_info)) + break; + MARK_NODE(pred_info); + } + + if (get_irn_op(pred) == op_Sync) { + int i; + + /* handle all Sync predecessors */ + for (i = get_Sync_n_preds(pred) - 1; i >= 0; --i) { + res |= follow_Load_chain(load, skip_Proj(get_Sync_pred(pred, i))); + if (res) + break; + } + } + + return res; +} + /** * optimize a Load */ @@ -401,7 +531,7 @@ static unsigned optimize_load(ir_node *load) { ldst_info_t *info = get_irn_link(load); ir_mode *load_mode = get_Load_mode(load); - ir_node *pred, *mem, *ptr, *new_node; + ir_node *mem, *ptr, *new_node; entity *ent; unsigned res = 0; @@ -583,92 +713,58 @@ static unsigned optimize_load(ir_node *load) * We break such cycles using a special visited flag. */ INC_MASTER(); - for (pred = skip_Proj(mem); load != pred; pred = skip_Proj(get_Load_mem(pred))) { + res = follow_Load_chain(load, skip_Proj(mem)); + return res; +} + +/** + * follow the memory chain as long as there are only Loads. + * + * INC_MASTER() must be called before dive into + */ +static unsigned follow_Load_chain_for_Store(ir_node *store, ir_node *curr) { + unsigned res = 0; + ldst_info_t *info = get_irn_link(store); + ir_node *pred; + ir_node *ptr = get_Store_ptr(store); + ir_node *mem = get_Store_mem(store); + ir_node *value = get_Store_value(store); + ir_mode *mode = get_irn_mode(value); + ir_node *block = get_nodes_block(store); + + for (pred = curr; pred != store; pred = skip_Proj(get_Load_mem(pred))) { ldst_info_t *pred_info = get_irn_link(pred); /* * BEWARE: one might think that checking the modes is useless, because * if the pointers are identical, they refer to the same object. - * This is only true in strong typed languages, not in C were the following - * is possible a = *(ir_type1 *)p; b = *(ir_type2 *)p ... + * This is only true in strong typed languages, not is C were the following + * is possible *(ir_type1 *)p = a; *(ir_type2 *)p = b ... */ - if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr && - get_irn_mode(get_Store_value(pred)) == load_mode) { + get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) { /* - * a Load immediately after a Store -- a read after write. - * We may remove the Load, if both Load & Store does not have an exception handler - * OR they are in the same block. In the latter case the Load cannot - * throw an exception when the previous Store was quiet. + * a Store after a Store in the same block -- a write after write. + * We may remove the first Store, if it does not have an exception handler. * - * Why we need to check for Store Exception? If the Store cannot - * be executed (ROM) the exception handler might simply jump into - * the load block :-( - * We could make it a little bit better if we would know that the exception - * handler of the Store jumps directly to the end... + * TODO: What, if both have the same exception handler ??? */ - if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) || - get_nodes_block(load) == get_nodes_block(pred)) { - ir_node *value = get_Store_value(pred); - - DBG_OPT_RAW(load, value); - if (info->projs[pn_Load_M]) - exchange(info->projs[pn_Load_M], mem); - - /* no exception */ - if (info->projs[pn_Load_X_except]) { - exchange( info->projs[pn_Load_X_except], new_Bad()); - res |= CF_CHANGED; - } - - if (info->projs[pn_Load_res]) - exchange(info->projs[pn_Load_res], value); - - return res | DF_CHANGED; + if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) { + DBG_OPT_WAW(pred, store); + exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) ); + return DF_CHANGED; } } else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr && - get_Load_mode(pred) == load_mode) { + value == pred_info->projs[pn_Load_res]) { /* - * a Load after a Load -- a read after read. - * We may remove the second Load, if it does not have an exception handler - * OR they are in the same block. In the later case the Load cannot - * throw an exception when the previous Load was quiet. - * - * Here, there is no need to check if the previous Load has an exception - * hander because they would have exact the same exception... + * a Store of a value after a Load -- a write after read. + * We may remove the second Store, if it does not have an exception handler. */ - if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) { - DBG_OPT_RAR(load, pred); - - if (pred_info->projs[pn_Load_res]) { - /* we need a data proj from the previous load for this optimization */ - if (info->projs[pn_Load_res]) - exchange(info->projs[pn_Load_res], pred_info->projs[pn_Load_res]); - - if (info->projs[pn_Load_M]) - exchange(info->projs[pn_Load_M], mem); - } - else { - if (info->projs[pn_Load_res]) { - set_Proj_pred(info->projs[pn_Load_res], pred); - set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred)); - pred_info->projs[pn_Load_res] = info->projs[pn_Load_res]; - } - if (info->projs[pn_Load_M]) { - /* Actually, this if should not be necessary. Construct the Loads - properly!!! */ - exchange(info->projs[pn_Load_M], mem); - } - } - - /* no exception */ - if (info->projs[pn_Load_X_except]) { - exchange(info->projs[pn_Load_X_except], new_Bad()); - res |= CF_CHANGED; - } - - return res |= DF_CHANGED; + if (! info->projs[pn_Store_X_except]) { + DBG_OPT_WAR(store, pred); + exchange( info->projs[pn_Store_M], mem ); + return DF_CHANGED; } } @@ -681,6 +777,17 @@ static unsigned optimize_load(ir_node *load) break; MARK_NODE(pred_info); } + + if (get_irn_op(pred) == op_Sync) { + int i; + + /* handle all Sync predecessors */ + for (i = get_Sync_n_preds(pred) - 1; i >= 0; --i) { + res |= follow_Load_chain_for_Store(store, skip_Proj(get_Sync_pred(pred, i))); + if (res) + break; + } + } return res; } @@ -690,74 +797,23 @@ static unsigned optimize_load(ir_node *load) static unsigned optimize_store(ir_node *store) { ldst_info_t *info = get_irn_link(store); - ir_node *pred, *mem, *ptr, *value, *block; - ir_mode *mode; - unsigned res = 0; + ir_node *ptr, *mem; if (get_Store_volatility(store) == volatility_is_volatile) return 0; - /* - * BEWARE: one might think that checking the modes is useless, because - * if the pointers are identical, they refer to the same object. - * This is only true in strong typed languages, not is C were the following - * is possible *(ir_type1 *)p = a; *(ir_type2 *)p = b ... - */ - - ptr = get_Store_ptr(store); + ptr = get_Store_ptr(store); /* Check, if the address of this load is used more than once. * If not, this load cannot be removed in any case. */ if (get_irn_out_n(ptr) <= 1) return 0; - block = get_nodes_block(store); - mem = get_Store_mem(store); - value = get_Store_value(store); - mode = get_irn_mode(value); + mem = get_Store_mem(store); /* follow the memory chain as long as there are only Loads */ INC_MASTER(); - for (pred = skip_Proj(mem); pred != store; pred = skip_Proj(get_Load_mem(pred))) { - ldst_info_t *pred_info = get_irn_link(pred); - - if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr && - get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) { - /* - * a Store after a Store in the same block -- a write after write. - * We may remove the first Store, if it does not have an exception handler. - * - * TODO: What, if both have the same exception handler ??? - */ - if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) { - DBG_OPT_WAW(pred, store); - exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) ); - return DF_CHANGED; - } - } - else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr && - value == pred_info->projs[pn_Load_res]) { - /* - * a Store of a value after a Load -- a write after read. - * We may remove the second Store, if it does not have an exception handler. - */ - if (! info->projs[pn_Store_X_except]) { - DBG_OPT_WAR(store, pred); - exchange( info->projs[pn_Store_M], mem ); - return DF_CHANGED; - } - } - - /* follow only Load chains */ - if (get_irn_op(pred) != op_Load) - break; - - /* check for cycles */ - if (NODE_VISITED(pred_info)) - break; - MARK_NODE(pred_info); - } - return res; + return follow_Load_chain_for_Store(store, skip_Proj(mem)); } /** -- 2.20.1