From patchwork Mon Jun 14 14:04:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1491674 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=xsqHVDc4; dkim=fail reason="signature verification failed" header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=zXgzjMwy; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G3Y9Z6QZfz9sW6 for ; Tue, 15 Jun 2021 00:04:49 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EBDAC3896C30 for ; Mon, 14 Jun 2021 14:04:45 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id ED12B389683E for ; Mon, 14 Jun 2021 14:04:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org ED12B389683E Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id A3D542199C; Mon, 14 Jun 2021 14:04:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1623679442; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=0n5FGfRf81YGay+aJtZ1tYDZryb6ucTkP/j6rBIf8Vg=; b=xsqHVDc4b+gO84qJ/AQTAiihdnwMehscmdysbTdsE9Ur5SHGu2/EFUGvJirEufBrVnRgKv rPiJgVG9Md9yue8uj1N30LcvHe63bcfg+bgppiDyKYo3qh5OXkJBftRpx/ds8FO33W+roe GH0SsflianFo/CyfnahPGSAeLxXuXps= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1623679442; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=0n5FGfRf81YGay+aJtZ1tYDZryb6ucTkP/j6rBIf8Vg=; b=zXgzjMwyNMwEecOmpgTXZGMee/LJM31ok1spWqaPBETni9H8hFodZWUWz0FHWJPPrXgdc3 ua/nh2+tMDyej5Aw== Received: from [10.163.41.62] (unknown [10.163.41.62]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 88084A3BA1; Mon, 14 Jun 2021 14:04:02 +0000 (UTC) Date: Mon, 14 Jun 2021 16:04:02 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Mark irreducible regions in the backwards threader Message-ID: MIME-Version: 1.0 X-Spam-Status: No, score=-10.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The same issue that arises in PR100934 can happen in the backward threader now (Aldy?) - we eventually run into mark_irreducible_loops for non-FSM thread paths checking for paths crossing irreducible region boundaries. The following thus initializes irreducible regions and makes irreducible region discovery handle multiple latches. Bootstrap & regtest pending. 2021-06-14 Richard Biener * cfgloopanal.c (mark_irreducible_loops): Use a dominance check to identify loop latches. * cfgloop.c (verify_loop_structure): Likewise. * loop-init.c (apply_loop_flags): Allow marked irreducible regions even with multiple latches. * predict.c (rebuild_frequencies): Simplify. * tree-ssa-threadbackward.c (pass_thread_jumps::execute): Mark irreducible regions. (pass_early_thread_jumps::execute): Likewise. * tree-ssa-threadupdate.c (jump_thread_path_registry::mark_threaded_blocks): Assert we have irreducible regions marked. --- gcc/cfgloop.c | 14 ++++++++++---- gcc/cfgloopanal.c | 2 +- gcc/loop-init.c | 3 ++- gcc/predict.c | 3 +-- gcc/tree-ssa-threadbackward.c | 6 ++++-- gcc/tree-ssa-threadupdate.c | 2 ++ 6 files changed, 20 insertions(+), 10 deletions(-) diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 4e227cd0891..f094538b9ff 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -1555,11 +1555,17 @@ verify_loop_structure (void) error ("loop %d%'s header does not belong directly to it", i); err = 1; } - if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) - && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) + if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) { - error ("loop %d%'s latch is marked as part of irreducible region", i); - err = 1; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, loop->header->preds) + if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header) + && e->flags & EDGE_IRREDUCIBLE_LOOP) + { + error ("loop %d%'s latch is marked as part of irreducible" + " region", i); + err = 1; + } } } diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c index d0eade3dd34..54426b54881 100644 --- a/gcc/cfgloopanal.c +++ b/gcc/cfgloopanal.c @@ -113,7 +113,7 @@ mark_irreducible_loops (void) /* Ignore latch edges. */ if (e->dest->loop_father->header == e->dest - && e->dest->loop_father->latch == act) + && dominated_by_p (CDI_DOMINATORS, act, e->dest)) continue; /* Edges inside a single loop should be left where they are. Edges diff --git a/gcc/loop-init.c b/gcc/loop-init.c index 17f14075f62..1fde0ede441 100644 --- a/gcc/loop-init.c +++ b/gcc/loop-init.c @@ -48,7 +48,8 @@ apply_loop_flags (unsigned flags) not work). However, we avoid modifying cfg, which some passes may want. */ gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES - | LOOPS_HAVE_RECORDED_EXITS)) == 0); + | LOOPS_HAVE_RECORDED_EXITS + | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) == 0); loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES); } else diff --git a/gcc/predict.c b/gcc/predict.c index 5d0cae5c4a4..d751e6cecce 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -4287,8 +4287,7 @@ rebuild_frequencies (void) if (profile_status_for_fn (cfun) == PROFILE_GUESSED) { - loop_optimizer_init (0); - mark_irreducible_loops (); + loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); connect_infinite_loops_to_exit (); estimate_bb_frequencies (true); remove_fake_exit_edges (); diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 7dd8594e3d4..1a5deafc463 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -887,7 +887,8 @@ pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED) unsigned int pass_thread_jumps::execute (function *fun) { - loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); + loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES + | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); /* Try to thread each block with more than one successor. */ thread_jumps threader; @@ -948,7 +949,8 @@ pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED) unsigned int pass_early_thread_jumps::execute (function *fun) { - loop_optimizer_init (AVOID_CFG_MODIFICATIONS); + loop_optimizer_init (AVOID_CFG_MODIFICATIONS + | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); /* Try to thread each block with more than one successor. */ thread_jumps threader (/*speed_p=*/false); diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index a86302be18e..387994fd882 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -1917,6 +1917,8 @@ jump_thread_path_registry::mark_threaded_blocks (bitmap threaded_blocks) edge e; edge_iterator ei; + gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)); + /* It is possible to have jump threads in which one is a subpath of the other. ie, (A, B), (B, C), (C, D) where B is a joiner block and (B, C), (C, D) where no joiner block exists.