From patchwork Mon Mar 25 10:48:29 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 230614 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 4CAFB2C00A5 for ; Mon, 25 Mar 2013 21:48:59 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=lexyNCH3GQDRNvPvGoMQRQZkl0MI8vuac1YqGP15ZCiW0pmgMELUB huZTojONjlol14WVv9wz8B1JkmcpLYByzGXrT7BnZBppGte+PV4leRiIJ93y2NZu mOZPw2R3DayVh1u7YKHh6wykqlclaCwGYWaOE5DcNRAkOlpejB9r1U= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=ygdtjdQmKh2uuu/KvZf3azcU/Fc=; b=wD7AdoHq4GxbfrcDg5K5 J4pVLaeioNtFNpzxVcbP2OGaKk1VEnkOnUIabvlFiMW3KBQRFD663CnqAlxEiKEa PbINlh+sMt2wvXeOLBEO0ZE47hTxk02q61SGVVh/UCcueoO9E4iSkPQuhTJTBrRs MS1Hl1zf0n6vYknH2x/7rhQ= Received: (qmail 10156 invoked by alias); 25 Mar 2013 10:48:49 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 10101 invoked by uid 89); 25 Mar 2013 10:48:37 -0000 X-Spam-SWARE-Status: No, score=-6.6 required=5.0 tests=AWL, BAYES_00, 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; Mon, 25 Mar 2013 10:48:33 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 9347AA51CB for ; Mon, 25 Mar 2013 11:48:30 +0100 (CET) Date: Mon, 25 Mar 2013 11:48:29 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Rest of LIM TLC Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 This is the rest of my queued LIM TLC (apart from limiting it's dependence checks). Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. Richard. 2013-03-25 Richard Biener * tree-ssa-loop-im.c (struct mem_ref): Use bitmap_head instead of bitmap. (memory_references): Likewise. (outermost_indep_loop, mem_ref_alloc, mark_ref_stored, gather_mem_refs_stmt, record_dep_loop, ref_indep_loop_p_1, ref_indep_loop_p_2, find_refs_for_sm): Adjust. (gather_mem_refs_in_loops): Fold into ... (analyze_memory_references): ... this. Move initialization to tree_ssa_lim_initialize. (fill_always_executed_in): Rename to ... (fill_always_executed_in_1): ... this. (fill_always_executed_in): Move contains_call computation to this new function from ... (tree_ssa_lim_initialize): ... here. (tree_ssa_lim): Call fill_always_executed_in. Index: gcc/tree-ssa-loop-im.c =================================================================== --- gcc/tree-ssa-loop-im.c (revision 197031) +++ gcc/tree-ssa-loop-im.c (working copy) @@ -108,7 +108,7 @@ typedef struct mem_ref query meta-data. */ ao_ref mem; - bitmap stored; /* The set of loops in that this memory location + 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 @@ -117,14 +117,14 @@ typedef struct mem_ref /* The following sets are computed on demand. We keep both set and its complement, so that we know whether the information was already computed or not. */ - bitmap indep_loop; /* The set of loops in that the memory + bitmap_head indep_loop; /* The set of loops in that the memory reference is independent, meaning: If it is stored in the loop, this store is independent on all other loads and stores. If it is only loaded, then it is independent on all stores in the loop. */ - bitmap dep_loop; /* The complement of INDEP_LOOP. */ + bitmap_head dep_loop; /* The complement of INDEP_LOOP. */ } *mem_ref_p; /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first @@ -146,13 +146,13 @@ static struct vec refs_list; /* The set of memory references accessed in each loop. */ - vec refs_in_loop; + vec refs_in_loop; /* The set of memory references stored in each loop. */ - vec refs_stored_in_loop; + vec refs_stored_in_loop; /* The set of memory references stored in each loop, including subloops . */ - vec all_refs_stored_in_loop; + vec all_refs_stored_in_loop; /* Cache for expanding memory addresses. */ struct pointer_map_t *ttae_cache; @@ -584,13 +584,13 @@ outermost_indep_loop (struct loop *outer { struct loop *aloop; - if (bitmap_bit_p (ref->stored, loop->num)) + if (bitmap_bit_p (&ref->stored, loop->num)) return NULL; for (aloop = outer; aloop != loop; aloop = superloop_at_depth (loop, loop_depth (aloop) + 1)) - if (!bitmap_bit_p (ref->stored, aloop->num) + if (!bitmap_bit_p (&ref->stored, aloop->num) && ref_indep_loop_p (aloop, ref)) return aloop; @@ -1457,9 +1457,9 @@ mem_ref_alloc (tree mem, unsigned hash, ao_ref_init (&ref->mem, mem); ref->id = id; ref->hash = hash; - ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack); - ref->indep_loop = BITMAP_ALLOC (&lim_bitmap_obstack); - ref->dep_loop = BITMAP_ALLOC (&lim_bitmap_obstack); + bitmap_initialize (&ref->stored, &lim_bitmap_obstack); + bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack); + bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack); ref->accesses_in_loop.create (0); return ref; @@ -1487,11 +1487,9 @@ record_mem_ref_loc (mem_ref_p ref, struc 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); + 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 @@ -1552,10 +1550,10 @@ gather_mem_refs_stmt (struct loop *loop, record_mem_ref_loc (ref, loop, stmt, mem); } - bitmap_set_bit (memory_accesses.refs_in_loop[loop->num], ref->id); + bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id); if (is_stored) { - bitmap_set_bit (memory_accesses.refs_stored_in_loop[loop->num], ref->id); + bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id); mark_ref_stored (ref, loop); } return; @@ -1580,7 +1578,7 @@ sort_bbs_in_loop_postorder_cmp (const vo /* Gathers memory references in loops. */ static void -gather_mem_refs_in_loops (void) +analyze_memory_references (void) { gimple_stmt_iterator bsi; basic_block bb, *bbs; @@ -1621,8 +1619,8 @@ gather_mem_refs_in_loops (void) FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) { /* Finalize the overall touched references (including subloops). */ - bitmap_ior_into (memory_accesses.all_refs_stored_in_loop[loop->num], - memory_accesses.refs_stored_in_loop[loop->num]); + bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num], + &memory_accesses.refs_stored_in_loop[loop->num]); /* Propagate the information about accessed memory references up the loop hierarchy. */ @@ -1630,42 +1628,9 @@ gather_mem_refs_in_loops (void) if (outer == current_loops->tree_root) continue; - bitmap_ior_into (memory_accesses.all_refs_stored_in_loop[outer->num], - memory_accesses.all_refs_stored_in_loop[loop->num]); - } -} - -/* 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 (100); - /* Allocate a special, unanalyzable mem-ref with ID zero. */ - memory_accesses.refs_list.quick_push - (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID)); - - memory_accesses.refs_in_loop.create (number_of_loops ()); - memory_accesses.refs_stored_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.refs_stored_in_loop.quick_push (empty); - empty = BITMAP_ALLOC (&lim_bitmap_obstack); - memory_accesses.all_refs_stored_in_loop.quick_push (empty); + bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num], + &memory_accesses.all_refs_stored_in_loop[loop->num]); } - - memory_accesses.ttae_cache = NULL; - - gather_mem_refs_in_loops (); } /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in @@ -2231,7 +2196,7 @@ record_dep_loop (struct loop *loop, mem_ /* We can propagate dependent-in-loop bits up the loop hierarchy to all outer loops. */ while (loop != current_loops->tree_root - && bitmap_set_bit (ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p))) + && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p))) loop = loop_outer (loop); } @@ -2247,9 +2212,9 @@ ref_indep_loop_p_1 (struct loop *loop, m mem_ref_p aref; if (stored_p) - refs_to_check = memory_accesses.refs_in_loop[loop->num]; + refs_to_check = &memory_accesses.refs_in_loop[loop->num]; else - refs_to_check = memory_accesses.refs_stored_in_loop[loop->num]; + refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num]; if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID)) return false; @@ -2270,11 +2235,11 @@ ref_indep_loop_p_1 (struct loop *loop, m static bool ref_indep_loop_p_2 (struct loop *loop, mem_ref_p ref, bool stored_p) { - stored_p |= bitmap_bit_p (ref->stored, loop->num); + stored_p |= bitmap_bit_p (&ref->stored, loop->num); - if (bitmap_bit_p (ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))) + if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))) return true; - if (bitmap_bit_p (ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p))) + if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p))) return false; struct loop *inner = loop->inner; @@ -2294,12 +2259,12 @@ ref_indep_loop_p_2 (struct loop *loop, m /* Record the computed result in the cache. */ if (indep_p) { - if (bitmap_set_bit (ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)) + if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)) && stored_p) { /* If it's independend against all refs then it's independent against stores, too. */ - bitmap_set_bit (ref->indep_loop, LOOP_DEP_BIT (loop->num, false)); + bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false)); } } else @@ -2373,7 +2338,7 @@ can_sm_ref_p (struct loop *loop, mem_ref static void find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm) { - bitmap refs = memory_accesses.all_refs_stored_in_loop[loop->num]; + bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num]; unsigned i; bitmap_iterator bi; mem_ref_p ref; @@ -2451,7 +2416,7 @@ store_motion (void) blocks that contain a nonpure call. */ static void -fill_always_executed_in (struct loop *loop, sbitmap contains_call) +fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call) { basic_block bb = NULL, *bbs, last = NULL; unsigned i; @@ -2510,45 +2475,80 @@ fill_always_executed_in (struct loop *lo } for (loop = loop->inner; loop; loop = loop->next) - fill_always_executed_in (loop, contains_call); + fill_always_executed_in_1 (loop, contains_call); } -/* Compute the global information needed by the loop invariant motion pass. */ +/* 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 -tree_ssa_lim_initialize (void) +fill_always_executed_in (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); + struct loop *loop; bitmap_clear (contains_call); FOR_EACH_BB (bb) { - for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - if (nonpure_call_p (gsi_stmt (bsi))) + if (nonpure_call_p (gsi_stmt (gsi))) break; } - if (!gsi_end_p (bsi)) + 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 (loop, contains_call); + 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 (); if (flag_tm) 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); + /* Allocate a special, unanalyzable mem-ref with ID zero. */ + memory_accesses.refs_list.quick_push + (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID)); + + memory_accesses.refs_in_loop.create (number_of_loops ()); + memory_accesses.refs_in_loop.quick_grow (number_of_loops ()); + memory_accesses.refs_stored_in_loop.create (number_of_loops ()); + memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops ()); + memory_accesses.all_refs_stored_in_loop.create (number_of_loops ()); + memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops ()); + + for (i = 0; i < number_of_loops (); i++) + { + bitmap_initialize (&memory_accesses.refs_in_loop[i], + &lim_bitmap_obstack); + bitmap_initialize (&memory_accesses.refs_stored_in_loop[i], + &lim_bitmap_obstack); + bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i], + &lim_bitmap_obstack); + } + + memory_accesses.ttae_cache = NULL; } /* Cleans up after the invariant motion pass. */ @@ -2595,6 +2595,9 @@ tree_ssa_lim (void) /* 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 ();