From patchwork Sat Nov 7 06:31:50 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 541220 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 E605B140D16 for ; Sat, 7 Nov 2015 17:32:02 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=yOTwQzfg; 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=dTaDitaIaNZfQWIOwgHJXuTS6bF7qkOtCrJCL3u4HN1iBFwtbh iIjOa3pa+fhjky8+5SXcJ17J3II1sV/SqDJEayhbAT4iid+YWZBgghB6i393e4sP 3hALPaBNCDyezkE/k+LkqTH2LpuV6ueApQOB0ibcim53anzPo8CBVVjXQ= 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=5OGV3lpFJbKEIHxPJS7iXUs3REk=; b=yOTwQzfgbD/Qbit+pxza dooQeh0/3jksIgTQfErIW4L4sGysBHGzvs7j8BF19i6taHovqz5DhvDOz9ahyYZM 0aUXkFMJrt3g26Zgqaqd1MCL/za4VphHSgxQSDBn+aQIA7iURxumtLw7kfSmdG9B yd7BEs/h9MAlIU4daEtRc+0= Received: (qmail 97528 invoked by alias); 7 Nov 2015 06:31:54 -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 97519 invoked by uid 89); 7 Nov 2015 06:31:54 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.8 required=5.0 tests=AWL, BAYES_40, 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; Sat, 07 Nov 2015 06:31:52 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (Postfix) with ESMTPS id 13E0AC00075E for ; Sat, 7 Nov 2015 06:31:51 +0000 (UTC) Received: from localhost.localdomain (ovpn-113-107.phx2.redhat.com [10.3.113.107]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA76VoEB018731 for ; Sat, 7 Nov 2015 01:31:50 -0500 To: gcc-patches@gcc.gnu.org From: Jeff Law Subject: [PATCH] Remove more backedge threading support Message-ID: <563D9AD6.4060803@redhat.com> Date: Fri, 6 Nov 2015 23:31:50 -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 removes the last bits of code to thread through backedges using the old threader. Behaviour is essentially the same, except some shuffling of code to ensure we always fall back to the FSM threader if a backedge is found. Bootstrapped and regression tested on x86_64-linux-gnu. Installing on the trunk momentarily. This does not affect 68198. Next step in the cleanup is removing the bits that handle updating the CFG/SSA graph for threads across backedges :-) Jeff commit 5de480fca9f5b76d13033a274699b9557f5fe66c Author: law Date: Sat Nov 7 06:31:14 2015 +0000 [PATCH] Remove more backedge threading support * tree-ssa-threadedge.c (dummy_simplify): Remove. (thread_around_empty_blocks): Remove backedge_seen_p argument. If we thread to a backedge, then return false. Update recursive call to eliminate backedge_seen_p argument. (thread_through_normal_block): Remove backedge_seen_p argument. Remove backedge_seen_p argument from calls to thread_around_empty_blocks. Remove checks on backedge_seen_p. If we thread to a backedge, then return 0. (thread_across_edge): Remove bookkeeping for backedge_seen. Don't pass it to thread_through_normal_block or thread_through_empty_blocks. For joiner handling, if we see a backedge, do not try normal threading. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@229911 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 90fbe5f..78dc3f0 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2015-11-06 Jeff Law + + * tree-ssa-threadedge.c (dummy_simplify): Remove. + (thread_around_empty_blocks): Remove backedge_seen_p argument. + If we thread to a backedge, then return false. Update recursive + call to eliminate backedge_seen_p argument. + (thread_through_normal_block): Remove backedge_seen_p argument. + Remove backedge_seen_p argument from calls to + thread_around_empty_blocks. Remove checks on backedge_seen_p. + If we thread to a backedge, then return 0. + (thread_across_edge): Remove bookkeeping for backedge_seen. Don't + pass it to thread_through_normal_block or thread_through_empty_blocks. + For joiner handling, if we see a backedge, do not try normal + threading. + 2015-11-06 Abderrazek Zaafrani * graphite-optimize-isl.c (optimize_isl): Call isl_union_map_is_equal. diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 9379198..971fc52 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -376,17 +376,6 @@ record_temporary_equivalences_from_stmts_at_dest (edge e, return stmt; } -/* Once we have passed a backedge in the CFG when threading, we do not want to - utilize edge equivalences for simplification purpose. They are no longer - necessarily valid. We use this callback rather than the ones provided by - DOM/VRP to achieve that effect. */ -static tree -dummy_simplify (gimple *stmt1 ATTRIBUTE_UNUSED, gimple *stmt2 ATTRIBUTE_UNUSED, - class avail_exprs_stack *avail_exprs_stack ATTRIBUTE_UNUSED) -{ - return NULL_TREE; -} - /* Simplify the control statement at the end of the block E->dest. To avoid allocating memory unnecessarily, a scratch GIMPLE_COND @@ -396,7 +385,7 @@ dummy_simplify (gimple *stmt1 ATTRIBUTE_UNUSED, gimple *stmt2 ATTRIBUTE_UNUSED, a condition using pass specific information. Return the simplified condition or NULL if simplification could - not be performed. + not be performed. The available expression table is referenced via AVAIL_EXPRS_STACK. */ @@ -707,7 +696,7 @@ propagate_threaded_block_debug_into (basic_block dest, basic_block src) return false. DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to - try and simplify the condition at the end of TAKEN_EDGE->dest. + try and simplify the condition at the end of TAKEN_EDGE->dest. The available expression table is referenced via AVAIL_EXPRS_STACK. */ @@ -718,8 +707,7 @@ thread_around_empty_blocks (edge taken_edge, bool handle_dominating_asserts, pfn_simplify simplify, bitmap visited, - vec *path, - bool *backedge_seen_p) + vec *path) { basic_block bb = taken_edge->dest; gimple_stmt_iterator gsi; @@ -754,23 +742,23 @@ thread_around_empty_blocks (edge taken_edge, if (single_succ_p (bb)) { taken_edge = single_succ_edge (bb); + + if ((taken_edge->flags & EDGE_DFS_BACK) != 0) + return false; + if (!bitmap_bit_p (visited, taken_edge->dest->index)) { jump_thread_edge *x = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); path->safe_push (x); bitmap_set_bit (visited, taken_edge->dest->index); - *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); - if (*backedge_seen_p) - simplify = dummy_simplify; return thread_around_empty_blocks (taken_edge, dummy_cond, avail_exprs_stack, handle_dominating_asserts, simplify, visited, - path, - backedge_seen_p); + path); } } @@ -786,13 +774,6 @@ thread_around_empty_blocks (edge taken_edge, && gimple_code (stmt) != GIMPLE_SWITCH) return false; - /* If we have traversed a backedge, then we do not want to look - at certain expressions in the table that can not be relied upon. - Luckily the only code that looked at those expressions is the - SIMPLIFY callback, which we replace if we can no longer use it. */ - if (*backedge_seen_p) - simplify = dummy_simplify; - /* Extract and simplify the condition. */ cond = simplify_control_stmt_condition (taken_edge, stmt, avail_exprs_stack, dummy_cond, @@ -805,6 +786,9 @@ thread_around_empty_blocks (edge taken_edge, { taken_edge = find_taken_edge (bb, cond); + if ((taken_edge->flags & EDGE_DFS_BACK) != 0) + return false; + if (bitmap_bit_p (visited, taken_edge->dest->index)) return false; bitmap_set_bit (visited, taken_edge->dest->index); @@ -812,9 +796,6 @@ thread_around_empty_blocks (edge taken_edge, jump_thread_edge *x = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); path->safe_push (x); - *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); - if (*backedge_seen_p) - simplify = dummy_simplify; thread_around_empty_blocks (taken_edge, dummy_cond, @@ -822,8 +803,7 @@ thread_around_empty_blocks (edge taken_edge, handle_dominating_asserts, simplify, visited, - path, - backedge_seen_p); + path); return true; } @@ -871,14 +851,8 @@ thread_through_normal_block (edge e, avail_exprs_stack *avail_exprs_stack, pfn_simplify simplify, vec *path, - bitmap visited, - bool *backedge_seen_p) + bitmap visited) { - /* If we have seen a backedge, then we rely solely on the FSM threader - to find jump threads. */ - if (*backedge_seen_p) - return 0; - /* We want to record any equivalences created by traversing E. */ if (!handle_dominating_asserts) record_temporary_equivalences (e, const_and_copies, avail_exprs_stack); @@ -948,6 +922,7 @@ thread_through_normal_block (edge e, address. */ if (dest == NULL || dest == e->dest + || (taken_edge->flags & EDGE_DFS_BACK) != 0 || bitmap_bit_p (visited, dest->index)) return 0; @@ -958,15 +933,11 @@ thread_through_normal_block (edge e, jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); path->safe_push (x); - *backedge_seen_p |= ((e->flags & EDGE_DFS_BACK) != 0); } jump_thread_edge *x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK); path->safe_push (x); - *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); - if (*backedge_seen_p) - simplify = dummy_simplify; /* See if we can thread through DEST as well, this helps capture secondary effects of threading without having to re-run DOM or @@ -982,8 +953,7 @@ thread_through_normal_block (edge e, handle_dominating_asserts, simplify, visited, - path, - backedge_seen_p); + path); return 1; } } @@ -993,18 +963,6 @@ thread_through_normal_block (edge e, /* We are exiting E->src, see if E->dest ends with a conditional jump which has a known value when reached via E. - Special care is necessary if E is a back edge in the CFG as we - may have already recorded equivalences for E->dest into our - various tables, including the result of the conditional at - the end of E->dest. Threading opportunities are severely - limited in that case to avoid short-circuiting the loop - incorrectly. - - Note it is quite common for the first block inside a loop to - end with a conditional which is either always true or always - false when reached via the loop backedge. Thus we do not want - to blindly disable threading across a loop backedge. - DUMMY_COND is a shared cond_expr used by condition simplification as scratch, to avoid allocating memory. @@ -1029,7 +987,6 @@ thread_across_edge (gcond *dummy_cond, class avail_exprs_stack *)) { bitmap visited = BITMAP_ALLOC (NULL); - bool backedge_seen; stmt_count = 0; @@ -1037,16 +994,18 @@ thread_across_edge (gcond *dummy_cond, bitmap_clear (visited); bitmap_set_bit (visited, e->src->index); bitmap_set_bit (visited, e->dest->index); - backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0); - if (backedge_seen) - simplify = dummy_simplify; - - int threaded = thread_through_normal_block (e, dummy_cond, - handle_dominating_asserts, - const_and_copies, - avail_exprs_stack, - simplify, path, - visited, &backedge_seen); + + int threaded; + if ((e->flags & EDGE_DFS_BACK) == 0) + threaded = thread_through_normal_block (e, dummy_cond, + handle_dominating_asserts, + const_and_copies, + avail_exprs_stack, + simplify, path, + visited); + else + threaded = 0; + if (threaded > 0) { propagate_threaded_block_debug_into (path->last ()->e->dest, @@ -1111,6 +1070,13 @@ thread_across_edge (gcond *dummy_cond, /* Look at each successor of E->dest to see if we can thread through it. */ FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) { + if ((e->flags & EDGE_DFS_BACK) != 0 + || (taken_edge->flags & EDGE_DFS_BACK) != 0) + { + find_jump_threads_backwards (taken_edge); + continue; + } + /* Push a fresh marker so we can unwind the equivalences created for each of E->dest's successors. */ const_and_copies->push_marker (); @@ -1132,21 +1098,13 @@ thread_across_edge (gcond *dummy_cond, x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK); path->safe_push (x); found = false; - backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0); - backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); - if (backedge_seen) - simplify = dummy_simplify; found = thread_around_empty_blocks (taken_edge, dummy_cond, avail_exprs_stack, handle_dominating_asserts, simplify, visited, - path, - &backedge_seen); - - if (backedge_seen) - simplify = dummy_simplify; + path); if (!found) found = thread_through_normal_block (path->last ()->e, dummy_cond, @@ -1154,7 +1112,7 @@ thread_across_edge (gcond *dummy_cond, const_and_copies, avail_exprs_stack, simplify, path, - visited, &backedge_seen) > 0; + visited) > 0; /* If we were able to thread through a successor of E->dest, then record the jump threading opportunity. */