From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR05-AM6-obe.outbound.protection.outlook.com (mail-am6eur05on2071.outbound.protection.outlook.com [40.107.22.71]) by sourceware.org (Postfix) with ESMTPS id AC7663858D35 for ; Wed, 28 Jun 2023 13:41:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org AC7663858D35 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=XqG6kuUisk4/d2kYo1l9LgVmOaQmaJhGT4cHpvmiG8Q=; b=PZmGhAVgj0QW2NxxI1YTLut62GIrHw+HG5wCsibDZ1nwHtl/M496ZUwkgOcu/RS7K4L+OzBRiwnkIHwqCsc7QH8TzWC1vOjT727qnMrzH9b73wPQtbqSaAJg2LOe8QihSjOy6woFLSKe4Jxbjqdatw5PAPtVbrQIL6f02bRJFgs= Received: from DUZPR01CA0222.eurprd01.prod.exchangelabs.com (2603:10a6:10:4b4::29) by DU0PR08MB8638.eurprd08.prod.outlook.com (2603:10a6:10:402::5) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6521.24; Wed, 28 Jun 2023 13:41:11 +0000 Received: from DBAEUR03FT019.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:4b4:cafe::f8) by DUZPR01CA0222.outlook.office365.com (2603:10a6:10:4b4::29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6544.19 via Frontend Transport; Wed, 28 Jun 2023 13:41:11 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DBAEUR03FT019.mail.protection.outlook.com (100.127.142.129) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6544.18 via Frontend Transport; Wed, 28 Jun 2023 13:41:11 +0000 Received: ("Tessian outbound 546d04a74417:v142"); Wed, 28 Jun 2023 13:41:11 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 73d362209b2d6a96 X-CR-MTA-TID: 64aa7808 Received: from dbd2d2d3e616.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 2063862E-61F2-4D96-B1D2-0D2AD90E7DC7.1; Wed, 28 Jun 2023 13:41:04 +0000 Received: from EUR01-DB5-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id dbd2d2d3e616.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Wed, 28 Jun 2023 13:41:04 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Koy2S7WzHu2fXczR+D/7Z0LmSiyBoiT/53qXBYX3Wm0rbotM/1VyP1RCE/+NRtInCZqUEdw7wrgLsT89VuDa3hNJRIBfjN0brCJckJgDIgeeqZJgK1BBBsy0IzYyL68RNcHf8dyZC2lA0Sq0byYl4hqkKMRU3fyBl8GNVipci01ak0WOPoys+Qn1IOronhZJgjheXm2rHyRYJq6Hk/+ogT+ptUEyTH2P2PockAiIPLaJZKjb/Zjo0BCslwYZ1TwlblqrM7rQIZD3mXROGIfkvsVTntGAp14I+MuQR9DdeARaiU9tdDVadJrRi5lNDvBbEoBTm18ZGU41m+Evmw/OZQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=XqG6kuUisk4/d2kYo1l9LgVmOaQmaJhGT4cHpvmiG8Q=; b=AqSDDp1VDWEZS8YfORqxviMx/MpMpyvYyMMVONvcO6vowtQZZ0OgNZ2ERxQUFY+JaRc3ZZVlB3yQj4J9pkBL+thkCcnfk+BNPO34XHs7BNgJN21GqWl5Uh7H8JEEvMdJAmKFnvbCX9PIEsNwU84RqmnTn1qSlZbb9yjsdQTcVLIOFVZdC8WpjiM/B1vestAQtC3KP12mTY3dRAomm/purkvPBh/3X/JvjBDCT/32I6JT3kosFp++lbHDxmMn8DsAFZGeAMjQ+hK+8s+YItg6dDwLb/WqZopl3ukRXz3nyldGXgNHaKrcVgtinUfUMRBybAnp0zItIxmF6nBybBIaWw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=XqG6kuUisk4/d2kYo1l9LgVmOaQmaJhGT4cHpvmiG8Q=; b=PZmGhAVgj0QW2NxxI1YTLut62GIrHw+HG5wCsibDZ1nwHtl/M496ZUwkgOcu/RS7K4L+OzBRiwnkIHwqCsc7QH8TzWC1vOjT727qnMrzH9b73wPQtbqSaAJg2LOe8QihSjOy6woFLSKe4Jxbjqdatw5PAPtVbrQIL6f02bRJFgs= Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by DBAPR08MB5576.eurprd08.prod.outlook.com (2603:10a6:10:1ae::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6521.26; Wed, 28 Jun 2023 13:41:02 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::2301:1cde:cfe7:eaf0]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::2301:1cde:cfe7:eaf0%6]) with mapi id 15.20.6521.026; Wed, 28 Jun 2023 13:41:02 +0000 Date: Wed, 28 Jun 2023 14:40:59 +0100 From: Tamar Christina To: gcc-patches@gcc.gnu.org Cc: nd@arm.com, rguenther@suse.de, jlaw@ventanamicro.com Subject: [PATCH v5 0/19] Support early break/return auto-vectorization Message-ID: Content-Type: multipart/mixed; boundary="H/n9T9ifpmrWjE63" Content-Disposition: inline X-ClientProxiedBy: LO4P265CA0176.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:312::16) To VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: VI1PR08MB5325:EE_|DBAPR08MB5576:EE_|DBAEUR03FT019:EE_|DU0PR08MB8638:EE_ X-MS-Office365-Filtering-Correlation-Id: 1bfee86b-b897-446b-0649-08db77dd55fe x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: QGXYGbze0i0BwPF2odCKIQFySlVnN9foHMP84q5h0paK1pT9RTNM8iQxAN5zjf+q9idvRlkYUns22cYAxDYzjRC4TEDVVEFCiOgn1ij6R9GHLuXWbrthkye9AHrdRtPsFuTD3Q18+Nfa41oQoTpyMEBeWYQmUpu7gqVpxt2xcsopQ/Ait30ii8+UooaY3r/1RSJMRFtGK1BqCeZpJwPJ+5IgfxJYYo0HSCIv49WU09F1adXCK1qC7qCbJgeZU+Q/cCtkW9tYVtp0m1xEi6wVU7r8RqLMMx+vMDFKzk0dvRRNLPfCiUEsaVkS3kg57hJlwigi1Y6X/SfmzpeIneCNLFP93d66+udPvj2fCzk1P+tWNTx2f+E3v0+bv8P75X17NnYJI0zpolqQ/mi2LfiMeI1AdssU9HPN+HqW6knLLraSv8XZ7Ty1u+bf4vZxiMWYz64Kz/6dg9GeGZFaiF9yikkLbFOw9iz1EsTjBXa74Q5Upb1weTAa5pmqYzdyy5fLprng+7gwTaVgCE7hsVTWw1+w1Z2t8UvidBZ6D2zorzbMDOk0BSoH0gYpvxyqpKtYKfiscC686WZCbefvYSULhzkKpP8w7N3rdlgpCPlfc8T0xeoagTd61U3gQLUit1hBjVn+HSErutMcdssA7UPAKBN5YpmJCIpj3Dh0b0KQ79Q= X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:VI1PR08MB5325.eurprd08.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230028)(4636009)(136003)(346002)(39860400002)(396003)(376002)(366004)(451199021)(6486002)(2616005)(83380400001)(33964004)(6666004)(6512007)(6506007)(26005)(44144004)(2906002)(186003)(478600001)(235185007)(44832011)(6916009)(5660300002)(36756003)(4326008)(66946007)(316002)(38100700002)(8936002)(41300700001)(66476007)(8676002)(86362001)(66556008)(4216001)(2700100001)(357404004);DIR:OUT;SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBAPR08MB5576 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: DBAEUR03FT019.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: b57eb8f2-27ec-4eae-fae0-08db77dd4ff2 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: CThu3jGmWXJmUVhw1Hl3WnghHPlHX5ttcyLNSc4Kj3VOpob5mb0YVSS60w6Rslk/qHlv0aIrhz0xeS1A8ougaQsBZln+uvOxxHytx1qHTNfSS64nvazAqolmQ+yyUyDvQSoS+4xyQ7bcTMZFCAMAWVU9Tg+mb7p9TGOFcrY45pldvG5W9uOOIUWAerIvLgC+6D3nNw37XHUSr7Sv1HE4Q9x0MZ0oC8ObPOpoViJB1CQhjzwUvNPsq9KAJEjq2buXWC0GXHAxq8x1OQugOijuGqy7TULGmXO5DJ/ufWtvSmN7rsqlfo6J6xDWKrputYAR0BAHQ6kEZK06LLwwBFTpsSiNt8jlHJ4MRk2cSF0nscQjY45L6+tp5cSzGIjHk85TRcabPBdkfIghTPsY+EgwnCQo+T20w0gUeZuiCJv+ZJk92hqXbQ6LHJC++qeBrNUwoYkBogWfmdLUbow+sfd3p3k1mx7AffpJwmqkM6KbG8ZEMVwGkA8Sr8o53JaamCvTOEiZ7McRHR2gzSWvhw5U+L9+IQAJbZFBD583d4Lz0ohlTQaOq4jqCIBurvpqkKFEZ8pbtw4U7skGt0EwYVwn6DtoxVBM+woLbfmekGCzW6252iG7PiGyGooB5/L4o2QPK4Fa7c3W9+JSMiYoO5Ja6LaQGNIyZwi6gjouhZ6G53JF/rXpnX8H9tD0q7yR/u5lNMheOGYnHlSAWz8gwJxxwfgdP1DX5JOlaCxgqW3i9t0uQP7hEqGMjWQQsCsSB9qUE+lEfK8IGuTl2ozlCtuXQLAQGjW4jK8JeLPcqv0BS83XtTChVYQaWjK4n/5njKvt X-Forefront-Antispam-Report: CIP:63.35.35.123;CTRY:IE;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:64aa7808-outbound-1.mta.getcheckrecipient.com;PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com;CAT:NONE;SFS:(13230028)(4636009)(346002)(39860400002)(396003)(136003)(376002)(451199021)(36840700001)(46966006)(40470700004)(82310400005)(36860700001)(36756003)(5660300002)(356005)(44832011)(235185007)(70206006)(86362001)(41300700001)(6916009)(8936002)(40460700003)(40480700001)(8676002)(81166007)(316002)(82740400003)(4326008)(70586007)(478600001)(107886003)(6486002)(47076005)(186003)(6506007)(6512007)(26005)(44144004)(33964004)(336012)(2906002)(83380400001)(6666004)(2616005)(4216001)(2700100001)(357404004);DIR:OUT;SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Jun 2023 13:41:11.7089 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 1bfee86b-b897-446b-0649-08db77dd55fe X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d;Ip=[63.35.35.123];Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: DBAEUR03FT019.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU0PR08MB8638 X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,FORGED_SPF_HELO,KAM_DMARC_NONE,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SCC_10_SHORT_WORD_LINES,SCC_5_SHORT_WORD_LINES,SPF_HELO_PASS,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE,UNPARSEABLE_RELAY autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: --H/n9T9ifpmrWjE63 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Hi All, This patch adds initial support for early break vectorization in GCC. The support is added for any target that implements a vector cbranch optab, this includes both fully masked and non-masked targets. Depending on the operation, the vectorizer may also require support for boolean mask reductions using Inclusive OR. This is however only checked then the comparison would produce multiple statements. Concretely the kind of loops supported are of the forms: for (int i = 0; i < N; i++) { if () { ... ; } } where can be: - break - return - goto Any number of statements can be used before the occurs. Since this is an initial version for GCC 14 it has the following limitations and features: - Only fixed sized iterations and buffers are supported. That is to say any vectors loaded or stored must be to statically allocated arrays with known sizes. N must also be known. This limitation is because our primary target for this optimization is SVE. For VLA SVE we can't easily do cross page iteraion checks. The result is likely to also not be beneficial. For that reason we punt support for variable buffers till we have First-Faulting support in GCC. - any stores in should not be to the same objects as in . Loads are fine as long as they don't have the possibility to alias. More concretely, we block RAW dependencies when the intermediate value can't be separated fromt the store, or the store itself can't be moved. - The number of loop iterations must be known, this is just a temporarily limitation that I intend to address in GCC 14 itself as follow on patches. - Prologue peeling, alignment peelinig and loop versioning are supported. - Fully masked loops, unmasked loops and partially masked loops are supported - Any number of loop early exits are supported. - The early exit must be before the natural loop exit/latch. The vectorizer is designed in way to propage phi-nodes downwards. As such supporting this inverted control flow is hard. - No support for epilogue vectorization. The only epilogue supported is the scalar final one. Epilogue vectorization would also not be profitable. - Early breaks are only supported for inner loop vectorization. I have pushed a branch to refs/users/tnfchris/heads/gcc-14-early-break With the help of IPA and LTO this still gets hit quite often. During bootstrap it hit rather frequently. Additionally TSVC s332, s481 and s482 all pass now since these are tests for support for early exit vectorization. This implementation does not support completely handling the early break inside the vector loop itself but instead supports adding checks such that if we know that we have to exit in the current iteration then we branch to scalar code to actually do the final VF iterations which handles all the code in . niters analysis and the majority of the vectorizer with hardcoded single_exit have been updated with the use of a new function vec_loop_iv value which returns the exit the vectorizer wants to use as the main IV exit. for niters the this exit is what determines the overall iterations as that is the O(iters) for the loop. For the scalar loop we know that whatever exit you take you have to perform at most VF iterations. For vector code we only case about the state of fully performed iteration and reset the scalar code to the (partially) remaining loop. This new version of the patch does the majority of the work in a new rewritten loop peeling. This new function maintains LCSSA all the way through and no longer requires the touch up functions the vectorized used to incrementally adjust them later on. This means that aside from IV updates and guard edge updates the early exit code is identical to the single exit cases. When the loop is peeled during the copying I have to go through great lengths to keep the dominators up to date. All exits from the first loop are rewired to the loop header of the second loop. But this can change the immediate dominator. The dominators can change again when we wire in the loop guard, as such peeling now returns a list of dominators that need to be updated if a new guard edge is added. For the loop peeling we rewrite the loop form: Header --- |x| 2 | v -------3<------ early exit | | | v v | latch 7 4----->6 | | | v | 8 | | | v ------>5 into Header --- |x| 2 | v -------3<------ early exit | | | v v | latch 7 4----->6 | | | v | 8 | | | v | New Header | --- ----->|x| 9 | v ------10<----- early exit | | | v v | latch 14 11---->13 | | | v | 12 | | | v ------> 5 That is to say, the first vector loop executes so long as the early exit isn't needed. Once the exit is taken, the scalar code will perform at most VF extra iterations. The exact number depending on peeling and iteration start and which exit was taken (natural or early). For this scalar loop, all early exits are treated the same. When we vectorize we move any statement not related to the early break itself and that would be incorrect to execute before the break (i.e. has side effects) to after the break. If this is not possible we decline to vectorize. This means that we check at the start of iterations whether we are going to exit or not. During the analyis phase we check whether we are allowed to do this moving of statements. Also note that we only move the scalar statements, but only do so after peeling but just before we start transforming statements. Codegen: for e.g. #define N 803 unsigned vect_a[N]; unsigned vect_b[N]; unsigned test4(unsigned x) { unsigned ret = 0; for (int i = 0; i < N; i++) { vect_b[i] = x + i; if (vect_a[i] > x) break; vect_a[i] = x; } return ret; } We generate for Adv. SIMD: test4: adrp x2, .LC0 adrp x3, .LANCHOR0 dup v2.4s, w0 add x3, x3, :lo12:.LANCHOR0 movi v4.4s, 0x4 add x4, x3, 3216 ldr q1, [x2, #:lo12:.LC0] mov x1, 0 mov w2, 0 .p2align 3,,7 .L3: ldr q0, [x3, x1] add v3.4s, v1.4s, v2.4s add v1.4s, v1.4s, v4.4s cmhi v0.4s, v0.4s, v2.4s umaxp v0.4s, v0.4s, v0.4s fmov x5, d0 cbnz x5, .L6 add w2, w2, 1 str q3, [x1, x4] str q2, [x3, x1] add x1, x1, 16 cmp w2, 200 bne .L3 mov w7, 3 .L2: lsl w2, w2, 2 add x5, x3, 3216 add w6, w2, w0 sxtw x4, w2 ldr w1, [x3, x4, lsl 2] str w6, [x5, x4, lsl 2] cmp w0, w1 bcc .L4 add w1, w2, 1 str w0, [x3, x4, lsl 2] add w6, w1, w0 sxtw x1, w1 ldr w4, [x3, x1, lsl 2] str w6, [x5, x1, lsl 2] cmp w0, w4 bcc .L4 add w4, w2, 2 str w0, [x3, x1, lsl 2] sxtw x1, w4 add w6, w1, w0 ldr w4, [x3, x1, lsl 2] str w6, [x5, x1, lsl 2] cmp w0, w4 bcc .L4 str w0, [x3, x1, lsl 2] add w2, w2, 3 cmp w7, 3 beq .L4 sxtw x1, w2 add w2, w2, w0 ldr w4, [x3, x1, lsl 2] str w2, [x5, x1, lsl 2] cmp w0, w4 bcc .L4 str w0, [x3, x1, lsl 2] .L4: mov w0, 0 ret .p2align 2,,3 .L6: mov w7, 4 b .L2 and for SVE: test4: adrp x2, .LANCHOR0 add x2, x2, :lo12:.LANCHOR0 add x5, x2, 3216 mov x3, 0 mov w1, 0 cntw x4 mov z1.s, w0 index z0.s, #0, #1 ptrue p1.b, all ptrue p0.s, all .p2align 3,,7 .L3: ld1w z2.s, p1/z, [x2, x3, lsl 2] add z3.s, z0.s, z1.s cmplo p2.s, p0/z, z1.s, z2.s b.any .L2 st1w z3.s, p1, [x5, x3, lsl 2] add w1, w1, 1 st1w z1.s, p1, [x2, x3, lsl 2] add x3, x3, x4 incw z0.s cmp w3, 803 bls .L3 .L5: mov w0, 0 ret .p2align 2,,3 .L2: cntw x5 mul w1, w1, w5 cbz w5, .L5 sxtw x1, w1 sub w5, w5, #1 add x5, x5, x1 add x6, x2, 3216 b .L6 .p2align 2,,3 .L14: str w0, [x2, x1, lsl 2] cmp x1, x5 beq .L5 mov x1, x4 .L6: ldr w3, [x2, x1, lsl 2] add w4, w0, w1 str w4, [x6, x1, lsl 2] add x4, x1, 1 cmp w0, w3 bcs .L14 mov w0, 0 ret On the workloads this work is based on we see between 2-3x performance uplift using this patch. Follow up plan: - Boolean vectorization has several shortcomings. I've filed PR110223 with the bigger ones that cause vectorization to fail with this patch. - SLP support. This is planned for GCC 15 as for majority of the cases build SLP itself fails. This means I'll need to spend time in making this more robust first. Additionally it requires: * Adding support for vectorizing CFG (gconds) * Support for CFG to differ between vector and scalar loops. Both of which would be disruptive to the tree and I suspect I'll be handling fallouts from this patch for a while. So I plan to work on the surrounding building blocks first for the remainder of the year. Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. Also ran across various workloads and no issues. When closer to acceptance I will run on other targets as well and clean up related testsuite fallouts there. --- inline copy of patch -- -- --H/n9T9ifpmrWjE63 Content-Type: text/plain; charset=utf-8 Content-Disposition: attachment; filename="rb17494.patch" --H/n9T9ifpmrWjE63-- From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-db3eur04on2058.outbound.protection.outlook.com [40.107.6.58]) by sourceware.org (Postfix) with ESMTPS id 6A9D73858C52 for ; Mon, 6 Nov 2023 07:37:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6A9D73858C52 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 6A9D73858C52 Authentication-Results: server2.sourceware.org; arc=pass smtp.remote-ip=40.107.6.58 ARC-Seal: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1699256236; cv=pass; b=umpNBKVNso706z6wy6PTzZyEVM4oOdjLaQg55PAgaGVEcdTwE44hfIqEWmNWyW16cU3gz5wk8FrBDvGQ7S2D9d8yZ+6MiAXP3C7xzs+SWthq3Zv8tMOiIiI8IZxMBJEP4+9IVXn1C8wSNZoD8T0xa0ymeJFxgqToMhESQwlzprU= ARC-Message-Signature: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1699256236; c=relaxed/simple; bh=iG6PKn6lr/MoOv4o4n46XXhXplCyxTaKCdkZi3Qx0Qk=; h=DKIM-Signature:DKIM-Signature:Date:From:To:Subject:Message-ID: MIME-Version; b=Mj1Wcbek3sNl72I2EkLUhZvBDpP/EZW4D+ilyoiDLqd5lSgMUCkQF7RN731hDbzAobUMm2t56IIFbSeTGGGAmztylrGkNNk/NNFEahytoIhBmeUwaPPky0ete7SRHfs8c4+vuBJ7sSWQEKm0t0SBrzg1ENW4wrqSveqHHLRKk3w= ARC-Authentication-Results: i=3; server2.sourceware.org ARC-Seal: i=2; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=pass; b=ZmDDhlrpMq7zjbSTmbL3PS37X7WfkcJ8aEUk/mrXp2Mxuxu9EPXbgH08dXgStKNayDeQlQhA/5i1zBffLvo2l1vOgtTUCsNE4X/slzlZvhifJKKCNoCudc+ua+8UUlESyiSLvqUz7+DksiJ7Ad4l/t2VPdtrOdLoBII39A9iBD8mlHXodhxqW+pD2wh63KVVXfqSa8n8fJEk17XE50SRB6fbfp2LeTPUsy+nSsFZuCPnJMZIqE2a835vmuwalJabK6gTXBwanKRa+7VKadNYDjKqVIIwFWW36r4g2dZaIVj6HDgMx0tejWXgRxeO9GwDnzJuvYQYEczAXx7kSlCIQw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=oC3fPuB6iQzDpddgjvq1OZ0mp5GPLiPa64nbKaRaSkU=; b=ZiQKgF2UsLf036TNcHuZlm76qoVtTmje0DXlvAsqw+hbmOOwcC5yax8ufsfCBuNN7rKRu3MzC7fIO8YwpYdqJNLkt/qTGDUBg1tK56NwELCGkK/R8rKIZuv6L3clMCvqoOw6TGEAzCiSO/O14aHG1pX3iE1/2SxpEPgmb8j82t0dRGa/Tg6MeTCW3RLWyRAC8I+sTJMqoZNymXSeYU1sX6Vw4GR4EDS0lh1Uam8gHXGwrotnppw4EQ0vZB1NOAd/a561S2wbrms0/lsHqVNsB6Z4uK/Nli4oPeSKgNYzVZuiZN2XEx2F8JD21PlpBGiJ4+BHk638v8TBiYJW532SDg== ARC-Authentication-Results: i=2; mx.microsoft.com 1; spf=pass (sender ip is 63.35.35.123) smtp.rcpttodomain=gcc.gnu.org smtp.mailfrom=arm.com; dmarc=pass (p=none sp=none pct=100) action=none header.from=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com; arc=pass (0 oda=1 ltdi=1 spf=[1,1,smtp.mailfrom=arm.com] dkim=[1,1,header.d=arm.com] dmarc=[1,1,header.from=arm.com]) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=oC3fPuB6iQzDpddgjvq1OZ0mp5GPLiPa64nbKaRaSkU=; b=GbTZ9iEli2NsIjHvvo3bZVSvWGxOc3exgsHwK6rPPc6PwXMf64v2lsl7vu3JGRGEuHnQOm1EPHqHN6Zqg8GC8jiz+osXonFHz9H/ZS2e3D8zAR5OVhC3WzgBJR4k4EeInVlGncdjmLRKd7mCsb0Dr/99vl3lAIX5yml/U2Dj1kE= Received: from DU2PR04CA0288.eurprd04.prod.outlook.com (2603:10a6:10:28c::23) by AS2PR08MB10293.eurprd08.prod.outlook.com (2603:10a6:20b:62f::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6954.27; Mon, 6 Nov 2023 07:37:07 +0000 Received: from DB5PEPF00014B8B.eurprd02.prod.outlook.com (2603:10a6:10:28c:cafe::e) by DU2PR04CA0288.outlook.office365.com (2603:10a6:10:28c::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6954.27 via Frontend Transport; Mon, 6 Nov 2023 07:37:07 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DB5PEPF00014B8B.mail.protection.outlook.com (10.167.8.199) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6977.16 via Frontend Transport; Mon, 6 Nov 2023 07:37:07 +0000 Received: ("Tessian outbound e243565b0037:v228"); Mon, 06 Nov 2023 07:37:07 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 73d362209b2d6a96 X-CR-MTA-TID: 64aa7808 Received: from 9e78d91d3b7a.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 7B970B7F-BD27-4D94-987C-133F6B6EC1EC.1; Mon, 06 Nov 2023 07:37:00 +0000 Received: from EUR03-DBA-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 9e78d91d3b7a.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Mon, 06 Nov 2023 07:37:00 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=WYo9kDuCkWX+wYhzDClJkvunI0DE3i+e6KIW0FgErKCnvvz0tPVbQG74JMe6fZCxuLghCojKau+kFoAdoC/axw3CecZJWoy4yyBzNQ6pDPg1MO2eN1SJMocCbsgE1O5LOtF0BLHseOb9c8VxjGs1Hf1ko84IFDtfFdDDIWAKipLPrlEnOf5cl5zUcc5Thx4kCuetn41phOk9lEiECBTnoRjSgNxhv/JaPgsCdnFIbxLmDRw7AeIOc8YnNexipa5mj7Yksen8rlqh6+x8B/zIp+WpJ0i66Qq8o9xgmxpLdgqcH10a+dki8cih5PJcdOfEF5Eu0eqmvvNgaXp2nYxUlw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=oC3fPuB6iQzDpddgjvq1OZ0mp5GPLiPa64nbKaRaSkU=; b=dAAIooPF/yBgk4wFt9Z16G/6MLTdVhtv6XvBDr4uPSQuubN/9mJwkxXmICdXlHU28xBbWxWjVLWUUtJMMuNcxj29vHiSYcEfdDji2kfJJhOJ/d5jr2JU5ZFynsWbWSscYqWAf6jd0GvDbjna0kcYBZ++kCp4joc/JKcmjOWcxZq94zdtvj/6OAIxnR9pZ2sQ1VkGieIWRmAaGSjTRa2OvOtw9wv+MrIQjiQc8GyQRN2ZhtJW9sO2387nuM3ck+LNAx4htggihzfleRGwuT37RkETUyKBfa7+2Lk5cOBfcMrq2QdZ4zJ/7n4ixMTBWZfjP4s6Pfpijj5N1R1VQY2nZA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=oC3fPuB6iQzDpddgjvq1OZ0mp5GPLiPa64nbKaRaSkU=; b=GbTZ9iEli2NsIjHvvo3bZVSvWGxOc3exgsHwK6rPPc6PwXMf64v2lsl7vu3JGRGEuHnQOm1EPHqHN6Zqg8GC8jiz+osXonFHz9H/ZS2e3D8zAR5OVhC3WzgBJR4k4EeInVlGncdjmLRKd7mCsb0Dr/99vl3lAIX5yml/U2Dj1kE= Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by DU0PR08MB9581.eurprd08.prod.outlook.com (2603:10a6:10:44b::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6954.28; Mon, 6 Nov 2023 07:36:57 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::26aa:efdd:a74a:27d0]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::26aa:efdd:a74a:27d0%5]) with mapi id 15.20.6954.028; Mon, 6 Nov 2023 07:36:57 +0000 Date: Mon, 6 Nov 2023 07:36:53 +0000 From: Tamar Christina To: rguenther@suse.de, gcc-patches@gcc.gnu.org Cc: nd@arm.com Subject: [PATCH v6 0/21]middle-end: Support early break/return auto-vectorization Message-ID: Content-Type: multipart/mixed; boundary="WYf58djMjHI13eUX" Content-Disposition: inline X-ClientProxiedBy: LO4P123CA0146.GBRP123.PROD.OUTLOOK.COM (2603:10a6:600:188::7) To VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: VI1PR08MB5325:EE_|DU0PR08MB9581:EE_|DB5PEPF00014B8B:EE_|AS2PR08MB10293:EE_ X-MS-Office365-Filtering-Correlation-Id: c656aafd-3e84-49c4-eff5-08dbde9b2dd3 x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: qQa/IS9tWiqgN/j5WAWOqFuZY/0G5iu8mLxH6UL4gQAifwhwPguqMbaDV1bqiniB9a1202QTnxfQjFgP8lt37+WGS3GzLIJCs4tm4hvlGwObBTmAK5zVY79aY6Z7yzFrJP5c1CVwYS8aGEdz7eqEeZhwUFldzRPGs7wi93fCkSo0PkVFkfJJil6ltmtGITwjTtq5cA1rovm5LK3+W6DJSkItqUA12vaMSOY++IFmLc8ELW+Ahs3FJ1slAoSYrmwH+yt9SlLfmyQRqegI0mKvyyXDOSVnRmn4CcyWQUSQLx95SR6ZYOq1Kl+8OTdgWnpTkIa5yFE9nkaSCflZGOe9q86If3t92nK7PqNdAC4EIG9z4AVHGCICvGwcXbtGOsvRsRC74Dfn8jArxgVQMXCzpFGrNW4LZPFop/hEUK4Hi8z/OICi/gnfLaxcyQgGhidoTY9u/NO+R17ktda2AnEEt4K59EcGXICWdJ2r4SMD8M/xrEwSFK+aOEseUjhXj90jYs2PpYBqt48qG2T7UynRzGVJFKTa8LV33sDDPNcsIL6pLuT53w3WSyH4sHZJhD5gJnarml6lm+3d3J4V8qWn7Gl032gfXlXJEgQHjfbhzCmrQOoVRB/c0YCz6Zcxrf4W+rF0J2U38m2NmFmu4bBOZaq7ozcAEv5BWjEJCS4ESg8= X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:VI1PR08MB5325.eurprd08.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230031)(396003)(376002)(136003)(346002)(39860400002)(366004)(230922051799003)(64100799003)(451199024)(186009)(1800799009)(6506007)(478600001)(2616005)(44144004)(6512007)(6666004)(6486002)(33964004)(36756003)(38100700002)(86362001)(66946007)(5660300002)(235185007)(44832011)(316002)(66476007)(66556008)(41300700001)(83380400001)(2906002)(26005)(8676002)(4326008)(8936002)(4216001)(2700100001)(357404004);DIR:OUT;SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU0PR08MB9581 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: DB5PEPF00014B8B.eurprd02.prod.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: c52f85c5-45c5-4e79-6f03-08dbde9b27ea X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: scJqcrr9jChrknKEMJYYtFjDovQI2CNDMgN1MNrPURzOw9F7waDPZiIGyf9ND/U4keMFjhRQOAQU4MLBa8iD61ItoZnQ267vE+Rdlr4hzHqsUJ5WWhcTzyramNNn+c0JKm0OZUv7IMoRa3LzYckp/EKKKWiXqK5PfbiCEbOBLmmR4wN4Ye681YtJSD5sSAMrC+61fihpRRT4MqBoNq5UNMnh0EO4fFgIK999p3PbcVLH3RYcAeWTP6rFo1x3CumQXRpjHbesq8ak9y1odQVL6GM+u10ttKd1NhI+Mjnrn9+57S8gzRJH55AN1qjFtCNJmPnnrkFOvkzVZnueHAfDRPzUyKzpb2ojb3/C65BN93PFRv8RTXFbBaqUW12BMGhVkYZuF/upVibeYVRUHxewy+srH23dZ9QXC4+PtxrJ7LTCoiUZ10MnTt5LjgNPMZBI85Cxe8lUYNn7+ZmUihWC7rQt3hYh+F4g05RJt6DTjFY/X8zSuweMZiYnHt6cs2EvYm+D0o+EmwGteLEM+uDR5zfjoybo2npx27O2jq8mxv6hD3iOuYDsIIndlj68QwVRnB+ar6yBKI5wQLtRG2/mXk7x4KQBtQOCJNP/gJNeRWP/V4dssf2rjBffdQdLYzTbOf+QWg5EZNJ9eOvMNUa3pi1izIIwc8krgTNdAK9EPgRYcuoidYvyKB/dX8XSFUEFs6yJJE62fVN/jOgh9oFqBCLS/4TY0tah6MqubCP6DU591BtOUJzQUJ53eSfL5Nprk695iunfhXO730o2pkH6gQpRl0gDjUkDFjLX6OyjgdAk3vFx4yY2oO5LwpU02xMT X-Forefront-Antispam-Report: CIP:63.35.35.123;CTRY:IE;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:64aa7808-outbound-1.mta.getcheckrecipient.com;PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com;CAT:NONE;SFS:(13230031)(4636009)(396003)(136003)(376002)(39860400002)(346002)(230922051799003)(451199024)(64100799003)(1800799009)(82310400011)(186009)(36840700001)(46966006)(40470700004)(40460700003)(40480700001)(6666004)(2616005)(6512007)(44144004)(6506007)(478600001)(6486002)(33964004)(36860700001)(36756003)(356005)(86362001)(82740400003)(81166007)(41300700001)(5660300002)(235185007)(70586007)(70206006)(44832011)(47076005)(83380400001)(2906002)(26005)(336012)(316002)(8936002)(8676002)(4326008)(4216001)(2700100001)(357404004);DIR:OUT;SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Nov 2023 07:37:07.3218 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: c656aafd-3e84-49c4-eff5-08dbde9b2dd3 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d;Ip=[63.35.35.123];Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: DB5PEPF00014B8B.eurprd02.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS2PR08MB10293 X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,FORGED_SPF_HELO,KAM_DMARC_NONE,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SCC_10_SHORT_WORD_LINES,SCC_5_SHORT_WORD_LINES,SPF_HELO_PASS,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE,UNPARSEABLE_RELAY autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Message-ID: <20231106073653.hYrrWRdFvayB_jtP3eC51lzbyuaQKMc6-fQj9IBVueg@z> --WYf58djMjHI13eUX Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Hi All, This patch adds initial support for early break vectorization in GCC. The support is added for any target that implements a vector cbranch optab, this includes both fully masked and non-masked targets. Depending on the operation, the vectorizer may also require support for boolean mask reductions using Inclusive OR. This is however only checked then the comparison would produce multiple statements. Note: I am currently struggling to get patch 7 correct in all cases and could use some feedback there. Concretely the kind of loops supported are of the forms: for (int i = 0; i < N; i++) { if () { ... ; } } where can be: - break - return - goto Any number of statements can be used before the occurs. Since this is an initial version for GCC 14 it has the following limitations and features: - Only fixed sized iterations and buffers are supported. That is to say any vectors loaded or stored must be to statically allocated arrays with known sizes. N must also be known. This limitation is because our primary target for this optimization is SVE. For VLA SVE we can't easily do cross page iteraion checks. The result is likely to also not be beneficial. For that reason we punt support for variable buffers till we have First-Faulting support in GCC. - any stores in should not be to the same objects as in . Loads are fine as long as they don't have the possibility to alias. More concretely, we block RAW dependencies when the intermediate value can't be separated fromt the store, or the store itself can't be moved. - Prologue peeling, alignment peelinig and loop versioning are supported. - Fully masked loops, unmasked loops and partially masked loops are supported - Any number of loop early exits are supported. - No support for epilogue vectorization. The only epilogue supported is the scalar final one. Peeling code supports it but the code motion code cannot find instructions to make the move in the epilog. - Early breaks are only supported for inner loop vectorization. I have pushed a branch to refs/users/tnfchris/heads/gcc-14-early-break With the help of IPA and LTO this still gets hit quite often. During bootstrap it hit rather frequently. Additionally TSVC s332, s481 and s482 all pass now since these are tests for support for early exit vectorization. This implementation does not support completely handling the early break inside the vector loop itself but instead supports adding checks such that if we know that we have to exit in the current iteration then we branch to scalar code to actually do the final VF iterations which handles all the code in . For the scalar loop we know that whatever exit you take you have to perform at most VF iterations. For vector code we only case about the state of fully performed iteration and reset the scalar code to the (partially) remaining loop. That is to say, the first vector loop executes so long as the early exit isn't needed. Once the exit is taken, the scalar code will perform at most VF extra iterations. The exact number depending on peeling and iteration start and which exit was taken (natural or early). For this scalar loop, all early exits are treated the same. When we vectorize we move any statement not related to the early break itself and that would be incorrect to execute before the break (i.e. has side effects) to after the break. If this is not possible we decline to vectorize. This means that we check at the start of iterations whether we are going to exit or not. During the analyis phase we check whether we are allowed to do this moving of statements. Also note that we only move the scalar statements, but only do so after peeling but just before we start transforming statements. Codegen: for e.g. #define N 803 unsigned vect_a[N]; unsigned vect_b[N]; unsigned test4(unsigned x) { unsigned ret = 0; for (int i = 0; i < N; i++) { vect_b[i] = x + i; if (vect_a[i] > x) break; vect_a[i] = x; } return ret; } We generate for Adv. SIMD: test4: adrp x2, .LC0 adrp x3, .LANCHOR0 dup v2.4s, w0 add x3, x3, :lo12:.LANCHOR0 movi v4.4s, 0x4 add x4, x3, 3216 ldr q1, [x2, #:lo12:.LC0] mov x1, 0 mov w2, 0 .p2align 3,,7 .L3: ldr q0, [x3, x1] add v3.4s, v1.4s, v2.4s add v1.4s, v1.4s, v4.4s cmhi v0.4s, v0.4s, v2.4s umaxp v0.4s, v0.4s, v0.4s fmov x5, d0 cbnz x5, .L6 add w2, w2, 1 str q3, [x1, x4] str q2, [x3, x1] add x1, x1, 16 cmp w2, 200 bne .L3 mov w7, 3 .L2: lsl w2, w2, 2 add x5, x3, 3216 add w6, w2, w0 sxtw x4, w2 ldr w1, [x3, x4, lsl 2] str w6, [x5, x4, lsl 2] cmp w0, w1 bcc .L4 add w1, w2, 1 str w0, [x3, x4, lsl 2] add w6, w1, w0 sxtw x1, w1 ldr w4, [x3, x1, lsl 2] str w6, [x5, x1, lsl 2] cmp w0, w4 bcc .L4 add w4, w2, 2 str w0, [x3, x1, lsl 2] sxtw x1, w4 add w6, w1, w0 ldr w4, [x3, x1, lsl 2] str w6, [x5, x1, lsl 2] cmp w0, w4 bcc .L4 str w0, [x3, x1, lsl 2] add w2, w2, 3 cmp w7, 3 beq .L4 sxtw x1, w2 add w2, w2, w0 ldr w4, [x3, x1, lsl 2] str w2, [x5, x1, lsl 2] cmp w0, w4 bcc .L4 str w0, [x3, x1, lsl 2] .L4: mov w0, 0 ret .p2align 2,,3 .L6: mov w7, 4 b .L2 and for SVE: test4: adrp x2, .LANCHOR0 add x2, x2, :lo12:.LANCHOR0 add x5, x2, 3216 mov x3, 0 mov w1, 0 cntw x4 mov z1.s, w0 index z0.s, #0, #1 ptrue p1.b, all ptrue p0.s, all .p2align 3,,7 .L3: ld1w z2.s, p1/z, [x2, x3, lsl 2] add z3.s, z0.s, z1.s cmplo p2.s, p0/z, z1.s, z2.s b.any .L2 st1w z3.s, p1, [x5, x3, lsl 2] add w1, w1, 1 st1w z1.s, p1, [x2, x3, lsl 2] add x3, x3, x4 incw z0.s cmp w3, 803 bls .L3 .L5: mov w0, 0 ret .p2align 2,,3 .L2: cntw x5 mul w1, w1, w5 cbz w5, .L5 sxtw x1, w1 sub w5, w5, #1 add x5, x5, x1 add x6, x2, 3216 b .L6 .p2align 2,,3 .L14: str w0, [x2, x1, lsl 2] cmp x1, x5 beq .L5 mov x1, x4 .L6: ldr w3, [x2, x1, lsl 2] add w4, w0, w1 str w4, [x6, x1, lsl 2] add x4, x1, 1 cmp w0, w3 bcs .L14 mov w0, 0 ret On the workloads this work is based on we see between 2-3x performance uplift using this patch. Follow up plan: - Boolean vectorization has several shortcomings. I've filed PR110223 with the bigger ones that cause vectorization to fail with this patch. - SLP support. This is planned for GCC 15 as for majority of the cases build SLP itself fails. This means I'll need to spend time in making this more robust first. Additionally it requires: * Adding support for vectorizing CFG (gconds) * Support for CFG to differ between vector and scalar loops. Both of which would be disruptive to the tree and I suspect I'll be handling fallouts from this patch for a while. So I plan to work on the surrounding building blocks first for the remainder of the year. Bootstrapped Regtested on aarch64-none-linux-gnu and some issues so looking for some feedback. Also ran across various workloads and no issues. When closer to acceptance I will run on other targets as well and clean up related testsuite fallouts there. --- inline copy of patch -- -- --WYf58djMjHI13eUX Content-Type: text/plain; charset=utf-8 Content-Disposition: attachment; filename="rb17494.patch" --WYf58djMjHI13eUX--