From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29809 invoked by alias); 12 Mar 2013 08:38:32 -0000 Received: (qmail 29495 invoked by uid 22791); 12 Mar 2013 08:38:28 -0000 X-SWARE-Spam-Status: No, hits=-7.5 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,KHOP_THREADED,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; Tue, 12 Mar 2013 08:38:21 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 8A30BA3A4A for ; Tue, 12 Mar 2013 09:38:19 +0100 (CET) Date: Tue, 12 Mar 2013 08:38:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: Re: [PATCH][1/n] tree LIM TLC In-Reply-To: Message-ID: References: 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/msg00426.txt.bz2 On Mon, 11 Mar 2013, Richard Biener wrote: > > This is a series of patches applying some TLC to LIM. This first > patch gets rid of the remains of create_vop_ref_mapping and > alongside cleans up how we record references. Actually I rolled in some more changes into this patch, bootstrapped and tested on x86_64-unknown-linux-gnu, queued for 4.9. Richard. 2013-03-11 Richard Biener * tree-ssa-loop-im.c (record_mem_ref_loc): Record ref as stored here. (gather_mem_refs_stmt): Instead of here and in create_vop_ref_mapping_loop. (gather_mem_refs_in_loops): Fold into ... (analyze_memory_references): ... this. Move data structure init to tree_ssa_lim_initialize. Propagate stored refs info as well. (create_vop_ref_mapping_loop): Remove. (create_vop_ref_mapping): Likewise. (tree_ssa_lim_initialize): Initialize ref bitmaps here. Split always-executed computation into ... (fill_always_executed_in): ... this. Rename original to ... (fill_always_executed_in_1): ... this. (tree_ssa_lim): Call fill_always_executed_in here. Index: trunk/gcc/tree-ssa-loop-im.c =================================================================== *** trunk.orig/gcc/tree-ssa-loop-im.c 2013-03-11 12:38:43.000000000 +0100 --- trunk/gcc/tree-ssa-loop-im.c 2013-03-11 14:12:00.143773587 +0100 *************** mem_ref_locs_alloc (void) *** 1518,1528 **** description REF. The reference occurs in statement STMT. */ 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); mem_ref_locs_p accs; - bitmap ril = memory_accesses.refs_in_loop[loop->num]; if (ref->accesses_in_loop.length () <= (unsigned) loop->num) --- 1518,1528 ---- description REF. The reference occurs in statement STMT. */ static void ! record_mem_ref_loc (mem_ref_p ref, bool is_stored, ! struct loop *loop, gimple stmt, tree *loc) { mem_ref_loc_p aref = XNEW (struct mem_ref_loc); mem_ref_locs_p accs; if (ref->accesses_in_loop.length () <= (unsigned) loop->num) *************** record_mem_ref_loc (mem_ref_p ref, struc *** 1536,1556 **** aref->stmt = stmt; aref->ref = loc; - accs->locs.safe_push (aref); - bitmap_set_bit (ril, ref->id); - } - - /* Marks reference REF as stored in LOOP. */ ! static void ! mark_ref_stored (mem_ref_p ref, struct loop *loop) ! { ! for (; ! loop != current_loops->tree_root ! && !bitmap_bit_p (ref->stored, loop->num); ! loop = loop_outer (loop)) ! bitmap_set_bit (ref->stored, loop->num); } /* Gathers memory references in statement STMT in LOOP, storing the --- 1536,1552 ---- aref->stmt = stmt; aref->ref = loc; accs->locs.safe_push (aref); ! bitmap_set_bit (memory_accesses.refs_in_loop[loop->num], ref->id); ! if (is_stored) ! { ! bitmap_set_bit (memory_accesses.all_refs_stored_in_loop[loop->num], ! ref->id); ! while (loop != current_loops->tree_root ! && bitmap_set_bit (ref->stored, loop->num)) ! loop = loop_outer (loop); ! } } /* Gathers memory references in statement STMT in LOOP, storing the *************** gather_mem_refs_stmt (struct loop *loop, *** 1582,1590 **** fprintf (dump_file, "Unanalyzed memory reference %u: ", id); print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } ! if (gimple_vdef (stmt)) ! mark_ref_stored (ref, loop); ! record_mem_ref_loc (ref, loop, stmt, mem); return; } --- 1578,1584 ---- fprintf (dump_file, "Unanalyzed memory reference %u: ", id); print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } ! record_mem_ref_loc (ref, gimple_vdef (stmt), loop, stmt, mem); return; } *************** gather_mem_refs_stmt (struct loop *loop, *** 1611,1627 **** } } ! if (is_stored) ! mark_ref_stored (ref, loop); ! ! record_mem_ref_loc (ref, loop, stmt, mem); return; } /* Gathers memory references in loops. */ static void ! gather_mem_refs_in_loops (void) { gimple_stmt_iterator bsi; basic_block bb; --- 1605,1618 ---- } } ! record_mem_ref_loc (ref, is_stored, loop, stmt, mem); return; } /* Gathers memory references in loops. */ static void ! analyze_memory_references (void) { gimple_stmt_iterator bsi; basic_block bb; *************** gather_mem_refs_in_loops (void) *** 1647,1731 **** alrefs = memory_accesses.all_refs_in_loop[loop->num]; bitmap_ior_into (alrefs, lrefs); ! if (loop_outer (loop) == current_loops->tree_root) continue; ! alrefso = memory_accesses.all_refs_in_loop[loop_outer (loop)->num]; bitmap_ior_into (alrefso, alrefs); } } - /* Create a mapping from virtual operands to references that touch them - in LOOP. */ - - static void - create_vop_ref_mapping_loop (struct loop *loop) - { - bitmap refs = memory_accesses.refs_in_loop[loop->num]; - struct loop *sloop; - bitmap_iterator bi; - unsigned i; - mem_ref_p ref; - - EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi) - { - ref = memory_accesses.refs_list[i]; - for (sloop = loop; sloop != current_loops->tree_root; - sloop = loop_outer (sloop)) - if (bitmap_bit_p (ref->stored, loop->num)) - { - bitmap refs_stored - = memory_accesses.all_refs_stored_in_loop[sloop->num]; - bitmap_set_bit (refs_stored, ref->id); - } - } - } - - /* For each non-clobbered virtual operand and each loop, record the memory - references in this loop that touch the operand. */ - - static void - create_vop_ref_mapping (void) - { - loop_iterator li; - struct loop *loop; - - FOR_EACH_LOOP (li, loop, 0) - { - create_vop_ref_mapping_loop (loop); - } - } - - /* Gathers information about memory accesses in the loops. */ - - static void - analyze_memory_references (void) - { - unsigned i; - bitmap empty; - - memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL); - memory_accesses.refs_list.create (0); - memory_accesses.refs_in_loop.create (number_of_loops ()); - memory_accesses.all_refs_in_loop.create (number_of_loops ()); - memory_accesses.all_refs_stored_in_loop.create (number_of_loops ()); - - for (i = 0; i < number_of_loops (); i++) - { - empty = BITMAP_ALLOC (&lim_bitmap_obstack); - memory_accesses.refs_in_loop.quick_push (empty); - empty = BITMAP_ALLOC (&lim_bitmap_obstack); - memory_accesses.all_refs_in_loop.quick_push (empty); - empty = BITMAP_ALLOC (&lim_bitmap_obstack); - memory_accesses.all_refs_stored_in_loop.quick_push (empty); - } - - memory_accesses.ttae_cache = NULL; - - gather_mem_refs_in_loops (); - create_vop_ref_mapping (); - } - /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in tree_to_aff_combination_expand. */ --- 1638,1654 ---- alrefs = memory_accesses.all_refs_in_loop[loop->num]; bitmap_ior_into (alrefs, lrefs); ! struct loop *outer = loop_outer (loop); ! if (outer == current_loops->tree_root) continue; ! alrefso = memory_accesses.all_refs_in_loop[outer->num]; bitmap_ior_into (alrefso, alrefs); + bitmap_ior_into (memory_accesses.all_refs_stored_in_loop[outer->num], + memory_accesses.all_refs_stored_in_loop[loop->num]); } } /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in tree_to_aff_combination_expand. */ *************** store_motion (void) *** 2483,2489 **** blocks that contain a nonpure call. */ static void ! fill_always_executed_in (struct loop *loop, sbitmap contains_call) { basic_block bb = NULL, *bbs, last = NULL; unsigned i; --- 2406,2412 ---- blocks that contain a nonpure call. */ static void ! fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call) { basic_block bb = NULL, *bbs, last = NULL; unsigned i; *************** fill_always_executed_in (struct loop *lo *** 2542,2579 **** } for (loop = loop->inner; loop; loop = loop->next) ! fill_always_executed_in (loop, contains_call); } ! /* Compute the global information needed by the loop invariant motion pass. */ static void ! tree_ssa_lim_initialize (void) { sbitmap contains_call = sbitmap_alloc (last_basic_block); - gimple_stmt_iterator bsi; - struct loop *loop; basic_block bb; ! ! bitmap_obstack_initialize (&lim_bitmap_obstack); bitmap_clear (contains_call); FOR_EACH_BB (bb) { ! for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { ! if (nonpure_call_p (gsi_stmt (bsi))) break; } ! if (!gsi_end_p (bsi)) bitmap_set_bit (contains_call, bb->index); } for (loop = current_loops->tree_root->inner; loop; loop = loop->next) ! fill_always_executed_in (loop, contains_call); sbitmap_free (contains_call); lim_aux_data_map = pointer_map_create (); --- 2465,2513 ---- } for (loop = loop->inner; loop; loop = loop->next) ! fill_always_executed_in_1 (loop, contains_call); } ! /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e. ! for each such basic block bb records the outermost loop for that execution ! of its header implies execution of bb. */ static void ! fill_always_executed_in (void) { sbitmap contains_call = sbitmap_alloc (last_basic_block); basic_block bb; ! struct loop *loop; bitmap_clear (contains_call); FOR_EACH_BB (bb) { ! gimple_stmt_iterator gsi; ! for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { ! if (nonpure_call_p (gsi_stmt (gsi))) break; } ! if (!gsi_end_p (gsi)) bitmap_set_bit (contains_call, bb->index); } for (loop = current_loops->tree_root->inner; loop; loop = loop->next) ! fill_always_executed_in_1 (loop, contains_call); sbitmap_free (contains_call); + } + + + /* Compute the global information needed by the loop invariant motion pass. */ + + static void + tree_ssa_lim_initialize (void) + { + unsigned i; + + bitmap_obstack_initialize (&lim_bitmap_obstack); lim_aux_data_map = pointer_map_create (); *************** tree_ssa_lim_initialize (void) *** 2581,2586 **** --- 2515,2538 ---- compute_transaction_bits (); alloc_aux_for_edges (0); + + memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL); + memory_accesses.refs_list.create (100); + memory_accesses.refs_in_loop.create (number_of_loops ()); + memory_accesses.all_refs_in_loop.create (number_of_loops ()); + memory_accesses.all_refs_stored_in_loop.create (number_of_loops ()); + + for (i = 0; i < number_of_loops (); i++) + { + bitmap empty = BITMAP_ALLOC (&lim_bitmap_obstack); + memory_accesses.refs_in_loop.quick_push (empty); + empty = BITMAP_ALLOC (&lim_bitmap_obstack); + memory_accesses.all_refs_in_loop.quick_push (empty); + empty = BITMAP_ALLOC (&lim_bitmap_obstack); + memory_accesses.all_refs_stored_in_loop.quick_push (empty); + } + + memory_accesses.ttae_cache = NULL; } /* Cleans up after the invariant motion pass. */ *************** tree_ssa_lim (void) *** 2627,2632 **** --- 2579,2587 ---- /* Gathers information about memory accesses in the loops. */ analyze_memory_references (); + /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */ + fill_always_executed_in (); + /* For each statement determine the outermost loop in that it is invariant and cost for computing the invariant. */ determine_invariantness ();