From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10286 invoked by alias); 13 Mar 2013 13:43:52 -0000 Received: (qmail 10095 invoked by uid 22791); 13 Mar 2013 13:43:50 -0000 X-SWARE-Spam-Status: No, hits=-6.6 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,RCVD_IN_DNSWL_HI,RP_MATCHES_RCVD,TW_TM X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 13 Mar 2013 13:43:38 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id A3B79A51B7 for ; Wed, 13 Mar 2013 14:43:36 +0100 (CET) Date: Wed, 13 Mar 2013 13:43:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][8/n] tree LIM TLC Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 X-SW-Source: 2013-03/txt/msg00461.txt.bz2 This changes the vector of locations we track for each memory reference from storing a pointer to a location aggregate to storing the aggregate directly, avoiding an indirection and tons of small memory allocations. This also touches the way we iterate over locations of refs - instead of building up a vector of all refs and then iterating over it and then freeing it the following implements a proper iterator using a functor template (and allows an early exit from ref_always_accessed_p). Bootstrap and regtest pending on x86_64-unknown-linux-gnu. Richard. 2013-03-13 Richard Biener * tree-ssa-loop-im.c (struct mem_ref): Make accesses_in_loop a vec of a vec of the aggregate mem_ref_loc. (memref_free): Adjust. (record_mem_ref_loc): Likewise. (get_all_locs_in_loop): Rewrite into ... (for_all_locs_in_loop): ... this iterator. (rewrite_mem_ref_loc): New functor. (rewrite_mem_refs): Use for_all_locs_in_loop. (sm_set_flag_if_changed): New functor. (execute_sm_if_changed_flag_set): Use for_all_locs_in_loop. (ref_always_accessed): New functor. (ref_always_accessed_p): Use for_all_locs_in_loop. Index: trunk/gcc/tree-ssa-loop-im.c =================================================================== *** trunk.orig/gcc/tree-ssa-loop-im.c 2013-03-13 14:15:32.000000000 +0100 --- trunk/gcc/tree-ssa-loop-im.c 2013-03-13 14:19:17.016903594 +0100 *************** typedef struct mem_ref *** 115,121 **** hashval_t hash; /* Its hash value. */ bitmap_head stored; /* The set of loops in that this memory location is stored to. */ ! vec > accesses_in_loop; /* The locations of the accesses. Vector indexed by the loop number. */ --- 115,121 ---- hashval_t hash; /* Its hash value. */ bitmap_head stored; /* The set of loops in that this memory location is stored to. */ ! vec > accesses_in_loop; /* The locations of the accesses. Vector indexed by the loop number. */ *************** memref_eq (const void *obj1, const void *** 1435,1450 **** static void memref_free (struct mem_ref *mem) { ! unsigned i, j; ! vec *accs; ! mem_ref_loc_p loc; FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs) ! { ! FOR_EACH_VEC_ELT (*accs, j, loc) ! free (loc); ! accs->release (); ! } mem->accesses_in_loop.release (); free (mem); --- 1435,1445 ---- static void memref_free (struct mem_ref *mem) { ! unsigned i; ! vec *accs; FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs) ! accs->release (); mem->accesses_in_loop.release (); free (mem); *************** mem_ref_alloc (tree mem, unsigned hash, *** 1474,1487 **** static void record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc) { ! mem_ref_loc_p aref = XNEW (struct mem_ref_loc); if (ref->accesses_in_loop.length () <= (unsigned) loop->num) ref->accesses_in_loop.safe_grow_cleared (loop->num + 1); ! aref->stmt = stmt; ! aref->ref = loc; ref->accesses_in_loop[loop->num].safe_push (aref); } --- 1469,1482 ---- static void record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc) { ! mem_ref_loc aref; if (ref->accesses_in_loop.length () <= (unsigned) loop->num) ref->accesses_in_loop.safe_grow_cleared (loop->num + 1); ! aref.stmt = stmt; ! aref.ref = loc; ref->accesses_in_loop[loop->num].safe_push (aref); } *************** mem_refs_may_alias_p (tree mem1, tree me *** 1628,1647 **** return true; } ! /* Rewrites location LOC by TMP_VAR. */ ! ! static void ! rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var) ! { ! *loc->ref = tmp_var; ! update_stmt (loc->stmt); ! } ! ! /* Adds all locations of REF in LOOP and its subloops to LOCS. */ ! static void ! get_all_locs_in_loop (struct loop *loop, mem_ref_p ref, ! vec *locs) { unsigned i; mem_ref_loc_p loc; --- 1623,1636 ---- return true; } ! /* Iterates over all locations of REF in LOOP and its subloops calling ! fn.operator() with the location as argument. When that operator ! returns true the iteration is stopped and true is returned. ! Otherwise false is returned. */ ! template ! static bool ! for_all_locs_in_loop (struct loop *loop, mem_ref_p ref, FN fn) { unsigned i; mem_ref_loc_p loc; *************** get_all_locs_in_loop (struct loop *loop, *** 1649,1665 **** struct loop *subloop; if (!bitmap_bit_p (refs, ref->id)) ! return; ! if (ref->accesses_in_loop.length () ! > (unsigned) loop->num) ! { ! FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc) ! locs->safe_push (loc); ! } for (subloop = loop->inner; subloop != NULL; subloop = subloop->next) ! get_all_locs_in_loop (subloop, ref, locs); } /* Rewrites all references to REF in LOOP by variable TMP_VAR. */ --- 1638,1672 ---- struct loop *subloop; if (!bitmap_bit_p (refs, ref->id)) ! return false; ! if (ref->accesses_in_loop.length () > (unsigned) loop->num) ! FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc) ! if (fn (loc)) ! return true; for (subloop = loop->inner; subloop != NULL; subloop = subloop->next) ! if (for_all_locs_in_loop (subloop, ref, fn)) ! return true; ! ! return false; ! } ! ! /* Rewrites location LOC by TMP_VAR. */ ! ! struct rewrite_mem_ref_loc ! { ! rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {} ! bool operator()(mem_ref_loc_p loc); ! tree tmp_var; ! }; ! ! bool ! rewrite_mem_ref_loc::operator()(mem_ref_loc_p loc) ! { ! *loc->ref = tmp_var; ! update_stmt (loc->stmt); ! return false; } /* Rewrites all references to REF in LOOP by variable TMP_VAR. */ *************** get_all_locs_in_loop (struct loop *loop, *** 1667,1680 **** static void rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var) { ! unsigned i; ! mem_ref_loc_p loc; ! vec locs = vNULL; ! ! get_all_locs_in_loop (loop, ref, &locs); ! FOR_EACH_VEC_ELT (locs, i, loc) ! rewrite_mem_ref_loc (loc, tmp_var); ! locs.release (); } /* The name and the length of the currently generated variable --- 1674,1680 ---- static void rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var) { ! for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var)); } /* The name and the length of the currently generated variable *************** execute_sm_if_changed (edge ex, tree mem *** 1932,1967 **** EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU; } /* Helper function for execute_sm. On every location where REF is set, set an appropriate flag indicating the store. */ static tree execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref) { - unsigned i; - mem_ref_loc_p loc; tree flag; - vec locs = vNULL; char *str = get_lsm_tmp_name (ref->mem, ~0); - lsm_tmp_name_add ("_flag"); flag = create_tmp_reg (boolean_type_node, str); ! get_all_locs_in_loop (loop, ref, &locs); ! FOR_EACH_VEC_ELT (locs, i, loc) ! { ! gimple_stmt_iterator gsi; ! gimple stmt; ! ! /* Only set the flag for writes. */ ! if (is_gimple_assign (loc->stmt) ! && gimple_assign_lhs_ptr (loc->stmt) == loc->ref) ! { ! gsi = gsi_for_stmt (loc->stmt); ! stmt = gimple_build_assign (flag, boolean_true_node); ! gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING); ! } ! } ! locs.release (); return flag; } --- 1932,1971 ---- EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU; } + /* When REF is set on the location, set flag indicating the store. */ + + struct sm_set_flag_if_changed + { + sm_set_flag_if_changed (tree flag_) : flag (flag_) {} + bool operator()(mem_ref_loc_p loc); + tree flag; + }; + + bool + sm_set_flag_if_changed::operator()(mem_ref_loc_p loc) + { + /* Only set the flag for writes. */ + if (is_gimple_assign (loc->stmt) + && gimple_assign_lhs_ptr (loc->stmt) == loc->ref) + { + gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt); + gimple stmt = gimple_build_assign (flag, boolean_true_node); + gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING); + } + return false; + } + /* Helper function for execute_sm. On every location where REF is set, set an appropriate flag indicating the store. */ static tree execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref) { tree flag; char *str = get_lsm_tmp_name (ref->mem, ~0); lsm_tmp_name_add ("_flag"); flag = create_tmp_reg (boolean_type_node, str); ! for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag)); return flag; } *************** hoist_memory_references (struct loop *lo *** 2056,2116 **** } } ! /* Returns true if REF is always accessed in LOOP. If STORED_P is true ! make sure REF is always stored to in LOOP. */ ! static bool ! ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p) { - vec locs = vNULL; - unsigned i; - mem_ref_loc_p loc; - bool ret = false; struct loop *must_exec; - tree base; ! base = get_base_address (ref->mem); ! if (INDIRECT_REF_P (base) ! || TREE_CODE (base) == MEM_REF) ! base = TREE_OPERAND (base, 0); ! get_all_locs_in_loop (loop, ref, &locs); ! FOR_EACH_VEC_ELT (locs, i, loc) { ! if (!get_lim_data (loc->stmt)) ! continue; ! /* If we require an always executed store make sure the statement ! stores to the reference. */ ! if (stored_p) ! { ! tree lhs; ! if (!gimple_get_lhs (loc->stmt)) ! continue; ! lhs = get_base_address (gimple_get_lhs (loc->stmt)); ! if (!lhs) ! continue; ! if (INDIRECT_REF_P (lhs) ! || TREE_CODE (lhs) == MEM_REF) ! lhs = TREE_OPERAND (lhs, 0); ! if (lhs != base) ! continue; ! } ! must_exec = get_lim_data (loc->stmt)->always_executed_in; ! if (!must_exec) ! continue; ! if (must_exec == loop ! || flow_loop_nested_p (must_exec, loop)) ! { ! ret = true; ! break; ! } ! } ! locs.release (); ! return ret; } /* Returns true if REF1 and REF2 are independent. */ --- 2060,2123 ---- } } ! struct ref_always_accessed ! { ! ref_always_accessed (struct loop *loop_, tree base_, bool stored_p_) ! : loop (loop_), base (base_), stored_p (stored_p_) {} ! bool operator()(mem_ref_loc_p loc); ! struct loop *loop; ! tree base; ! bool stored_p; ! }; ! bool ! ref_always_accessed::operator()(mem_ref_loc_p loc) { struct loop *must_exec; ! if (!get_lim_data (loc->stmt)) ! return false; ! /* If we require an always executed store make sure the statement ! stores to the reference. */ ! if (stored_p) { ! tree lhs; ! if (!gimple_get_lhs (loc->stmt)) ! return false; ! lhs = get_base_address (gimple_get_lhs (loc->stmt)); ! if (!lhs) ! return false; ! if (INDIRECT_REF_P (lhs) ! || TREE_CODE (lhs) == MEM_REF) ! lhs = TREE_OPERAND (lhs, 0); ! if (lhs != base) ! return false; ! } ! must_exec = get_lim_data (loc->stmt)->always_executed_in; ! if (!must_exec) ! return false; ! if (must_exec == loop ! || flow_loop_nested_p (must_exec, loop)) ! return true; ! return false; ! } ! /* Returns true if REF is always accessed in LOOP. If STORED_P is true ! make sure REF is always stored to in LOOP. */ ! ! static bool ! ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p) ! { ! tree base = get_base_address (ref->mem); ! if (TREE_CODE (base) == MEM_REF) ! base = TREE_OPERAND (base, 0); ! ! return for_all_locs_in_loop (loop, ref, ! ref_always_accessed (loop, base, stored_p)); } /* Returns true if REF1 and REF2 are independent. */