From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12927 invoked by alias); 28 Mar 2013 15:15:16 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 12711 invoked by uid 89); 28 Mar 2013 15:15:09 -0000 X-Spam-SWARE-Status: No, score=-6.1 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,RCVD_IN_DNSWL_HI,RP_MATCHES_RCVD,TW_TM autolearn=ham version=3.3.1 Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Thu, 28 Mar 2013 15:15:06 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id C0648A524D for ; Thu, 28 Mar 2013 16:15:03 +0100 (CET) Date: Thu, 28 Mar 2013 15:15:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix PR56756 Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2013-03/txt/msg01216.txt.bz2 The domwalker fix to order dom children after inverted postorder exposed the latent issue that LIM relies on domwalk to walk all blocks defining SSA names before all blocks using them ... which is what the following patch tries to fix using the dependency information it already tracks (but incompletely so, thus the fixes). Bootstrapped and tested on x86_64-unknown-linux-gnu. I'm not entirely happy with this - it should use a worklist of stmts instead of recursing and handling basic-blocks. But well ... Leaving for comments. (inverted_post_order_compute visits loop nodes in "weird" order because it visits loop exit nodes last) Richard. 2013-03-28 Richard Biener PR tree-optimization/56756 * tree-ssa-loop-im.c (outermost_invariant_loop): More properly handle not yet processed def stmts. (add_dependency): Simplify. (move_computations_stmt): Rename to ... (move_computations_bb): ... this. Process blocks with dependencies recursively. (move_computations): Instead of a dominator walk process basic-blocks in order determined by dependences of stmts we want to hoist. (force_move_till_op): Add dependencies. (struct fmt_data): Add dependence storage. (execute_sm): Adjust. * gcc.dg/torture/pr56756.c: New testcase. Index: gcc/tree-ssa-loop-im.c =================================================================== --- gcc/tree-ssa-loop-im.c (revision 197188) +++ gcc/tree-ssa-loop-im.c (working copy) @@ -417,7 +418,7 @@ outermost_invariant_loop (tree def, stru { gimple def_stmt; basic_block def_bb; - struct loop *max_loop; + struct loop *def_loop; struct lim_aux_data *lim_data; if (!def) @@ -434,17 +435,22 @@ outermost_invariant_loop (tree def, stru if (!def_bb) return superloop_at_depth (loop, 1); - max_loop = find_common_loop (loop, def_bb->loop_father); - + def_loop = def_bb->loop_father; lim_data = get_lim_data (def_stmt); - if (lim_data != NULL && lim_data->max_loop != NULL) - max_loop = find_common_loop (max_loop, - loop_outer (lim_data->max_loop)); - if (max_loop == loop) - return NULL; - max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1); + if (lim_data == NULL + || lim_data->max_loop == NULL) + { + if (def_loop == loop) + return NULL; + if (!flow_loop_nested_p (def_loop, loop)) + return NULL; + return superloop_at_depth (loop, loop_depth (def_loop) + 1); + } - return max_loop; + if (lim_data->max_loop != loop + && !flow_loop_nested_p (lim_data->max_loop, loop)) + return NULL; + return lim_data->max_loop; } /* DATA is a structure containing information associated with a statement @@ -466,7 +472,6 @@ add_dependency (tree def, struct lim_aux gimple def_stmt = SSA_NAME_DEF_STMT (def); basic_block def_bb = gimple_bb (def_stmt); struct loop *max_loop; - struct lim_aux_data *def_data; if (!def_bb) return true; @@ -478,17 +483,13 @@ add_dependency (tree def, struct lim_aux if (flow_loop_nested_p (data->max_loop, max_loop)) data->max_loop = max_loop; - def_data = get_lim_data (def_stmt); - if (!def_data) - return true; - if (add_cost /* Only add the cost if the statement defining DEF is inside LOOP, i.e. if it is likely that by moving the invariants dependent on it, we will be able to avoid creating a new register for it (since it will be only used in these dependent invariants). */ && def_bb->loop_father == loop) - data->cost += def_data->cost; + data->cost += get_lim_data (def_stmt)->cost; data->depends.safe_push (def_stmt); @@ -1174,18 +1175,20 @@ determine_invariantness (void) data stored in LIM_DATA structures associated with each statement. Callback for walk_dominator_tree. */ -static void -move_computations_stmt (struct dom_walk_data *dw_data, - basic_block bb) +static unsigned +move_computations_bb (basic_block bb, sbitmap visited) { struct loop *level; gimple_stmt_iterator bsi; gimple stmt; unsigned cost = 0; struct lim_aux_data *lim_data; + unsigned todo = 0; + unsigned i; + gimple dep_stmt; if (!loop_outer (bb->loop_father)) - return; + return 0; for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); ) { @@ -1201,14 +1204,25 @@ move_computations_stmt (struct dom_walk_ cost = lim_data->cost; level = lim_data->tgt_loop; - clear_lim_data (stmt); if (!level) { + clear_lim_data (stmt); gsi_next (&bsi); continue; } + /* Make sure to process blocks with stmts we depend on first. */ + FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt) + if (gimple_bb (dep_stmt) + && !bitmap_bit_p (visited, gimple_bb (dep_stmt)->index)) + { + bitmap_set_bit (visited, gimple_bb (dep_stmt)->index); + todo |= move_computations_bb (gimple_bb (dep_stmt), visited); + } + + clear_lim_data (stmt); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Moving PHI node\n"); @@ -1240,7 +1254,7 @@ move_computations_stmt (struct dom_walk_ gimple_phi_result (stmt), t, arg0, arg1); SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt; - *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg; + todo |= TODO_cleanup_cfg; } gsi_insert_on_edge (loop_preheader_edge (level), new_stmt); remove_phi_node (&bsi, false); @@ -1261,14 +1275,25 @@ move_computations_stmt (struct dom_walk_ cost = lim_data->cost; level = lim_data->tgt_loop; - clear_lim_data (stmt); if (!level) { + clear_lim_data (stmt); gsi_next (&bsi); continue; } + /* Make sure to process blocks with stmts we depend on first. */ + FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt) + if (gimple_bb (dep_stmt) + && !bitmap_bit_p (visited, gimple_bb (dep_stmt)->index)) + { + bitmap_set_bit (visited, gimple_bb (dep_stmt)->index); + todo |= move_computations_bb (gimple_bb (dep_stmt), visited); + } + + clear_lim_data (stmt); + /* We do not really want to move conditionals out of the loop; we just placed it here to force its operands to be moved if necessary. */ if (gimple_code (stmt) == GIMPLE_COND) @@ -1303,6 +1328,8 @@ move_computations_stmt (struct dom_walk_ gsi_remove (&bsi, false); gsi_insert_on_edge (e, stmt); } + + return todo; } /* Hoist the statements out of the loops prescribed by data stored in @@ -1311,17 +1338,19 @@ move_computations_stmt (struct dom_walk_ static unsigned int move_computations (void) { - struct dom_walk_data walk_data; - unsigned int todo = 0; + basic_block bb; + unsigned todo = 0; + sbitmap visited = sbitmap_alloc (last_basic_block); + bitmap_clear (visited); - memset (&walk_data, 0, sizeof (struct dom_walk_data)); - walk_data.global_data = &todo; - walk_data.dom_direction = CDI_DOMINATORS; - walk_data.before_dom_children = move_computations_stmt; + FOR_EACH_BB (bb) + if (!bitmap_bit_p (visited, bb->index)) + { + bitmap_set_bit (visited, bb->index); + todo |= move_computations_bb (bb, visited); + } - init_walk_dominator_tree (&walk_data); - walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); - fini_walk_dominator_tree (&walk_data); + sbitmap_free (visited); gsi_commit_edge_inserts (); if (need_ssa_update_p (cfun)) @@ -1365,7 +1394,8 @@ may_move_till (tree ref, tree *index, vo moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */ static void -force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop) +force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop, + struct lim_aux_data *lim_data) { gimple stmt; @@ -1380,6 +1410,7 @@ force_move_till_op (tree op, struct loop return; set_level (stmt, orig_loop, loop); + lim_data->depends.safe_push (stmt); } /* Forces statement defining invariants in REF (and *INDEX) to be moved out of @@ -1390,6 +1421,7 @@ struct fmt_data { struct loop *loop; struct loop *orig_loop; + struct lim_aux_data *lim_data; }; static bool @@ -1402,11 +1434,14 @@ force_move_till (tree ref, tree *index, tree step = TREE_OPERAND (ref, 3); tree lbound = TREE_OPERAND (ref, 2); - force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop); - force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop); + force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop, + fmt_data->lim_data); + force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop, + fmt_data->lim_data); } - force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop); + force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop, + fmt_data->lim_data); return true; } @@ -2036,10 +2071,6 @@ execute_sm (struct loop *loop, vec tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref), get_lsm_tmp_name (ref->mem.ref, ~0)); - fmt_data.loop = loop; - fmt_data.orig_loop = loop; - for_each_index (&ref->mem.ref, force_move_till, &fmt_data); - if (block_in_transaction (loop_preheader_edge (loop)->src) || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES)) multi_threaded_model_p = true; @@ -2062,6 +2093,11 @@ execute_sm (struct loop *loop, vec lim_data->tgt_loop = loop; gsi_insert_on_edge (latch_edge, load); + fmt_data.loop = loop; + fmt_data.orig_loop = loop; + fmt_data.lim_data = lim_data; + for_each_index (&ref->mem.ref, force_move_till, &fmt_data); + if (multi_threaded_model_p) { load = gimple_build_assign (store_flag, boolean_false_node); Index: gcc/testsuite/gcc.dg/torture/pr56756.c =================================================================== --- gcc/testsuite/gcc.dg/torture/pr56756.c (revision 0) +++ gcc/testsuite/gcc.dg/torture/pr56756.c (working copy) @@ -0,0 +1,28 @@ +/* { dg-do compile } */ + +int a, *b; + +void f(void) +{ + if(a) + { + int k; + + for(a = 0; a < 1; a++) + { + int **q; + f(); + + for(; **q; ++**q) + lbl: + if(a) + { + a = 0; + goto lbl; + } + + b = &k; + } + } + goto lbl; +}