From patchwork Mon Nov 9 03:19:53 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 541563 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 AED9E1402C6 for ; Mon, 9 Nov 2015 14:20:05 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=q1BjQuep; 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=cnYBLhPtp6Tc0m8dCNn1rCvUSjlCY/f4WnOFWWwcuRsLO682IY LPXFuj26TRn50l2iVzpOg0jLEpn4K+oFjN+ShFIEd4y4DTfB+bwZ/MObK+JUmYep Kxzo4ETdH9AWA4Uo0Yxf0YKEhg3WRd7TzYKBkzB1B+yrmjPYKoRFxvMGM= 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=Jawh4Zp98kpxoqcrhNBAsvXuFWM=; b=q1BjQuepsKdgYKhnqek5 BlJF6795BeCayZtMKE4YwvdASoY7jXEz6KIdOfkk9P6wH3bJWGFtP05DG0OmfJSr 8V6XpjvHDvkonm7/WaFuN9+038mHGFU5cQa+qvXoa2oiu1K3AR7U59z/dvNPorCi BIxt4I54axPYhLhizkTliAg= Received: (qmail 123744 invoked by alias); 9 Nov 2015 03:19:58 -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 123730 invoked by uid 89); 9 Nov 2015 03:19:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, T_RP_MATCHES_RCVD 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 03:19:55 +0000 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) by mx1.redhat.com (Postfix) with ESMTPS id 0111DA2873 for ; Mon, 9 Nov 2015 03:19:53 +0000 (UTC) Received: from localhost.localdomain (ovpn-113-107.phx2.redhat.com [10.3.113.107]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA93JrJ2002554 for ; Sun, 8 Nov 2015 22:19:53 -0500 To: gcc-patches From: Jeff Law Subject: [PATCH] Remove backedge handling support in tree-ssa-threadupdate.c Message-ID: <564010D9.2010808@redhat.com> Date: Sun, 8 Nov 2015 20:19:53 -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 With the FSM threader handling all edges with EDGE_DFS_BACK set, we can simplify a variety of bits in tree-ssa-threadupdate.c which is precisely what this patch does. The patch also introduces some checking bits to ensure that backedges do not appear in old-fashioned jump threading paths. Bootstrapped and regression tested on x86_64-linux-gnu. Installing on the trunk. This is the last threading cleanup for stage1. I am hoping to do one more cleanup in the ssa name manager before stage1 closes, then onward to bugfixing. Jeff commit a22a1fbd306cf41a797a3457a8c8ebf4ba07a276 Author: law Date: Mon Nov 9 03:19:09 2015 +0000 [PATCH] Remove backedge handling support in tree-ssa-threadupdate.c * tree-ssa-threadupdate.c (register_jump_thraed): Assert that a non-FSM path has no edges marked with EDGE_DFS_BACK. (ssa_redirect_edges): No longer call mark_loop_for_removal. (thread_single_edge, def_split_header_continue_p): Remove. (bb_ends_with_multiway_branch): Likewise. (thread_through_loop_header): Remove cases of threading from latch through the header. Simplify knowing we won't thread the latch. (thread_through_all_blocks): Simplify knowing that only the FSM threader needs to handle backedges. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@229982 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 81664bf..6401c43 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +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. + (ssa_redirect_edges): No longer call mark_loop_for_removal. + (thread_single_edge, def_split_header_continue_p): Remove. + (bb_ends_with_multiway_branch): Likewise. + (thread_through_loop_header): Remove cases of threading from + latch through the header. Simplify knowing we won't thread + the latch. + (thread_through_all_blocks): Simplify knowing that only the FSM + threader needs to handle backedges. + 2015-11-08 Eric Botcazou * doc/extend.texi (type attributes): Document scalar_storage_order. diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 68650e5..184cf34 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -1406,10 +1406,6 @@ ssa_redirect_edges (struct redirection_data **slot, fprintf (dump_file, " Threaded jump %d --> %d to %d\n", e->src->index, e->dest->index, rd->dup_blocks[0]->index); - /* If we redirect a loop latch edge cancel its loop. */ - if (e->src == e->src->loop_father->latch) - mark_loop_for_removal (e->src->loop_father); - /* Redirect the incoming edge (possibly to the joiner block) to the appropriate duplicate block. */ e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]); @@ -1630,67 +1626,6 @@ thread_block (basic_block bb, bool noloop_only) return retval; } - -/* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the - copy of E->dest created during threading, or E->dest if it was not necessary - to copy it (E is its single predecessor). */ - -static basic_block -thread_single_edge (edge e) -{ - basic_block bb = e->dest; - struct redirection_data rd; - vec *path = THREAD_PATH (e); - edge eto = (*path)[1]->e; - - delete_jump_thread_path (path); - e->aux = NULL; - - thread_stats.num_threaded_edges++; - - if (single_pred_p (bb)) - { - /* If BB has just a single predecessor, we should only remove the - control statements at its end, and successors except for ETO. */ - remove_ctrl_stmt_and_useless_edges (bb, eto->dest); - - /* And fixup the flags on the single remaining edge. */ - eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); - eto->flags |= EDGE_FALLTHRU; - - return bb; - } - - /* Otherwise, we need to create a copy. */ - if (e->dest == eto->src) - update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto); - - vec *npath = new vec (); - jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); - npath->safe_push (x); - - x = new jump_thread_edge (eto, EDGE_COPY_SRC_BLOCK); - npath->safe_push (x); - rd.path = npath; - - create_block_for_threading (bb, &rd, 0, NULL); - remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL); - create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 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_blocks[0]->index); - - 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); - - delete_jump_thread_path (npath); - return rd.dup_blocks[0]; -} - /* Callback for dfs_enumerate_from. Returns true if BB is different from STOP and DBDS_CE_STOP. */ @@ -1769,24 +1704,6 @@ determine_bb_domination_status (struct loop *loop, basic_block bb) return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN); } -/* Return true if BB is part of the new pre-header that is created - when threading the latch to DATA. */ - -static bool -def_split_header_continue_p (const_basic_block bb, const void *data) -{ - const_basic_block new_header = (const_basic_block) data; - const struct loop *l; - - if (bb == new_header - || loop_depth (bb->loop_father) < loop_depth (new_header->loop_father)) - return false; - for (l = bb->loop_father; l; l = loop_outer (l)) - if (l == new_header->loop_father) - return true; - return false; -} - /* Thread jumps through the header of LOOP. Returns true if cfg changes. If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges to the inside of the loop. */ @@ -1869,27 +1786,7 @@ thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers) if (single_succ_p (header)) goto fail; - /* If we threaded the latch using a joiner block, we cancel the - threading opportunity out of an abundance of caution. However, - still allow threading from outside to inside the loop. */ - if (latch->aux) - { - vec *path = THREAD_PATH (latch); - if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK) - { - delete_jump_thread_path (path); - latch->aux = NULL; - } - } - - if (latch->aux) - { - vec *path = THREAD_PATH (latch); - tgt_edge = (*path)[1]->e; - tgt_bb = tgt_edge->dest; - } - else if (!may_peel_loop_headers - && !redirection_block_p (loop->header)) + if (!may_peel_loop_headers && !redirection_block_p (loop->header)) goto fail; else { @@ -1961,96 +1858,34 @@ thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers) tgt_bb = split_edge (tgt_edge); } - if (latch->aux) - { - basic_block *bblocks; - unsigned nblocks, i; - - /* First handle the case latch edge is redirected. We are copying - the loop header but not creating a multiple entry loop. Make the - cfg manipulation code aware of that fact. */ - set_loop_copy (loop, loop); - loop->latch = thread_single_edge (latch); - set_loop_copy (loop, NULL); - gcc_assert (single_succ (loop->latch) == tgt_bb); - loop->header = tgt_bb; - - /* Remove the new pre-header blocks from our loop. */ - bblocks = XCNEWVEC (basic_block, loop->num_nodes); - nblocks = dfs_enumerate_from (header, 0, def_split_header_continue_p, - bblocks, loop->num_nodes, tgt_bb); - for (i = 0; i < nblocks; i++) - if (bblocks[i]->loop_father == loop) - { - remove_bb_from_loops (bblocks[i]); - add_bb_to_loop (bblocks[i], loop_outer (loop)); - } - free (bblocks); - - /* If the new header has multiple latches mark it so. */ - FOR_EACH_EDGE (e, ei, loop->header->preds) - if (e->src->loop_father == loop - && e->src != loop->latch) - { - loop->latch = NULL; - loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES); - } - - /* Cancel remaining threading requests that would make the - loop a multiple entry loop. */ - FOR_EACH_EDGE (e, ei, header->preds) - { - edge e2; - - if (e->aux == NULL) - continue; + basic_block new_preheader; - vec *path = THREAD_PATH (e); - e2 = path->last ()->e; - - if (e->src->loop_father != e2->dest->loop_father - && e2->dest != loop->header) - { - delete_jump_thread_path (path); - e->aux = NULL; - } - } - - /* Thread the remaining edges through the former header. */ - thread_block (header, false); - } - else + /* Now consider the case entry edges are redirected to the new entry + block. Remember one entry edge, so that we can find the new + preheader (its destination after threading). */ + FOR_EACH_EDGE (e, ei, header->preds) { - basic_block new_preheader; + if (e->aux) + break; + } - /* Now consider the case entry edges are redirected to the new entry - block. Remember one entry edge, so that we can find the new - preheader (its destination after threading). */ - FOR_EACH_EDGE (e, ei, header->preds) - { - if (e->aux) - break; - } + /* The duplicate of the header is the new preheader of the loop. Ensure + that it is placed correctly in the loop hierarchy. */ + set_loop_copy (loop, loop_outer (loop)); - /* The duplicate of the header is the new preheader of the loop. Ensure - that it is placed correctly in the loop hierarchy. */ - set_loop_copy (loop, loop_outer (loop)); - - thread_block (header, false); - set_loop_copy (loop, NULL); - new_preheader = e->dest; - - /* Create the new latch block. This is always necessary, as the latch - must have only a single successor, but the original header had at - least two successors. */ - loop->latch = NULL; - mfb_kj_edge = single_succ_edge (new_preheader); - loop->header = mfb_kj_edge->dest; - latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL); - loop->header = latch->dest; - loop->latch = latch->src; - } + thread_block (header, false); + set_loop_copy (loop, NULL); + new_preheader = e->dest; + /* Create the new latch block. This is always necessary, as the latch + must have only a single successor, but the original header had at + least two successors. */ + loop->latch = NULL; + mfb_kj_edge = single_succ_edge (new_preheader); + loop->header = mfb_kj_edge->dest; + latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL); + loop->header = latch->dest; + loop->latch = latch->src; return true; fail: @@ -2332,20 +2167,6 @@ mark_threaded_blocks (bitmap threaded_blocks) } -/* Return TRUE if BB ends with a switch statement or a computed goto. - Otherwise return false. */ -static bool -bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED) -{ - gimple *stmt = last_stmt (bb); - if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) - return true; - if (stmt && gimple_code (stmt) == GIMPLE_GOTO - && TREE_CODE (gimple_goto_dest (stmt)) == SSA_NAME) - return true; - return false; -} - /* Verify that the REGION is a valid jump thread. A jump thread is a special case of SEME Single Entry Multiple Exits region in which all nodes in the REGION have exactly one incoming edge. The only exception is the first block @@ -2788,36 +2609,7 @@ thread_through_all_blocks (bool may_peel_loop_headers) e->aux = NULL; ei_next (&ei); } - else if (bb_ends_with_multiway_branch (path->last ()->e->src)) - { - /* The code to thread through loop headers may have - split a block with jump threads attached to it. - - We can identify this with a disjoint jump threading - path. If found, just remove it. */ - for (unsigned int i = 0; i < path->length () - 1; i++) - if ((*path)[i]->e->dest != (*path)[i + 1]->e->src) - { - delete_jump_thread_path (path); - e->aux = NULL; - ei_next (&ei); - break; - } - - /* Our path is still valid, thread it. */ - if (e->aux) - { - if (thread_block ((*path)[0]->e->dest, false)) - e->aux = NULL; - else - { - delete_jump_thread_path (path); - e->aux = NULL; - ei_next (&ei); - } - } - } - else + else { delete_jump_thread_path (path); e->aux = NULL; @@ -2878,18 +2670,26 @@ register_jump_thread (vec *path) /* First make sure there are no NULL outgoing edges on the jump threading path. That can happen for jumping to a constant address. */ for (unsigned int i = 0; i < path->length (); i++) - if ((*path)[i]->e == NULL) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, - "Found NULL edge in jump threading path. Cancelling jump thread:\n"); - dump_jump_thread_path (dump_file, *path, false); - } + { + if ((*path)[i]->e == NULL) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Found NULL edge in jump threading path. Cancelling jump thread:\n"); + dump_jump_thread_path (dump_file, *path, false); + } - delete_jump_thread_path (path); - return; - } + delete_jump_thread_path (path); + return; + } + + /* Only the FSM threader is allowed to thread across + backedges in the CFG. */ + if (flag_checking + && (*path)[0]->type != EDGE_FSM_THREAD) + gcc_assert (((*path)[i]->e->flags & EDGE_DFS_BACK) == 0); + } if (dump_file && (dump_flags & TDF_DETAILS)) dump_jump_thread_path (dump_file, *path, true);