From patchwork Mon Nov 18 21:57:44 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 292217 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)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 7E4132C00B3 for ; Tue, 19 Nov 2013 08:58:05 +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 :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=r1Ty+CoB2S8Gzl0cpWkuqerYjO45OVXWegaEWpluXMLEcL KMNdZ1GkLt5IuMjuM4DXmfOnALB62CZFmeCfv6FEpkREQrlVe8UxAGy/CIe6156+ Md+SVK60MjZqxQZKJwVdOb8UHzkr1uQ1y3JRIozzqidu0zSyOFziYSQTkCdds= 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 :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=8wOWQ7aO+oy3fm5O9xoR37Sbnhc=; b=iCh05gmth8IUi+QUrhZB loRhr6TYaj0JNd7uOyAnG12rxLIQIgR4kEoJJuqBca1i9CPa5fQRn1QPBTPmPAd9 nXHCpWETBPr84I3Lo5bulxBdbVeenlrozJi3EnZlla2a+yR5u6fvtyl/kudCJ3tm 4hSs0Z2wk4Vs4B83fV8FXF4= Received: (qmail 16337 invoked by alias); 18 Nov 2013 21:57:55 -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 16326 invoked by uid 89); 18 Nov 2013 21:57:54 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.9 required=5.0 tests=AWL, BAYES_50, RDNS_NONE, SPF_HELO_PASS, SPF_PASS autolearn=no version=3.3.2 X-HELO: mx1.redhat.com Received: from Unknown (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 18 Nov 2013 21:57:52 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id rAILvjOQ019690 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 18 Nov 2013 16:57:45 -0500 Received: from stumpy.slc.redhat.com (ovpn-113-162.phx2.redhat.com [10.3.113.162]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id rAILviFH006198 for ; Mon, 18 Nov 2013 16:57:44 -0500 Message-ID: <528A8D58.8090901@redhat.com> Date: Mon, 18 Nov 2013 14:57:44 -0700 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.1.0 MIME-Version: 1.0 To: gcc-patches Subject: [PATCH]Beginning of multi-block duplicate support in tree-ssa-threadupdate.c X-IsSubscribed: yes This is the beginnings of multi-block duplication support in tree-ssa-threadupdate.c and is part of the general FSA optimization work. This patch creates space in the redirection_data structure for the additional duplicated block, adds some infrastructure to duplicate a second block, updates the hashing routines to handle the second duplicate, and related fallout. Note we won't create a threading path with multiple duplicated blocks without a small change to tree-ssa-threadedge, so this code is a NOP today, but won't be very soon. Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed on the trunk. Jeff * tree-ssa-threadupdate.c (redirection_data): Record two duplicated blocks instead of just one. (local_info): Explain why we don't create a template for the second duplicated block in a thread path. (create_block_for_threading): Accept argument indicating array index into redirection_data to store its result. (lookup_redirection_data): Initialize both duplicate blocks. (ssa_create_duplicates): If a jump threading path needs multiple blocks duplicated, then duplicate them. (ssa_fix_duplicate_block_edges): Corresponding changes. (ssa_fixup_template_block, thread_single_edge): Likewise. diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index e819d65..f4c03cd 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -115,9 +115,20 @@ struct el struct redirection_data : typed_free_remove { - /* A duplicate of B with the trailing control statement removed and which - targets a single successor of B. */ - basic_block dup_block; + /* We support wiring up two block duplicates in a jump threading path. + + One is a normal block copy where we remove the control statement + and wire up its single remaining outgoing edge to the thread path. + + The other is a joiner block where we leave the control statement + in place, but wire one of the outgoing edges to a thread path. + + In theory we could have multiple block duplicates in a jump + threading path, but I haven't tried that. + + The duplicate blocks appear in this array in the same order in + which they appear in the jump thread path. */ + basic_block dup_blocks[2]; /* The jump threading path. */ vec *path; @@ -171,8 +182,11 @@ struct ssa_local_info_t /* The current block we are working on. */ basic_block bb; - /* A template copy of BB with no outgoing edges or control statement that - we use for creating copies. */ + /* We only create a template block for the first duplicated block in a + jump threading path as we may need many duplicates of that block. + + The second duplicate block in a path is specific to that path. Creating + and sharing a template for that block is considerably more difficult. */ basic_block template_block; /* TRUE if we thread one or more jumps, FALSE otherwise. */ @@ -234,24 +248,27 @@ remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb) } } -/* Create a duplicate of BB. Record the duplicate block in RD. */ +/* Create a duplicate of BB. Record the duplicate block in an array + indexed by COUNT stored in RD. */ static void -create_block_for_threading (basic_block bb, struct redirection_data *rd) +create_block_for_threading (basic_block bb, + struct redirection_data *rd, + unsigned int count) { edge_iterator ei; edge e; /* We can use the generic block duplication code and simply remove the stuff we do not need. */ - rd->dup_block = duplicate_block (bb, NULL, NULL); + rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL); - FOR_EACH_EDGE (e, ei, rd->dup_block->succs) + FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs) e->aux = NULL; /* Zero out the profile, since the block is unreachable for now. */ - rd->dup_block->frequency = 0; - rd->dup_block->count = 0; + rd->dup_blocks[count]->frequency = 0; + rd->dup_blocks[count]->count = 0; } /* Main data structure to hold information for duplicates of BB. */ @@ -275,7 +292,8 @@ lookup_redirection_data (edge e, enum insert_option insert) in the table. */ elt = XNEW (struct redirection_data); elt->path = path; - elt->dup_block = NULL; + elt->dup_blocks[0] = NULL; + elt->dup_blocks[1] = NULL; elt->incoming_edges = NULL; slot = redirection_data.find_slot (elt, insert); @@ -423,11 +441,11 @@ ssa_fix_duplicate_block_edges (struct redirection_data *rd, /* This updates the PHIs at the destination of the duplicate block. */ - update_destination_phis (local_info->bb, rd->dup_block); + update_destination_phis (local_info->bb, rd->dup_blocks[0]); /* Find the edge from the duplicate block to the block we're threading through. That's the edge we want to redirect. */ - victim = find_edge (rd->dup_block, (*path)[1]->e->dest); + victim = find_edge (rd->dup_blocks[0], (*path)[1]->e->dest); e2 = redirect_edge_and_branch (victim, path->last ()->e->dest); e2->count = path->last ()->e->count; @@ -439,8 +457,8 @@ ssa_fix_duplicate_block_edges (struct redirection_data *rd, } else { - remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL); - create_edge_and_update_destination_phis (rd, rd->dup_block); + remove_ctrl_stmt_and_useless_edges (rd->dup_blocks[0], NULL); + create_edge_and_update_destination_phis (rd, rd->dup_blocks[0]); } } /* Hash table traversal callback routine to create duplicate blocks. */ @@ -451,12 +469,32 @@ ssa_create_duplicates (struct redirection_data **slot, { struct redirection_data *rd = *slot; + /* The second duplicated block in a jump threading path is specific + to the path. So it gets stored in RD rather than in LOCAL_DATA. + + Each time we're called, we have to look through the path and see + if a second block needs to be duplicated. + + Note the search starts with the third edge on the path. The first + edge is the incoming edge, the second edge always has its source + duplicated. Thus we start our search with the third edge. */ + vec *path = rd->path; + for (unsigned int i = 2; i < path->length (); i++) + { + if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK + || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK) + { + create_block_for_threading ((*path)[i]->e->src, rd, 1); + break; + } + } + /* Create a template block if we have not done so already. Otherwise use the template to create a new block. */ if (local_info->template_block == NULL) { - create_block_for_threading (local_info->bb, rd); - local_info->template_block = rd->dup_block; + create_block_for_threading ((*path)[1]->e->src, rd, 0); + local_info->template_block = rd->dup_blocks[0]; /* We do not create any outgoing edges for the template. We will take care of that in a later traversal. That way we do not @@ -464,7 +502,7 @@ ssa_create_duplicates (struct redirection_data **slot, } else { - create_block_for_threading (local_info->template_block, rd); + create_block_for_threading (local_info->template_block, rd, 0); /* Go ahead and wire up outgoing edges and update PHIs for the duplicate block. */ @@ -492,7 +530,7 @@ ssa_fixup_template_block (struct redirection_data **slot, to keep its control statement and redirect an outgoing edge. Else we want to remove the control statement & edges, then create a new outgoing edge. In both cases we may need to update PHIs. */ - if (rd->dup_block && rd->dup_block == local_info->template_block) + if (rd->dup_blocks[0] && rd->dup_blocks[0] == local_info->template_block) { ssa_fix_duplicate_block_edges (rd, local_info); return 0; @@ -526,30 +564,30 @@ ssa_redirect_edges (struct redirection_data **slot, thread_stats.num_threaded_edges++; - if (rd->dup_block) + if (rd->dup_blocks[0]) { edge e2; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " Threaded jump %d --> %d to %d\n", - e->src->index, e->dest->index, rd->dup_block->index); + e->src->index, e->dest->index, rd->dup_blocks[0]->index); - rd->dup_block->count += e->count; + rd->dup_blocks[0]->count += e->count; /* Excessive jump threading may make frequencies large enough so the computation overflows. */ - if (rd->dup_block->frequency < BB_FREQ_MAX * 2) - rd->dup_block->frequency += EDGE_FREQUENCY (e); + if (rd->dup_blocks[0]->frequency < BB_FREQ_MAX * 2) + rd->dup_blocks[0]->frequency += EDGE_FREQUENCY (e); /* In the case of threading through a joiner block, the outgoing edges from the duplicate block were updated when they were redirected during ssa_fix_duplicate_block_edges. */ if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK) - EDGE_SUCC (rd->dup_block, 0)->count += e->count; + EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count; /* Redirect the incoming edge (possibly to the joiner block) to the appropriate duplicate block. */ - e2 = redirect_edge_and_branch (e, rd->dup_block); + e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]); gcc_assert (e == e2); flush_pending_stmts (e2); } @@ -830,21 +868,21 @@ thread_single_edge (edge e) npath->safe_push (x); rd.path = npath; - create_block_for_threading (bb, &rd); - remove_ctrl_stmt_and_useless_edges (rd.dup_block, NULL); - create_edge_and_update_destination_phis (&rd, rd.dup_block); + create_block_for_threading (bb, &rd, 0); + remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL); + create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0]); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " Threaded jump %d --> %d to %d\n", - e->src->index, e->dest->index, rd.dup_block->index); + e->src->index, e->dest->index, rd.dup_blocks[0]->index); - rd.dup_block->count = e->count; - rd.dup_block->frequency = EDGE_FREQUENCY (e); - single_succ_edge (rd.dup_block)->count = e->count; - redirect_edge_and_branch (e, rd.dup_block); + rd.dup_blocks[0]->count = e->count; + rd.dup_blocks[0]->frequency = EDGE_FREQUENCY (e); + single_succ_edge (rd.dup_blocks[0])->count = e->count; + redirect_edge_and_branch (e, rd.dup_blocks[0]); flush_pending_stmts (e); - return rd.dup_block; + return rd.dup_blocks[0]; } /* Callback for dfs_enumerate_from. Returns true if BB is different