From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id AB2B33858D28 for ; Mon, 8 Jan 2024 12:24:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org AB2B33858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org AB2B33858D28 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1704716669; cv=none; b=CboGM2jAvJsLqN6sAJOjJz6HPSZeq7rA4YEBxDKS8Pyk5SE9GgImqhQb6uxRJ+pcHFLpdUHPWug9tgCoJwOlLxwg7KLkHElAIkSDSIQItxuJ3ZEdJqHvBA6YqeQ/zIo/Gya4s8pnJcw60lcJDfINw4sBITOr+3rt9xD1TBRicEw= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1704716669; c=relaxed/simple; bh=xG6EjZsLGSt1RLm45BWzvTdh+6QGtBJDJ+hhi9Aq1K4=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:Message-ID:MIME-Version; b=XTyRpKJcTWuFBJ+OIJY6GOLv0Ehiw6hzF9DuccSNRm3fyt03OL7lHK1zVtkRDFLoZXcRoEe4ITfxkB6IYqbO/6AFu8siWYRNXwd1VS2ipGLkUXi8M78e2HwpBobDqKoH1hkK9qY1+klArvCb1U7injTqkPrIQ3jyW0sfMl2QYdk= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.168.4.150] (unknown [10.168.4.150]) (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 smtp-out1.suse.de (Postfix) with ESMTPS id AC54421D4C; Mon, 8 Jan 2024 12:24:24 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1704716666; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=suo8fpIXHPWvNDLvtAHF2Yk/KoFvuXplKOESa3iq6sc=; b=VrWDktVsTzfXV27KHoS+WQ0Pb4BbSu/C2ly8TK5ma01p/SfVMNzT8qb/Qu+r7VHD1Bqr4n KrUil/N9A/3G+xqVFuif16VxMpWshuOtdlSyrt1ffUC9xr+JqQTLr9vF8MCu/6Tyj+mNRX l+kBRkOFw+sCIxllHZSzEUDYbQ4fkE8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1704716666; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=suo8fpIXHPWvNDLvtAHF2Yk/KoFvuXplKOESa3iq6sc=; b=jFENCUvpBsE2arK9oz2YQFw4xf8m7rPr7SOjZpEBmOPa4VPE3LzBSRMpEx6XSY9IGTrjH1 nipXTAc/pCzVPsBg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1704716664; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=suo8fpIXHPWvNDLvtAHF2Yk/KoFvuXplKOESa3iq6sc=; b=hUzQDyF5yS4nxc+wuBf9hUo7KfGlbo+bpDuH2dcyIRuhrsneqjZIDmMNSG7OAQ44RO6+3N Xwq78U+DRNUWgqU8cRg4tlTPBo3nG7f1x7kior+Lbo3C9txzeXBnYjvJmAMzrgQmOEdIiu M1x/rq9lSqSwokZyemq4jR7LGERQH0M= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1704716664; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=suo8fpIXHPWvNDLvtAHF2Yk/KoFvuXplKOESa3iq6sc=; b=KM1lrmN7C4VTbiC2lnwO9pWX2A8fgh+2I4tHWF51OrWULuV5fw7o3SPae4fALs66eoNufV CstQApN/iX+PvxCQ== Date: Mon, 8 Jan 2024 13:19:26 +0100 (CET) From: Richard Biener To: Tamar Christina cc: gcc-patches@gcc.gnu.org, nd@arm.com, jlaw@ventanamicro.com Subject: Re: [PATCH]middle-end: Fix dominators updates when peeling with multiple exits [PR113144] In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Level: Authentication-Results: smtp-out1.suse.de; none X-Spam-Level: X-Spam-Score: -4.30 X-Spamd-Result: default: False [-4.30 / 50.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[4]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MIME_GOOD(-0.10)[text/plain]; NEURAL_HAM_LONG(-1.00)[-1.000]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-0.996]; DBL_BLOCKED_OPENRESOLVER(0.00)[tree-vect-loop-manip.cc:url,suse.de:email]; FUZZY_BLOCKED(0.00)[rspamd.com]; RCVD_COUNT_ZERO(0.00)[0]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; BAYES_HAM(-3.00)[100.00%] X-Spam-Status: No, score=-11.2 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,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, 29 Dec 2023, Tamar Christina wrote: > Hi All, > > Only trying to update certain dominators doesn't seem to work very well > because as the loop gets versioned, peeled, or skip_vector then we end up with > very complicated control flow. This means that the final merge blocks for the > loop exit are not easy to find or update. > > Instead of trying to pick which exits to update, this changes it to update all > the blocks reachable by the new exits. This is because they'll contain common > blocks with e.g. the versioned loop. It's these blocks that need an update > most of the time. > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. > > Ok for master? This makes it quadratic in the number of vectorized early exit loops in a function. The vectorizer CFG manipulation operates in a local enough bubble that programmatic updating of dominators should be possible (after all we manage to produce correct SSA form!), the proposed change gets us too far off to a point where re-computating dominance info is likely cheaper (but no, we shouldn't do this either). Can you instead give manual updating a try again? I think versioning should produce up-to-date dominator info, it's only when you redirect branches during peeling that you'd need adjustments - but IIRC we're never introducing new merges? IIRC we can't wipe dominators during transform since we query them during code generation. We possibly could code generate all CFG manipulations of all vectorized loops, recompute all dominators and then do code generation of all vectorized loops. But then we're doing a loop transform and the exits will ultimatively end up in the same place, so the CFG and dominator update is bound to where the original exits went to. Richard > Thanks, > Tamar > > gcc/ChangeLog: > > PR middle-end/113144 > * tree-vect-loop-manip.cc (slpeel_tree_duplicate_loop_to_edge_cfg): > Update all dominators reachable from exit. > > gcc/testsuite/ChangeLog: > > PR middle-end/113144 > * gcc.dg/vect/vect-early-break_94-pr113144.c: New test. > > --- inline copy of patch -- > diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_94-pr113144.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_94-pr113144.c > new file mode 100644 > index 0000000000000000000000000000000000000000..903fe7be6621e81db6f29441e4309fa213d027c5 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_94-pr113144.c > @@ -0,0 +1,41 @@ > +/* { dg-do compile } */ > +/* { dg-add-options vect_early_break } */ > +/* { dg-require-effective-target vect_early_break } */ > +/* { dg-require-effective-target vect_int } */ > + > +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */ > + > +long tar_atol256_max, tar_atol256_size, tar_atosl_min; > +char tar_atol256_s; > +void __errno_location(); > + > + > +inline static long tar_atol256(long min) { > + char c; > + int sign; > + c = tar_atol256_s; > + sign = c; > + while (tar_atol256_size) { > + if (c != sign) > + return sign ? min : tar_atol256_max; > + c = tar_atol256_size--; > + } > + if ((c & 128) != (sign & 128)) > + return sign ? min : tar_atol256_max; > + return 0; > +} > + > +inline static long tar_atol(long min) { > + return tar_atol256(min); > +} > + > +long tar_atosl() { > + long n = tar_atol(-1); > + if (tar_atosl_min) { > + __errno_location(); > + return 0; > + } > + if (n > 0) > + return 0; > + return n; > +} > diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc > index 1066ea17c5674e03412b3dcd8a62ddf4dd54cf31..3810983a80c8b989be9fd9a9993642069fd39b99 100644 > --- a/gcc/tree-vect-loop-manip.cc > +++ b/gcc/tree-vect-loop-manip.cc > @@ -1716,8 +1716,6 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, edge loop_exit, > /* Now link the alternative exits. */ > if (multiple_exits_p) > { > - set_immediate_dominator (CDI_DOMINATORS, new_preheader, > - main_loop_exit_block); > for (auto gsi_from = gsi_start_phis (loop->header), > gsi_to = gsi_start_phis (new_preheader); > !gsi_end_p (gsi_from) && !gsi_end_p (gsi_to); > @@ -1751,12 +1749,26 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, edge loop_exit, > > /* Finally after wiring the new epilogue we need to update its main exit > to the original function exit we recorded. Other exits are already > - correct. */ > + correct. Because of versioning, skip vectors and others we must update > + the dominators of every node reachable by the new exits. */ > if (multiple_exits_p) > { > update_loop = new_loop; > - for (edge e : get_loop_exit_edges (loop)) > - doms.safe_push (e->dest); > + hash_set visited; > + auto_vec workset; > + edge ev; > + edge_iterator ei; > + workset.safe_splice (get_loop_exit_edges (loop)); > + while (!workset.is_empty ()) > + { > + auto bb = workset.pop ()->dest; > + if (visited.add (bb)) > + continue; > + doms.safe_push (bb); > + FOR_EACH_EDGE (ev, ei, bb->succs) > + workset.safe_push (ev); > + } > + visited.empty (); > doms.safe_push (exit_dest); > > /* Likely a fall-through edge, so update if needed. */ > > > > > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)