From patchwork Mon Nov 9 09:02:20 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 541659 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 960DD1402C6 for ; Mon, 9 Nov 2015 20:02:33 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=ZcIHAMRx; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=FHnlosvTpPi+I2wa3MUqW5QoHZ+R+nr/AeUAJ2fsmcNJDFU+R0 J3+1JqT8p9SC6x/IY9d2w54spNIQb25kNOG5Jg0lJ5s6ctzA9VcesDAwLxe6LBow Q8NHPHHVhOPRzlVHOqgCLy1oMGQQ6/xhIHexxIVJAz5UAWjhVSf2poN0E= 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:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=B71qe3o5iMbEh/+gVvky4wFY3Fg=; b=ZcIHAMRxK0e7Ji/Kqu2k cAJi87+whC5DdbhJmnnZC+kKsRzPeVgo0G1VRbaNdihrftS7ftFK/B506SSyP3fs GnSWSgQh+w8JqGlELdVeTDflCqSBAVk+G+7sEkfO4xpbC9m6RYyGf0DEsSi/IZna zIlDrkGTpgAFu4v87jGsMrk= Received: (qmail 117498 invoked by alias); 9 Nov 2015 09:02:25 -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 117475 invoked by uid 89); 9 Nov 2015 09:02:24 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Mon, 09 Nov 2015 09:02:22 +0000 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by mx1.redhat.com (Postfix) with ESMTPS id E46E2C0032F8 for ; Mon, 9 Nov 2015 09:02:20 +0000 (UTC) Received: from localhost.localdomain (ovpn-113-107.phx2.redhat.com [10.3.113.107]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA992KVM010273 for ; Mon, 9 Nov 2015 04:02:20 -0500 To: gcc-patches From: Jeff Law Subject: [PATCH] Minor refactoring in tree-ssanames.c & freelists verifier Message-ID: <5640611C.5090309@redhat.com> Date: Mon, 9 Nov 2015 02:02:20 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 X-IsSubscribed: yes This is a piece of a larger refactoring. I'm postponing the larger refactoring until next stage1 -- I have some concerns about the compile-time impact that I'll need to measure. In the mean time I want to get knowledge of the freelists out of pass_release_ssa_names::execute. The larger refactoring will move the freelists into a class and pass_release_ssa_names won't have access to those private members. So the guts of that routine have been moved into what will ultimately be a method of the name manager. I'm also including a leak detector/verification routine for the freelists. This version will bootstrap on the trunk if the verifier is enabled at the end of flush_ssanames_freelist. However, the vectorizer leaks names horribly, thus it won't pass a regression test or a -O3 bootstrap. In the mean time, the verifier is still useful to help find leaks -- it's obviously not checking by default and the code is marked as a debug function. This wraps up the things I expect to address during this stage1 cycle. I've got a fair amount of patch review to cover in the immediate future as well as starting the bugfixing cycle. Bootstrapped and regression tested on x86_64-linux-gnu. Installed on the trunk. Jeff commit feba260ed75060c9acc265ff12a44557e280f5be Author: Jeff Law Date: Sun Nov 8 20:33:59 2015 -0700 [PATCH] Minor refactoring in tree-ssanames.c & freelists verifier * tree-into-ssa.c (names_to_release): No longer static. * tree-into-ssa.h (names_to_release): Declare. * tree-ssanames.c (verify_ssaname_freelists): New debug function. (release_free_names_and_compact_live_names): New function extracted from pass_release_ssa_names::execute. (pass_release_ssa_names::execute): Use it. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index dfb8350..c70ab87 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2015-11-09 Jeff Law + + * tree-into-ssa.c (names_to_release): No longer static. + * tree-into-ssa.h (names_to_release): Declare. + * tree-ssanames.c (verify_ssaname_freelists): New debug function. + (release_free_names_and_compact_live_names): New function extracted + from pass_release_ssa_names::execute. + (pass_release_ssa_names::execute): Use it. + 2015-11-09 Alan Modra * gensupport.c (add_mnemonic_string): Make len param a size_t. @@ -11,7 +20,7 @@ * gcc/bb-reorder.c (reorder_basic_blocks_simple): Treat a conditional branch with only one successor just like unconditional branches. -2015-11-08 Jeff Law +2015-11-08 Jeff Law * tree-ssa-threadupdate.c (register_jump_thraed): Assert that a non-FSM path has no edges marked with EDGE_DFS_BACK. @@ -369,7 +378,7 @@ the dominance info; free it if we can't. (pass_call_cdce::execute): Don't free the dominance info here. -2015-11-06 Jeff Law +2015-11-06 Jeff Law * tree-ssa-threadedge.c (dummy_simplify): Remove. (thread_around_empty_blocks): Remove backedge_seen_p argument. @@ -402,7 +411,7 @@ (build_scop_scattering): Call build_pbb_minimal_scattering_polyhedrons. (build_poly_scop): Call build_scop_minimal_scattering. -2015-11-06 Jeff Law +2015-11-06 Jeff Law * cfg-flags.def (IGNORE): New edge flag. * tree-vrp.c (identify_jump_threads): Mark and clear edges @@ -1174,7 +1183,7 @@ * tree-ssa.c (gimple_uses_undefined_value_p): New. * tree-ssa.h (gimple_uses_undefined_value_p): Declare. -2015-11-02 Jeff Law +2015-11-02 Jeff Law * tree-ssa-threadupdate.c (valid_jump_thread_path): Also detect cases where the loop latch edge is in the middle of an FSM path. @@ -1238,7 +1247,7 @@ PR middle-end/68166 * fold-const.c: Include "md5.h". -2015-11-01 Jeff Law +2015-11-01 Jeff Law * vmsdbgout.c: Revert unused header file reduction patch. @@ -1287,7 +1296,7 @@ * tree-ssa-structalias.c (ipa_pta_execute): Use make_copy_constraint. -2015-10-30 Jeff Law +2015-10-30 Jeff Law Nathan Sidwell * config/nvptx/nvptx.h (HARD_REGNO_NREGS): Avoid warning on unused diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index 6533998..3086f82 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -94,7 +94,7 @@ static sbitmap interesting_blocks; /* Set of SSA names that have been marked to be released after they were registered in the replacement table. They will be finally released after we finish updating the SSA web. */ -static bitmap names_to_release; +bitmap names_to_release; /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds the to basic block with index I. Allocated once per compilation, *not* diff --git a/gcc/tree-into-ssa.h b/gcc/tree-into-ssa.h index c053f78..aed1e95 100644 --- a/gcc/tree-into-ssa.h +++ b/gcc/tree-into-ssa.h @@ -48,5 +48,6 @@ extern void dump_names_replaced_by (FILE *, tree); extern void debug_names_replaced_by (tree); extern void dump_update_ssa (FILE *); extern void debug_update_ssa (void); +extern bitmap names_to_release; #endif /* GCC_TREE_INTO_SSA_H */ diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 12235f6..096b75b 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -114,6 +114,133 @@ ssanames_print_statistics (void) fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); } +/* Verify the state of the SSA_NAME lists. + + There must be no duplicates on the free list. + Every name on the free list must be marked as on the free list. + Any name on the free list must not appear in the IL. + No names can be leaked. */ + +DEBUG_FUNCTION void +verify_ssaname_freelists (struct function *fun) +{ + /* Do nothing if we are in RTL format. */ + basic_block bb; + FOR_EACH_BB_FN (bb, fun) + { + if (bb->flags & BB_RTL) + return; + } + + bitmap names_in_il = BITMAP_ALLOC (NULL); + + /* Walk the entire IL noting every SSA_NAME we see. */ + FOR_EACH_BB_FN (bb, fun) + { + tree t; + /* First note the result and arguments of PHI nodes. */ + for (gphi_iterator gsi = gsi_start_phis (bb); + !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + t = gimple_phi_result (phi); + bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t)); + + for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) + { + t = gimple_phi_arg_def (phi, i); + if (TREE_CODE (t) == SSA_NAME) + bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t)); + } + } + + /* Then note the operands of each statement. */ + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); + !gsi_end_p (gsi); + gsi_next (&gsi)) + { + ssa_op_iter iter; + gimple *stmt = gsi_stmt (gsi); + FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS) + if (TREE_CODE (t) == SSA_NAME) + bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t)); + } + } + + /* Now walk the free list noting what we find there and verifying + there are no duplicates. */ + bitmap names_in_freelists = BITMAP_ALLOC (NULL); + if (FREE_SSANAMES (fun)) + { + for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++) + { + tree t = (*FREE_SSANAMES (fun))[i]; + + /* Verify that the name is marked as being in the free list. */ + gcc_assert (SSA_NAME_IN_FREE_LIST (t)); + + /* Verify the name has not already appeared in the free list and + note it in the list of names found in the free list. */ + gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t))); + bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t)); + } + } + + /* Similarly for the names in the pending free list. */ + if (FREE_SSANAMES_QUEUE (fun)) + { + for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++) + { + tree t = (*FREE_SSANAMES_QUEUE (fun))[i]; + + /* Verify that the name is marked as being in the free list. */ + gcc_assert (SSA_NAME_IN_FREE_LIST (t)); + + /* Verify the name has not already appeared in the free list and + note it in the list of names found in the free list. */ + gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t))); + bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t)); + } + } + + /* If any name appears in both the IL and the freelists, then + something horrible has happened. */ + bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists); + gcc_assert (!intersect_p); + + /* Names can be queued up for release if there is an ssa update + pending. Pretend we saw them in the IL. */ + if (names_to_release) + bitmap_ior_into (names_in_il, names_to_release); + + /* Function splitting can "lose" SSA_NAMEs in an effort to ensure that + debug/non-debug compilations have the same SSA_NAMEs. So for each + lost SSA_NAME, see if it's likely one from that wart. These will always + be marked as default definitions. So we loosely assume that anything + marked as a default definition isn't leaked by pretening they are + in the IL. */ + for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++) + if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i))) + bitmap_set_bit (names_in_il, i); + + unsigned int i; + bitmap_iterator bi; + bitmap all_names = BITMAP_ALLOC (NULL); + bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1); + bitmap_ior_into (names_in_il, names_in_freelists); + + /* Any name not mentioned in the IL and not in the feelists + has been leaked. */ + EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il, + UNUSED_NAME_VERSION + 1, i, bi) + gcc_assert (!ssa_name (i)); + + BITMAP_FREE (all_names); + BITMAP_FREE (names_in_freelists); + BITMAP_FREE (names_in_il); +} + /* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES. We do not, but should have a mode to verify the state of the SSA_NAMEs @@ -604,6 +731,42 @@ replace_ssa_name_symbol (tree ssa_name, tree sym) TREE_TYPE (ssa_name) = TREE_TYPE (sym); } +/* Release the vector of free SSA_NAMEs and compact the the + vector of SSA_NAMEs that are live. */ + +static void +release_free_names_and_compact_live_names (function *fun) +{ + unsigned i, j; + int n = vec_safe_length (FREE_SSANAMES (fun)); + + /* Now release the freelist. */ + vec_free (FREE_SSANAMES (fun)); + + /* And compact the SSA number space. We make sure to not change the + relative order of SSA versions. */ + for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i) + { + tree name = ssa_name (i); + if (name) + { + if (i != j) + { + SSA_NAME_VERSION (name) = j; + (*fun->gimple_df->ssa_names)[j] = name; + } + j++; + } + } + fun->gimple_df->ssa_names->truncate (j); + + statistics_counter_event (fun, "SSA names released", n); + statistics_counter_event (fun, "SSA name holes removed", i - j); + if (dump_file) + fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n", + n, n * 100.0 / num_ssa_names, i - j); +} + /* Return SSA names that are unused to GGC memory and compact the SSA version namespace. This is used to keep footprint of compiler during interprocedural optimization. */ @@ -638,34 +801,7 @@ public: unsigned int pass_release_ssa_names::execute (function *fun) { - unsigned i, j; - int n = vec_safe_length (FREE_SSANAMES (fun)); - - /* Now release the freelist. */ - vec_free (FREE_SSANAMES (fun)); - - /* And compact the SSA number space. We make sure to not change the - relative order of SSA versions. */ - for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i) - { - tree name = ssa_name (i); - if (name) - { - if (i != j) - { - SSA_NAME_VERSION (name) = j; - (*fun->gimple_df->ssa_names)[j] = name; - } - j++; - } - } - fun->gimple_df->ssa_names->truncate (j); - - statistics_counter_event (fun, "SSA names released", n); - statistics_counter_event (fun, "SSA name holes removed", i - j); - if (dump_file) - fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n", - n, n * 100.0 / num_ssa_names, i - j); + release_free_names_and_compact_live_names (fun); return 0; }