From patchwork Wed Jun 28 13:44:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tamar Christina X-Patchwork-Id: 113894 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp8939004vqr; Wed, 28 Jun 2023 06:47:41 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6gMi+CfqaWa5vH7fCQVcPfLCyMzfZ54kxy7w22GBC1OGLWyjHYMQJBRw0GGXkYPHMzh6LA X-Received: by 2002:a17:907:26cc:b0:987:498a:87f6 with SMTP id bp12-20020a17090726cc00b00987498a87f6mr23466341ejc.34.1687960061110; Wed, 28 Jun 2023 06:47:41 -0700 (PDT) Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id m19-20020a1709066d1300b0098d85fee2e2si5463047ejr.608.2023.06.28.06.47.40 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 28 Jun 2023 06:47:41 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=uQSWGJao; arc=fail (signature failed); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 905AA3851ABA for ; Wed, 28 Jun 2023 13:46:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 905AA3851ABA DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1687959978; bh=sqcL001IzrvkYK+E4g/6YR27pN5BjfPsEZ6SyEwymJA=; h=Date:To:Cc:Subject:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=uQSWGJaop6rnOx567fi1wGcH8J0Z1V3h+IoQu95UAYwPGLwIHcK9mb8aP0h8p87gW cSuJ0uUjfRUL9W3gGnQQPqXYaYhCmQiBwJqgG0c54fp2GeXUkmsHGvL6QihpBWmUTx XSiH3obHFAajXFSKNwQKPKkxdvz0Bo5jFngnxhNQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-he1eur04on2078.outbound.protection.outlook.com [40.107.7.78]) by sourceware.org (Postfix) with ESMTPS id 224883856633 for ; Wed, 28 Jun 2023 13:45:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 224883856633 Received: from DUZPR01CA0156.eurprd01.prod.exchangelabs.com (2603:10a6:10:4bd::19) by AS8PR08MB7839.eurprd08.prod.outlook.com (2603:10a6:20b:52e::8) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6521.23; Wed, 28 Jun 2023 13:45:18 +0000 Received: from DBAEUR03FT045.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:4bd:cafe::68) by DUZPR01CA0156.outlook.office365.com (2603:10a6:10:4bd::19) 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:45:18 +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 DBAEUR03FT045.mail.protection.outlook.com (100.127.142.142) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6544.20 via Frontend Transport; Wed, 28 Jun 2023 13:45:17 +0000 Received: ("Tessian outbound c08fa2e31830:v142"); Wed, 28 Jun 2023 13:45:17 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: d4a5ca4e19d36ff0 X-CR-MTA-TID: 64aa7808 Received: from cf42b78647f4.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id D9E04FA6-3DB5-48F9-A6B0-08FE9549E5F6.1; Wed, 28 Jun 2023 13:45:10 +0000 Received: from EUR02-DB5-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id cf42b78647f4.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Wed, 28 Jun 2023 13:45:10 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=GZUulIa0Rrb3BQYDzNO09AkEEx3KZHpJHQ/mQikaYKAkVI21C+mz5+z/BguSh8VOgnXs+/XT5fn1ZBCLx6h7o86xrnq9Pv3CtDXefatB9PNr04Sn2jGn670RKdivd2Ro331niJi/g8kZmcMkTc/ZT/uvyC+1aze9dj6Z1OJCUkWPY7nh8DyfGDVs2fyBghJU/vEjtqJAAg450llo54bl9vTTG2Y8iOvN+c/geNrPsqWEAJRNwmMX9P5bWq/rm9DS7K9u9YT6so8X+hGntRZoa466ccNg/mF/l60dJL0ZLRh4kFRv76bEFM2DEzYchzZVQxQJKvOvUa5aVjOysUCzsA== 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=sqcL001IzrvkYK+E4g/6YR27pN5BjfPsEZ6SyEwymJA=; b=j53/RusRf/exkBtv/kU/efLWy+KljIWYcW1w0UNYk6AMZ3Pm/XE7cYGaA32GYfMBWRCVt12MlX44KyCvbmY6qUe8i5Rf7XH7AZGAB3rR9/IZPOS9eXLlwgL2DJNAczJopeIxABY6QfhPFt/LKMeqbONoqS9Em2t+93KRg2vr+HQ7oWYL2mYdawRkcwS4kz2++Jj3WOww4pDfQg8s9N1KydHOoCt2HqF9Pyg98MpjrSKjZPRYR1WI9NewzWjO2jC33S5fT3gN3GWVocvapiEXqjTjjEd0WJoIU2yKQsPpmaI0zJVHRbckslCvb1XruotFzClucbJWwVODp/4hZa8uHA== 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 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 GV2PR08MB8172.eurprd08.prod.outlook.com (2603:10a6:150:7c::14) 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:45:07 +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:45:07 +0000 Date: Wed, 28 Jun 2023 14:44:59 +0100 To: gcc-patches@gcc.gnu.org Cc: nd@arm.com, rguenther@suse.de, jlaw@ventanamicro.com Subject: [PATCH 7/19]middle-end: Refactor vectorizer loop conditionals and separate out IV to new variables Message-ID: Content-Disposition: inline In-Reply-To: X-ClientProxiedBy: SA9PR13CA0045.namprd13.prod.outlook.com (2603:10b6:806:22::20) To VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: VI1PR08MB5325:EE_|GV2PR08MB8172:EE_|DBAEUR03FT045:EE_|AS8PR08MB7839:EE_ X-MS-Office365-Filtering-Correlation-Id: e409d6d1-21bc-4cc5-0909-08db77dde8c6 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: NY4ThcaWT4tUNkkv0ee0rSLefW5Fj48YfQM7oP/51JfGHCY2EU2L4UWaRggMxA9RC1fIgSDA2qwGCrJmpZb/2N030Eu9Ts4+aWJFcIYWohwH7Y4uNKqrg3PmIFXXMBtXZOuzi6WiLQ08zrNj/PQWcq4dY0R4bU7GJqnplGvVbQLIlRQ5yl9zDskyWgSKQ/BIYNJNxTL3VEgFugSeGt3nEugCE9p4TZbwLq1DkgiWKdgz1eQEBi8QYyeNIzs+8+g2BYPyTntADz3Qkerv3MNpjGZ4+/TyoqFllXsUdtv9gAMC6Jy7/d/xZDOpuGVEEGs5nQeWFIeMnYolj7T7yAH9vk6WUDbHbHGth8giagxw8bprTJ2Rfm6L2+PKy51+wH3pnv2F3cfI6bWWrF5+PoHnJC7eX9JkZREE1mNkfE9+5HT+Jb9zgq+V2Ax1g10cjyWmnqnPNP8/wtTSFQ1Mje2pC04RDNBu2TjF/U02RjdfTcM1vrXDFUdPy+Y4WB/j3qLVy72cRd011STWz7JcF5sEZuJelGMIAl9w11C9nLTGLNgOoxrDyY0i8rrCey+UBI/o6aIsF+q3216MtHKm4EXMP0HAbJp4/JXimPLtStuoBgrt0oUl+vKmpuIYYgjcJxM4 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)(39860400002)(136003)(346002)(366004)(396003)(376002)(451199021)(2906002)(6486002)(33964004)(2616005)(4743002)(44144004)(6666004)(83380400001)(38100700002)(30864003)(186003)(6512007)(86362001)(26005)(41300700001)(478600001)(36756003)(66556008)(66946007)(316002)(4326008)(6916009)(66476007)(6506007)(44832011)(5660300002)(235185007)(8936002)(8676002)(2700100001); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: GV2PR08MB8172 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: DBAEUR03FT045.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: e3a113b9-8a1b-4790-f3cf-08db77dde242 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: lRokRPmx7S/RJsrclaCAPqNlGdF0buj+fV5ZN+9/F0Syhk2plrRhnUVQOysqzQq0kqMlJkXC2paWuz1PELErd6JdSaVWk6FfK5/xkMqq7q8815jKTAVd4oGwRWky5AHs2k7UVDtc7UJxvKxb2SeWIGo9NaduOyTWMbKVWQTEqAGl6f957IGBTP/KecmaiPJVHnKolbRJ5P2T9moeeSn+ZYgCe85S6P0zxrESG511ie2T2lawSZoeZmHbyQ8p0bnVHhfgKLTG6w8GwHiOF/1YDlblfRxQpWjWqyeYzP8nzvN5Nhq5lG9AZeFFzVj2epYGJEnzorm0t9rn2/lfbg4uq3uoI9B9r85M6LOEDY8C2at2Q6CeYrpf6dyTT0qn4jZ53nX22CNpQ+5IfVyH+Mm5HUkp949TvcdCGhkDHR6fC1p4IWoRm8Dm4J6Swf7thd4vyjaoi+rBQmF8FGggqJnG+9wSuPTDp+0MS6lbrEyq2p7GCA/CFSdABvZWwE3rkZE9N8c2YzhusNsurNrJb9vKhY1PqBeY1UkMndvwPqmP1pzcrCu1Zw4jHyCBBFAR+au9Wi+8rH0ww0bVvOXZTXTHCpgKc8qHVbmHIDRqq5EuJyTSjXhx+C/7MwIiZJOjy2S6Dma1MB8M4AUiC/m+PktPAAWJ2B3J2u3W2V552JLnMpMdn8W+nMCTk/rOlk/LMYL04IcVZ7VtpQKxBq/jWdKL7N3LRjCSeWf8A9BoJ0S/vMS7ntx8g5js3bTrmk/hIIvDAMr++SIxaiTaCZpIL8/vKQ== 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)(396003)(376002)(346002)(136003)(39860400002)(451199021)(46966006)(40470700004)(36840700001)(82310400005)(36860700001)(70206006)(40460700003)(36756003)(30864003)(5660300002)(44832011)(235185007)(356005)(86362001)(8936002)(8676002)(6916009)(41300700001)(316002)(4326008)(81166007)(70586007)(40480700001)(82740400003)(107886003)(47076005)(2906002)(26005)(478600001)(6506007)(186003)(2616005)(6512007)(4743002)(33964004)(44144004)(83380400001)(6486002)(336012)(6666004)(2700100001); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Jun 2023 13:45:17.9671 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: e409d6d1-21bc-4cc5-0909-08db77dde8c6 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: DBAEUR03FT045.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR08MB7839 X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, KAM_DMARC_NONE, KAM_LOTSOFHASH, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE, UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: , X-Patchwork-Original-From: Tamar Christina via Gcc-patches From: Tamar Christina Reply-To: Tamar Christina Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1769954408917297224?= X-GMAIL-MSGID: =?utf-8?q?1769954408917297224?= Hi All, This patch splits off the vectorizer's understanding of the main loop exit off from the normal loop infrastructure. Essentially we're relaxing the use of single_exit() in the vectorizer as we will no longer have a single single and need a well defined split between the main and secondary exits of loops for vectorization. These new values were added to the loop class even though they're only used by the vectorizer for a couple of reasons: - We need access to them in places where we have no loop_vinfo. - We only have a single loop_vinfo for each loop under consideration, however that same loop can have different copies, e.g. peeled/versioned copies or the scalar variant of the loop. For each of these we still need to be able to have a coherent exit definition. For these reason the placement in the loop class was the only way to keep the book keeping together with the loops and avoid possibly expensive lookups. For this version of the patch the `main` exit of a loop is defined as the exit that is closest to the loop latch. This is stored in vec_loop_iv. The remaining exits which are relevant for the vectorizer are stored inside vec_loop_alt_exits. Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. Ok for master? Thanks, Tamar gcc/ChangeLog: * cfgloop.cc (alloc_loop): Initialize vec_loop_iv. * cfgloop.h (class loop): Add vec_loop_iv and vec_loop_alt_exits. * doc/loop.texi: Document get_edge_condition. * tree-loop-distribution.cc (loop_distribution::distribute_loop): Initialize vec_loop_iv since loop distributions calls loop peeling which only understands vec_loop_iv now. * tree-scalar-evolution.cc (get_edge_condition): New. (get_loop_exit_condition): Refactor into get_edge_condition. * tree-scalar-evolution.h (get_edge_condition): New. * tree-vect-data-refs.cc (vect_enhance_data_refs_alignment): Update use of single_exit. * tree-vect-loop-manip.cc (vect_set_loop_condition_partial_vectors, vect_set_loop_condition_normal, vect_set_loop_condition, slpeel_tree_duplicate_loop_to_edge_cfg, slpeel_can_duplicate_loop_p, find_loop_location, vect_update_ivs_after_vectorizer, vect_gen_vector_loop_niters_mult_vf, find_guard_arg, vect_do_peeling): Replace usages of single_exit. (vec_init_exit_info): New. * tree-vect-loop.cc (vect_analyze_loop_form, vect_create_epilog_for_reduction, vectorizable_live_operation, scale_profile_for_vect_loop, vect_transform_loop): New. * tree-vectorizer.h (LOOP_VINFO_IV_EXIT, LOOP_VINFO_ALT_EXITS, vec_init_exit_info): New. --- inline copy of patch -- diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index e7ac2b5f3db55de3dbbab7bd2bfe08388f4ec533..cab82d7960e5be517bba2621f7f4888e7bf3c295 100644 --- diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index e7ac2b5f3db55de3dbbab7bd2bfe08388f4ec533..cab82d7960e5be517bba2621f7f4888e7bf3c295 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -272,6 +272,14 @@ public: the basic-block from being collected but its index can still be reused. */ basic_block former_header; + + /* The controlling loop IV for the current loop when vectorizing. This IV + controls the natural exits of the loop. */ + edge GTY ((skip (""))) vec_loop_iv; + + /* If the loop has multiple exits this structure contains the alternate + exits of the loop which are relevant for vectorization. */ + vec GTY ((skip (""))) vec_loop_alt_exits; }; /* Set if the loop is known to be infinite. */ diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc index ccda7415d7037e26048425b5d85f3633a39fd325..98123f7dce98227c8dffe4833e159fbb05596831 100644 --- a/gcc/cfgloop.cc +++ b/gcc/cfgloop.cc @@ -355,6 +355,7 @@ alloc_loop (void) loop->nb_iterations_upper_bound = 0; loop->nb_iterations_likely_upper_bound = 0; loop->nb_iterations_estimate = 0; + loop->vec_loop_iv = NULL; return loop; } diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi index b357e9de7bcb1898ab9dda25738b9f003ca6f9f5..4ba6bb2585c81f7af34943b0493b94d5c3a8bf60 100644 --- a/gcc/doc/loop.texi +++ b/gcc/doc/loop.texi @@ -212,6 +212,7 @@ relation, and breath-first search order, respectively. @code{NULL} if the loop has more than one exit. You can only use this function if @code{LOOPS_HAVE_RECORDED_EXITS} is used. @item @code{get_loop_exit_edges}: Enumerates the exit edges of a loop. +@item @code{get_edge_condition}: Get the condition belonging to an exit edge. @item @code{just_once_each_iteration_p}: Returns true if the basic block is executed exactly once during each iteration of a loop (that is, it does not belong to a sub-loop, and it dominates the latch of the loop). diff --git a/gcc/tree-loop-distribution.cc b/gcc/tree-loop-distribution.cc index cf7c197aaf7919a0ecd56a10db0a42f93707ca58..97879498db46dd3c34181ae9aa6e5476004dd5b5 100644 --- a/gcc/tree-loop-distribution.cc +++ b/gcc/tree-loop-distribution.cc @@ -3042,6 +3042,24 @@ loop_distribution::distribute_loop (class loop *loop, return 0; } + /* Loop distribution only does prologue peeling but we still need to + initialize loop exit information. However we only support single exits at + the moment. As such, should exit information not have been provided and we + have more than one exit, bail out. */ + if (!(loop->vec_loop_iv = single_exit (loop))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Loop %d not distributed: too many exits.\n", + loop->num); + + free_rdg (rdg); + loop_nest.release (); + free_data_refs (datarefs_vec); + delete ddrs_table; + return 0; + } + data_reference_p dref; for (i = 0; datarefs_vec.iterate (i, &dref); ++i) dref->aux = (void *) (uintptr_t) i; diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index c58a8a16e81573aada38e912b7c58b3e1b23b66d..2e83836911ec8e968e90cf9b489dc7fe121ff80e 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3. If not see extern tree number_of_latch_executions (class loop *); extern gcond *get_loop_exit_condition (const class loop *); +extern gcond *get_edge_condition (edge); extern void scev_initialize (void); extern bool scev_initialized_p (void); diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index ba47a684f4b373fb4f2dc16ddb8edb0ef39da6ed..af8be618b0748258132ccbef2d387bfddbe3c16b 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -1293,8 +1293,15 @@ scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr, gcond * get_loop_exit_condition (const class loop *loop) { + return get_edge_condition (single_exit (loop)); +} + +/* If the statement just before the EXIT_EDGE contains a condition then + return the condition, otherwise NULL. */ + +gcond * +get_edge_condition (edge exit_edge){ gcond *res = NULL; - edge exit_edge = single_exit (loop); if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, "(get_loop_exit_condition \n "); diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc index ebe93832b1e89120eab2fdac0fc30fe35c0356a2..fcc950f528b2d1e044be12424c2df11f692ee8ba 100644 --- a/gcc/tree-vect-data-refs.cc +++ b/gcc/tree-vect-data-refs.cc @@ -2070,7 +2070,8 @@ vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo) /* Check if we can possibly peel the loop. */ if (!vect_can_advance_ivs_p (loop_vinfo) - || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)) + || !slpeel_can_duplicate_loop_p (loop_vinfo, + LOOP_VINFO_IV_EXIT (loop_vinfo)) || loop->inner) do_peeling = false; diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc index 20f570e4a0d64610d7b63fe492eba5254ab5dc2c..299dfb75e3372b6a91637101b4bab0e82eb560ad 100644 --- a/gcc/tree-vect-loop-manip.cc +++ b/gcc/tree-vect-loop-manip.cc @@ -904,7 +904,7 @@ vect_set_loop_condition_partial_vectors (class loop *loop, add_header_seq (loop, header_seq); /* Get a boolean result that tells us whether to iterate. */ - edge exit_edge = single_exit (loop); + edge exit_edge = LOOP_VINFO_IV_EXIT (loop_vinfo); gcond *cond_stmt; if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo) && !LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)) @@ -935,7 +935,7 @@ vect_set_loop_condition_partial_vectors (class loop *loop, if (final_iv) { gassign *assign = gimple_build_assign (final_iv, orig_niters); - gsi_insert_on_edge_immediate (single_exit (loop), assign); + gsi_insert_on_edge_immediate (exit_edge, assign); } return cond_stmt; @@ -1183,7 +1183,8 @@ vect_set_loop_condition_partial_vectors_avx512 (class loop *loop, loop handles exactly VF scalars per iteration. */ static gcond * -vect_set_loop_condition_normal (class loop *loop, tree niters, tree step, +vect_set_loop_condition_normal (loop_vec_info loop_vinfo, + class loop *loop, tree niters, tree step, tree final_iv, bool niters_maybe_zero, gimple_stmt_iterator loop_cond_gsi) { @@ -1191,13 +1192,13 @@ vect_set_loop_condition_normal (class loop *loop, tree niters, tree step, gcond *cond_stmt; gcond *orig_cond; edge pe = loop_preheader_edge (loop); - edge exit_edge = single_exit (loop); + edge exit_edge = loop->vec_loop_iv; gimple_stmt_iterator incr_gsi; bool insert_after; enum tree_code code; tree niters_type = TREE_TYPE (niters); - orig_cond = get_loop_exit_condition (loop); + orig_cond = get_edge_condition (exit_edge); gcc_assert (orig_cond); loop_cond_gsi = gsi_for_stmt (orig_cond); @@ -1305,7 +1306,7 @@ vect_set_loop_condition_normal (class loop *loop, tree niters, tree step, if (final_iv) { gassign *assign; - edge exit = single_exit (loop); + edge exit = LOOP_VINFO_IV_EXIT (loop_vinfo); gcc_assert (single_pred_p (exit->dest)); tree phi_dest = integer_zerop (init) ? final_iv : copy_ssa_name (indx_after_incr); @@ -1353,7 +1354,7 @@ vect_set_loop_condition (class loop *loop, loop_vec_info loop_vinfo, bool niters_maybe_zero) { gcond *cond_stmt; - gcond *orig_cond = get_loop_exit_condition (loop); + gcond *orig_cond = get_edge_condition (loop->vec_loop_iv); gimple_stmt_iterator loop_cond_gsi = gsi_for_stmt (orig_cond); if (loop_vinfo && LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)) @@ -1370,7 +1371,8 @@ vect_set_loop_condition (class loop *loop, loop_vec_info loop_vinfo, loop_cond_gsi); } else - cond_stmt = vect_set_loop_condition_normal (loop, niters, step, final_iv, + cond_stmt = vect_set_loop_condition_normal (loop_vinfo, loop, niters, + step, final_iv, niters_maybe_zero, loop_cond_gsi); @@ -1439,6 +1441,69 @@ slpeel_duplicate_current_defs_from_edges (edge from, edge to) get_current_def (PHI_ARG_DEF_FROM_EDGE (from_phi, from))); } +/* When copies of the same loop are created the copies won't have any SCEV + information and so we can't determine what their exits are. However since + they are copies of an original loop the exits should be the same. + + I don't really like this, and think we need a different way, but I don't + know what. So sending this up so Richi can comment. */ + +void +vec_init_exit_info (class loop *loop) +{ + if (loop->vec_loop_iv) + return; + + auto_vec exits = get_loop_exit_edges (loop); + if (exits.is_empty ()) + return; + + if ((loop->vec_loop_iv = single_exit (loop))) + return; + + loop->vec_loop_alt_exits.create (exits.length () - 1); + + /* The main IV is to be determined by the block that's the first reachable + block from the latch. We cannot rely on the order the loop analysis + returns and we don't have any SCEV analysis on the loop. */ + auto_vec workset; + workset.safe_push (loop_latch_edge (loop)); + hash_set visited; + + while (!workset.is_empty ()) + { + edge e = workset.pop (); + if (visited.contains (e)) + continue; + + bool found_p = false; + for (edge ex : e->src->succs) + { + if (exits.contains (ex)) + { + found_p = true; + e = ex; + break; + } + } + + if (found_p) + { + loop->vec_loop_iv = e; + for (edge ex : exits) + if (e != ex) + loop->vec_loop_alt_exits.safe_push (ex); + return; + } + else + { + for (edge ex : e->src->preds) + workset.safe_insert (0, ex); + } + visited.add (e); + } + gcc_unreachable (); +} /* Given LOOP this function generates a new copy of it and puts it on E which is either the entry or exit of LOOP. If SCALAR_LOOP is @@ -1458,13 +1523,15 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, edge exit, new_exit; bool duplicate_outer_loop = false; - exit = single_exit (loop); + exit = loop->vec_loop_iv; at_exit = (e == exit); if (!at_exit && e != loop_preheader_edge (loop)) return NULL; if (scalar_loop == NULL) scalar_loop = loop; + else + vec_init_exit_info (scalar_loop); bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1); pbbs = bbs + 1; @@ -1490,13 +1557,17 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, bbs[0] = preheader; new_bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1); - exit = single_exit (scalar_loop); + exit = scalar_loop->vec_loop_iv; copy_bbs (bbs, scalar_loop->num_nodes + 1, new_bbs, &exit, 1, &new_exit, NULL, at_exit ? loop->latch : e->src, true); - exit = single_exit (loop); + exit = loop->vec_loop_iv; basic_block new_preheader = new_bbs[0]; + /* Record the new loop exit information. new_loop doesn't have SCEV data and + so we must initialize the exit information. */ + vec_init_exit_info (new_loop); + /* Before installing PHI arguments make sure that the edges into them match that of the scalar loop we analyzed. This makes sure the SLP tree matches up between the main vectorized @@ -1537,7 +1608,7 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, but LOOP will not. slpeel_update_phi_nodes_for_guard{1,2} expects the LOOP SSA_NAMEs (on the exit edge and edge from latch to header) to have current_def set, so copy them over. */ - slpeel_duplicate_current_defs_from_edges (single_exit (scalar_loop), + slpeel_duplicate_current_defs_from_edges (scalar_loop->vec_loop_iv, exit); slpeel_duplicate_current_defs_from_edges (EDGE_SUCC (scalar_loop->latch, 0), @@ -1696,11 +1767,12 @@ slpeel_add_loop_guard (basic_block guard_bb, tree cond, */ bool -slpeel_can_duplicate_loop_p (const class loop *loop, const_edge e) +slpeel_can_duplicate_loop_p (const loop_vec_info loop_vinfo, const_edge e) { - edge exit_e = single_exit (loop); + class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); + edge exit_e = LOOP_VINFO_IV_EXIT (loop_vinfo); edge entry_e = loop_preheader_edge (loop); - gcond *orig_cond = get_loop_exit_condition (loop); + gcond *orig_cond = get_edge_condition (exit_e); gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src); unsigned int num_bb = loop->inner? 5 : 2; @@ -1709,7 +1781,7 @@ slpeel_can_duplicate_loop_p (const class loop *loop, const_edge e) if (!loop_outer (loop) || loop->num_nodes != num_bb || !empty_block_p (loop->latch) - || !single_exit (loop) + || !LOOP_VINFO_IV_EXIT (loop_vinfo) /* Verify that new loop exit condition can be trivially modified. */ || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi)) || (e != exit_e && e != entry_e)) @@ -1722,7 +1794,7 @@ slpeel_can_duplicate_loop_p (const class loop *loop, const_edge e) return ret; } -/* Function vect_get_loop_location. +/* Function find_loop_location. Extract the location of the loop in the source code. If the loop is not well formed for vectorization, an estimated @@ -1739,11 +1811,19 @@ find_loop_location (class loop *loop) if (!loop) return dump_user_location_t (); - stmt = get_loop_exit_condition (loop); + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + /* We only care about the loop location, so use any exit with location + information. */ + for (edge e : get_loop_exit_edges (loop)) + { + stmt = get_edge_condition (e); - if (stmt - && LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION) - return stmt; + if (stmt + && LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION) + return stmt; + } + } /* If we got here the loop is probably not "well formed", try to estimate the loop location */ @@ -1962,7 +2042,8 @@ vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, gphi_iterator gsi, gsi1; class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); basic_block update_bb = update_e->dest; - basic_block exit_bb = single_exit (loop)->dest; + + basic_block exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; /* Make sure there exists a single-predecessor exit bb: */ gcc_assert (single_pred_p (exit_bb)); @@ -2529,10 +2610,9 @@ vect_gen_vector_loop_niters_mult_vf (loop_vec_info loop_vinfo, { /* We should be using a step_vector of VF if VF is variable. */ int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo).to_constant (); - class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); tree type = TREE_TYPE (niters_vector); tree log_vf = build_int_cst (type, exact_log2 (vf)); - basic_block exit_bb = single_exit (loop)->dest; + basic_block exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; gcc_assert (niters_vector_mult_vf_ptr != NULL); tree niters_vector_mult_vf = fold_build2 (LSHIFT_EXPR, type, @@ -2559,7 +2639,7 @@ find_guard_arg (class loop *loop, class loop *epilog ATTRIBUTE_UNUSED, gphi *lcssa_phi) { gphi_iterator gsi; - edge e = single_exit (loop); + edge e = loop->vec_loop_iv; gcc_assert (single_pred_p (e->dest)); for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -3328,8 +3408,8 @@ vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1, if (epilog_peeling) { - e = single_exit (loop); - gcc_checking_assert (slpeel_can_duplicate_loop_p (loop, e)); + e = LOOP_VINFO_IV_EXIT (loop_vinfo); + gcc_checking_assert (slpeel_can_duplicate_loop_p (loop_vinfo, e)); /* Peel epilog and put it on exit edge of loop. If we are vectorizing said epilog then we should use a copy of the main loop as a starting @@ -3419,8 +3499,8 @@ vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1, { guard_cond = fold_build2 (EQ_EXPR, boolean_type_node, niters, niters_vector_mult_vf); - guard_bb = single_exit (loop)->dest; - guard_to = split_edge (single_exit (epilog)); + guard_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; + guard_to = split_edge (epilog->vec_loop_iv); guard_e = slpeel_add_loop_guard (guard_bb, guard_cond, guard_to, skip_vector ? anchor : guard_bb, prob_epilog.invert (), @@ -3428,7 +3508,7 @@ vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1, if (vect_epilogues) epilogue_vinfo->skip_this_loop_edge = guard_e; slpeel_update_phi_nodes_for_guard2 (loop, epilog, guard_e, - single_exit (epilog)); + epilog->vec_loop_iv); /* Only need to handle basic block before epilog loop if it's not the guard_bb, which is the case when skip_vector is true. */ if (guard_bb != bb_before_epilog) diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc index 0a03f56aae7b51fb4c5ce0e49d96888bae634ef7..0bca5932d237cf1cfbbb48271db3f4430672b5dc 100644 --- a/gcc/tree-vect-loop.cc +++ b/gcc/tree-vect-loop.cc @@ -1641,6 +1641,13 @@ vect_analyze_loop_form (class loop *loop, vect_loop_form_info *info) { DUMP_VECT_SCOPE ("vect_analyze_loop_form"); + vec_init_exit_info (loop); + if (!loop->vec_loop_iv) + return opt_result::failure_at (vect_location, + "not vectorized:" + " could not determine main exit from" + " loop with multiple exits.\n"); + /* Different restrictions apply when we are considering an inner-most loop, vs. an outer (nested) loop. (FORNOW. May want to relax some of these restrictions in the future). */ @@ -3025,9 +3032,8 @@ start_over: if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, "epilog loop required\n"); if (!vect_can_advance_ivs_p (loop_vinfo) - || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo), - single_exit (LOOP_VINFO_LOOP - (loop_vinfo)))) + || !slpeel_can_duplicate_loop_p (loop_vinfo, + LOOP_VINFO_IV_EXIT (loop_vinfo))) { ok = opt_result::failure_at (vect_location, "not vectorized: can't create required " @@ -5964,7 +5970,7 @@ vect_create_epilog_for_reduction (loop_vec_info loop_vinfo, Store them in NEW_PHIS. */ if (double_reduc) loop = outer_loop; - exit_bb = single_exit (loop)->dest; + exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; exit_gsi = gsi_after_labels (exit_bb); reduc_inputs.create (slp_node ? vec_num : ncopies); for (unsigned i = 0; i < vec_num; i++) @@ -5980,7 +5986,7 @@ vect_create_epilog_for_reduction (loop_vec_info loop_vinfo, phi = create_phi_node (new_def, exit_bb); if (j) def = gimple_get_lhs (STMT_VINFO_VEC_STMTS (rdef_info)[j]); - SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def); + SET_PHI_ARG_DEF (phi, LOOP_VINFO_IV_EXIT (loop_vinfo)->dest_idx, def); new_def = gimple_convert (&stmts, vectype, new_def); reduc_inputs.quick_push (new_def); } @@ -10301,12 +10307,12 @@ vectorizable_live_operation (vec_info *vinfo, lhs' = new_tree; */ class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); - basic_block exit_bb = single_exit (loop)->dest; + basic_block exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; gcc_assert (single_pred_p (exit_bb)); tree vec_lhs_phi = copy_ssa_name (vec_lhs); gimple *phi = create_phi_node (vec_lhs_phi, exit_bb); - SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, vec_lhs); + SET_PHI_ARG_DEF (phi, LOOP_VINFO_IV_EXIT (loop_vinfo)->dest_idx, vec_lhs); gimple_seq stmts = NULL; tree new_tree; @@ -10829,7 +10835,8 @@ scale_profile_for_vect_loop (class loop *loop, unsigned vf) scale_loop_frequencies (loop, p); } - edge exit_e = single_exit (loop); + edge exit_e = loop->vec_loop_iv; + exit_e->probability = profile_probability::always () / (new_est_niter + 1); edge exit_l = single_pred_edge (loop->latch); @@ -11177,7 +11184,7 @@ vect_transform_loop (loop_vec_info loop_vinfo, gimple *loop_vectorized_call) /* Make sure there exists a single-predecessor exit bb. Do this before versioning. */ - edge e = single_exit (loop); + edge e = LOOP_VINFO_IV_EXIT (loop_vinfo); if (! single_pred_p (e->dest)) { split_loop_exit_edge (e, true); diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index a36974c2c0d2103b0a2d0397d06ab84dace08129..bd5eceb5da7a45ef036cd14609ebe091799320bf 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -917,6 +917,8 @@ public: /* Access Functions. */ #define LOOP_VINFO_LOOP(L) (L)->loop +#define LOOP_VINFO_IV_EXIT(L) (L)->loop->vec_loop_iv +#define LOOP_VINFO_ALT_EXITS(L) (L)->loop->vec_loop_alt_exits #define LOOP_VINFO_BBS(L) (L)->bbs #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1 #define LOOP_VINFO_NITERS(L) (L)->num_iters @@ -2162,6 +2164,7 @@ extern void vect_prepare_for_masked_peels (loop_vec_info); extern dump_user_location_t find_loop_location (class loop *); extern bool vect_can_advance_ivs_p (loop_vec_info); extern void vect_update_inits_of_drs (loop_vec_info, tree, tree_code); +extern void vec_init_exit_info (class loop *); /* In tree-vect-stmts.cc. */ extern tree get_related_vectype_for_scalar_type (machine_mode, tree, --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -272,6 +272,14 @@ public: the basic-block from being collected but its index can still be reused. */ basic_block former_header; + + /* The controlling loop IV for the current loop when vectorizing. This IV + controls the natural exits of the loop. */ + edge GTY ((skip (""))) vec_loop_iv; + + /* If the loop has multiple exits this structure contains the alternate + exits of the loop which are relevant for vectorization. */ + vec GTY ((skip (""))) vec_loop_alt_exits; }; /* Set if the loop is known to be infinite. */ diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc index ccda7415d7037e26048425b5d85f3633a39fd325..98123f7dce98227c8dffe4833e159fbb05596831 100644 --- a/gcc/cfgloop.cc +++ b/gcc/cfgloop.cc @@ -355,6 +355,7 @@ alloc_loop (void) loop->nb_iterations_upper_bound = 0; loop->nb_iterations_likely_upper_bound = 0; loop->nb_iterations_estimate = 0; + loop->vec_loop_iv = NULL; return loop; } diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi index b357e9de7bcb1898ab9dda25738b9f003ca6f9f5..4ba6bb2585c81f7af34943b0493b94d5c3a8bf60 100644 --- a/gcc/doc/loop.texi +++ b/gcc/doc/loop.texi @@ -212,6 +212,7 @@ relation, and breath-first search order, respectively. @code{NULL} if the loop has more than one exit. You can only use this function if @code{LOOPS_HAVE_RECORDED_EXITS} is used. @item @code{get_loop_exit_edges}: Enumerates the exit edges of a loop. +@item @code{get_edge_condition}: Get the condition belonging to an exit edge. @item @code{just_once_each_iteration_p}: Returns true if the basic block is executed exactly once during each iteration of a loop (that is, it does not belong to a sub-loop, and it dominates the latch of the loop). diff --git a/gcc/tree-loop-distribution.cc b/gcc/tree-loop-distribution.cc index cf7c197aaf7919a0ecd56a10db0a42f93707ca58..97879498db46dd3c34181ae9aa6e5476004dd5b5 100644 --- a/gcc/tree-loop-distribution.cc +++ b/gcc/tree-loop-distribution.cc @@ -3042,6 +3042,24 @@ loop_distribution::distribute_loop (class loop *loop, return 0; } + /* Loop distribution only does prologue peeling but we still need to + initialize loop exit information. However we only support single exits at + the moment. As such, should exit information not have been provided and we + have more than one exit, bail out. */ + if (!(loop->vec_loop_iv = single_exit (loop))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Loop %d not distributed: too many exits.\n", + loop->num); + + free_rdg (rdg); + loop_nest.release (); + free_data_refs (datarefs_vec); + delete ddrs_table; + return 0; + } + data_reference_p dref; for (i = 0; datarefs_vec.iterate (i, &dref); ++i) dref->aux = (void *) (uintptr_t) i; diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index c58a8a16e81573aada38e912b7c58b3e1b23b66d..2e83836911ec8e968e90cf9b489dc7fe121ff80e 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3. If not see extern tree number_of_latch_executions (class loop *); extern gcond *get_loop_exit_condition (const class loop *); +extern gcond *get_edge_condition (edge); extern void scev_initialize (void); extern bool scev_initialized_p (void); diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index ba47a684f4b373fb4f2dc16ddb8edb0ef39da6ed..af8be618b0748258132ccbef2d387bfddbe3c16b 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -1293,8 +1293,15 @@ scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr, gcond * get_loop_exit_condition (const class loop *loop) { + return get_edge_condition (single_exit (loop)); +} + +/* If the statement just before the EXIT_EDGE contains a condition then + return the condition, otherwise NULL. */ + +gcond * +get_edge_condition (edge exit_edge){ gcond *res = NULL; - edge exit_edge = single_exit (loop); if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, "(get_loop_exit_condition \n "); diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc index ebe93832b1e89120eab2fdac0fc30fe35c0356a2..fcc950f528b2d1e044be12424c2df11f692ee8ba 100644 --- a/gcc/tree-vect-data-refs.cc +++ b/gcc/tree-vect-data-refs.cc @@ -2070,7 +2070,8 @@ vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo) /* Check if we can possibly peel the loop. */ if (!vect_can_advance_ivs_p (loop_vinfo) - || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)) + || !slpeel_can_duplicate_loop_p (loop_vinfo, + LOOP_VINFO_IV_EXIT (loop_vinfo)) || loop->inner) do_peeling = false; diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc index 20f570e4a0d64610d7b63fe492eba5254ab5dc2c..299dfb75e3372b6a91637101b4bab0e82eb560ad 100644 --- a/gcc/tree-vect-loop-manip.cc +++ b/gcc/tree-vect-loop-manip.cc @@ -904,7 +904,7 @@ vect_set_loop_condition_partial_vectors (class loop *loop, add_header_seq (loop, header_seq); /* Get a boolean result that tells us whether to iterate. */ - edge exit_edge = single_exit (loop); + edge exit_edge = LOOP_VINFO_IV_EXIT (loop_vinfo); gcond *cond_stmt; if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo) && !LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)) @@ -935,7 +935,7 @@ vect_set_loop_condition_partial_vectors (class loop *loop, if (final_iv) { gassign *assign = gimple_build_assign (final_iv, orig_niters); - gsi_insert_on_edge_immediate (single_exit (loop), assign); + gsi_insert_on_edge_immediate (exit_edge, assign); } return cond_stmt; @@ -1183,7 +1183,8 @@ vect_set_loop_condition_partial_vectors_avx512 (class loop *loop, loop handles exactly VF scalars per iteration. */ static gcond * -vect_set_loop_condition_normal (class loop *loop, tree niters, tree step, +vect_set_loop_condition_normal (loop_vec_info loop_vinfo, + class loop *loop, tree niters, tree step, tree final_iv, bool niters_maybe_zero, gimple_stmt_iterator loop_cond_gsi) { @@ -1191,13 +1192,13 @@ vect_set_loop_condition_normal (class loop *loop, tree niters, tree step, gcond *cond_stmt; gcond *orig_cond; edge pe = loop_preheader_edge (loop); - edge exit_edge = single_exit (loop); + edge exit_edge = loop->vec_loop_iv; gimple_stmt_iterator incr_gsi; bool insert_after; enum tree_code code; tree niters_type = TREE_TYPE (niters); - orig_cond = get_loop_exit_condition (loop); + orig_cond = get_edge_condition (exit_edge); gcc_assert (orig_cond); loop_cond_gsi = gsi_for_stmt (orig_cond); @@ -1305,7 +1306,7 @@ vect_set_loop_condition_normal (class loop *loop, tree niters, tree step, if (final_iv) { gassign *assign; - edge exit = single_exit (loop); + edge exit = LOOP_VINFO_IV_EXIT (loop_vinfo); gcc_assert (single_pred_p (exit->dest)); tree phi_dest = integer_zerop (init) ? final_iv : copy_ssa_name (indx_after_incr); @@ -1353,7 +1354,7 @@ vect_set_loop_condition (class loop *loop, loop_vec_info loop_vinfo, bool niters_maybe_zero) { gcond *cond_stmt; - gcond *orig_cond = get_loop_exit_condition (loop); + gcond *orig_cond = get_edge_condition (loop->vec_loop_iv); gimple_stmt_iterator loop_cond_gsi = gsi_for_stmt (orig_cond); if (loop_vinfo && LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)) @@ -1370,7 +1371,8 @@ vect_set_loop_condition (class loop *loop, loop_vec_info loop_vinfo, loop_cond_gsi); } else - cond_stmt = vect_set_loop_condition_normal (loop, niters, step, final_iv, + cond_stmt = vect_set_loop_condition_normal (loop_vinfo, loop, niters, + step, final_iv, niters_maybe_zero, loop_cond_gsi); @@ -1439,6 +1441,69 @@ slpeel_duplicate_current_defs_from_edges (edge from, edge to) get_current_def (PHI_ARG_DEF_FROM_EDGE (from_phi, from))); } +/* When copies of the same loop are created the copies won't have any SCEV + information and so we can't determine what their exits are. However since + they are copies of an original loop the exits should be the same. + + I don't really like this, and think we need a different way, but I don't + know what. So sending this up so Richi can comment. */ + +void +vec_init_exit_info (class loop *loop) +{ + if (loop->vec_loop_iv) + return; + + auto_vec exits = get_loop_exit_edges (loop); + if (exits.is_empty ()) + return; + + if ((loop->vec_loop_iv = single_exit (loop))) + return; + + loop->vec_loop_alt_exits.create (exits.length () - 1); + + /* The main IV is to be determined by the block that's the first reachable + block from the latch. We cannot rely on the order the loop analysis + returns and we don't have any SCEV analysis on the loop. */ + auto_vec workset; + workset.safe_push (loop_latch_edge (loop)); + hash_set visited; + + while (!workset.is_empty ()) + { + edge e = workset.pop (); + if (visited.contains (e)) + continue; + + bool found_p = false; + for (edge ex : e->src->succs) + { + if (exits.contains (ex)) + { + found_p = true; + e = ex; + break; + } + } + + if (found_p) + { + loop->vec_loop_iv = e; + for (edge ex : exits) + if (e != ex) + loop->vec_loop_alt_exits.safe_push (ex); + return; + } + else + { + for (edge ex : e->src->preds) + workset.safe_insert (0, ex); + } + visited.add (e); + } + gcc_unreachable (); +} /* Given LOOP this function generates a new copy of it and puts it on E which is either the entry or exit of LOOP. If SCALAR_LOOP is @@ -1458,13 +1523,15 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, edge exit, new_exit; bool duplicate_outer_loop = false; - exit = single_exit (loop); + exit = loop->vec_loop_iv; at_exit = (e == exit); if (!at_exit && e != loop_preheader_edge (loop)) return NULL; if (scalar_loop == NULL) scalar_loop = loop; + else + vec_init_exit_info (scalar_loop); bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1); pbbs = bbs + 1; @@ -1490,13 +1557,17 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, bbs[0] = preheader; new_bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1); - exit = single_exit (scalar_loop); + exit = scalar_loop->vec_loop_iv; copy_bbs (bbs, scalar_loop->num_nodes + 1, new_bbs, &exit, 1, &new_exit, NULL, at_exit ? loop->latch : e->src, true); - exit = single_exit (loop); + exit = loop->vec_loop_iv; basic_block new_preheader = new_bbs[0]; + /* Record the new loop exit information. new_loop doesn't have SCEV data and + so we must initialize the exit information. */ + vec_init_exit_info (new_loop); + /* Before installing PHI arguments make sure that the edges into them match that of the scalar loop we analyzed. This makes sure the SLP tree matches up between the main vectorized @@ -1537,7 +1608,7 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, but LOOP will not. slpeel_update_phi_nodes_for_guard{1,2} expects the LOOP SSA_NAMEs (on the exit edge and edge from latch to header) to have current_def set, so copy them over. */ - slpeel_duplicate_current_defs_from_edges (single_exit (scalar_loop), + slpeel_duplicate_current_defs_from_edges (scalar_loop->vec_loop_iv, exit); slpeel_duplicate_current_defs_from_edges (EDGE_SUCC (scalar_loop->latch, 0), @@ -1696,11 +1767,12 @@ slpeel_add_loop_guard (basic_block guard_bb, tree cond, */ bool -slpeel_can_duplicate_loop_p (const class loop *loop, const_edge e) +slpeel_can_duplicate_loop_p (const loop_vec_info loop_vinfo, const_edge e) { - edge exit_e = single_exit (loop); + class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); + edge exit_e = LOOP_VINFO_IV_EXIT (loop_vinfo); edge entry_e = loop_preheader_edge (loop); - gcond *orig_cond = get_loop_exit_condition (loop); + gcond *orig_cond = get_edge_condition (exit_e); gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src); unsigned int num_bb = loop->inner? 5 : 2; @@ -1709,7 +1781,7 @@ slpeel_can_duplicate_loop_p (const class loop *loop, const_edge e) if (!loop_outer (loop) || loop->num_nodes != num_bb || !empty_block_p (loop->latch) - || !single_exit (loop) + || !LOOP_VINFO_IV_EXIT (loop_vinfo) /* Verify that new loop exit condition can be trivially modified. */ || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi)) || (e != exit_e && e != entry_e)) @@ -1722,7 +1794,7 @@ slpeel_can_duplicate_loop_p (const class loop *loop, const_edge e) return ret; } -/* Function vect_get_loop_location. +/* Function find_loop_location. Extract the location of the loop in the source code. If the loop is not well formed for vectorization, an estimated @@ -1739,11 +1811,19 @@ find_loop_location (class loop *loop) if (!loop) return dump_user_location_t (); - stmt = get_loop_exit_condition (loop); + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + /* We only care about the loop location, so use any exit with location + information. */ + for (edge e : get_loop_exit_edges (loop)) + { + stmt = get_edge_condition (e); - if (stmt - && LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION) - return stmt; + if (stmt + && LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION) + return stmt; + } + } /* If we got here the loop is probably not "well formed", try to estimate the loop location */ @@ -1962,7 +2042,8 @@ vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, gphi_iterator gsi, gsi1; class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); basic_block update_bb = update_e->dest; - basic_block exit_bb = single_exit (loop)->dest; + + basic_block exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; /* Make sure there exists a single-predecessor exit bb: */ gcc_assert (single_pred_p (exit_bb)); @@ -2529,10 +2610,9 @@ vect_gen_vector_loop_niters_mult_vf (loop_vec_info loop_vinfo, { /* We should be using a step_vector of VF if VF is variable. */ int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo).to_constant (); - class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); tree type = TREE_TYPE (niters_vector); tree log_vf = build_int_cst (type, exact_log2 (vf)); - basic_block exit_bb = single_exit (loop)->dest; + basic_block exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; gcc_assert (niters_vector_mult_vf_ptr != NULL); tree niters_vector_mult_vf = fold_build2 (LSHIFT_EXPR, type, @@ -2559,7 +2639,7 @@ find_guard_arg (class loop *loop, class loop *epilog ATTRIBUTE_UNUSED, gphi *lcssa_phi) { gphi_iterator gsi; - edge e = single_exit (loop); + edge e = loop->vec_loop_iv; gcc_assert (single_pred_p (e->dest)); for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -3328,8 +3408,8 @@ vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1, if (epilog_peeling) { - e = single_exit (loop); - gcc_checking_assert (slpeel_can_duplicate_loop_p (loop, e)); + e = LOOP_VINFO_IV_EXIT (loop_vinfo); + gcc_checking_assert (slpeel_can_duplicate_loop_p (loop_vinfo, e)); /* Peel epilog and put it on exit edge of loop. If we are vectorizing said epilog then we should use a copy of the main loop as a starting @@ -3419,8 +3499,8 @@ vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1, { guard_cond = fold_build2 (EQ_EXPR, boolean_type_node, niters, niters_vector_mult_vf); - guard_bb = single_exit (loop)->dest; - guard_to = split_edge (single_exit (epilog)); + guard_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; + guard_to = split_edge (epilog->vec_loop_iv); guard_e = slpeel_add_loop_guard (guard_bb, guard_cond, guard_to, skip_vector ? anchor : guard_bb, prob_epilog.invert (), @@ -3428,7 +3508,7 @@ vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1, if (vect_epilogues) epilogue_vinfo->skip_this_loop_edge = guard_e; slpeel_update_phi_nodes_for_guard2 (loop, epilog, guard_e, - single_exit (epilog)); + epilog->vec_loop_iv); /* Only need to handle basic block before epilog loop if it's not the guard_bb, which is the case when skip_vector is true. */ if (guard_bb != bb_before_epilog) diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc index 0a03f56aae7b51fb4c5ce0e49d96888bae634ef7..0bca5932d237cf1cfbbb48271db3f4430672b5dc 100644 --- a/gcc/tree-vect-loop.cc +++ b/gcc/tree-vect-loop.cc @@ -1641,6 +1641,13 @@ vect_analyze_loop_form (class loop *loop, vect_loop_form_info *info) { DUMP_VECT_SCOPE ("vect_analyze_loop_form"); + vec_init_exit_info (loop); + if (!loop->vec_loop_iv) + return opt_result::failure_at (vect_location, + "not vectorized:" + " could not determine main exit from" + " loop with multiple exits.\n"); + /* Different restrictions apply when we are considering an inner-most loop, vs. an outer (nested) loop. (FORNOW. May want to relax some of these restrictions in the future). */ @@ -3025,9 +3032,8 @@ start_over: if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, "epilog loop required\n"); if (!vect_can_advance_ivs_p (loop_vinfo) - || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo), - single_exit (LOOP_VINFO_LOOP - (loop_vinfo)))) + || !slpeel_can_duplicate_loop_p (loop_vinfo, + LOOP_VINFO_IV_EXIT (loop_vinfo))) { ok = opt_result::failure_at (vect_location, "not vectorized: can't create required " @@ -5964,7 +5970,7 @@ vect_create_epilog_for_reduction (loop_vec_info loop_vinfo, Store them in NEW_PHIS. */ if (double_reduc) loop = outer_loop; - exit_bb = single_exit (loop)->dest; + exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; exit_gsi = gsi_after_labels (exit_bb); reduc_inputs.create (slp_node ? vec_num : ncopies); for (unsigned i = 0; i < vec_num; i++) @@ -5980,7 +5986,7 @@ vect_create_epilog_for_reduction (loop_vec_info loop_vinfo, phi = create_phi_node (new_def, exit_bb); if (j) def = gimple_get_lhs (STMT_VINFO_VEC_STMTS (rdef_info)[j]); - SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def); + SET_PHI_ARG_DEF (phi, LOOP_VINFO_IV_EXIT (loop_vinfo)->dest_idx, def); new_def = gimple_convert (&stmts, vectype, new_def); reduc_inputs.quick_push (new_def); } @@ -10301,12 +10307,12 @@ vectorizable_live_operation (vec_info *vinfo, lhs' = new_tree; */ class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); - basic_block exit_bb = single_exit (loop)->dest; + basic_block exit_bb = LOOP_VINFO_IV_EXIT (loop_vinfo)->dest; gcc_assert (single_pred_p (exit_bb)); tree vec_lhs_phi = copy_ssa_name (vec_lhs); gimple *phi = create_phi_node (vec_lhs_phi, exit_bb); - SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, vec_lhs); + SET_PHI_ARG_DEF (phi, LOOP_VINFO_IV_EXIT (loop_vinfo)->dest_idx, vec_lhs); gimple_seq stmts = NULL; tree new_tree; @@ -10829,7 +10835,8 @@ scale_profile_for_vect_loop (class loop *loop, unsigned vf) scale_loop_frequencies (loop, p); } - edge exit_e = single_exit (loop); + edge exit_e = loop->vec_loop_iv; + exit_e->probability = profile_probability::always () / (new_est_niter + 1); edge exit_l = single_pred_edge (loop->latch); @@ -11177,7 +11184,7 @@ vect_transform_loop (loop_vec_info loop_vinfo, gimple *loop_vectorized_call) /* Make sure there exists a single-predecessor exit bb. Do this before versioning. */ - edge e = single_exit (loop); + edge e = LOOP_VINFO_IV_EXIT (loop_vinfo); if (! single_pred_p (e->dest)) { split_loop_exit_edge (e, true); diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index a36974c2c0d2103b0a2d0397d06ab84dace08129..bd5eceb5da7a45ef036cd14609ebe091799320bf 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -917,6 +917,8 @@ public: /* Access Functions. */ #define LOOP_VINFO_LOOP(L) (L)->loop +#define LOOP_VINFO_IV_EXIT(L) (L)->loop->vec_loop_iv +#define LOOP_VINFO_ALT_EXITS(L) (L)->loop->vec_loop_alt_exits #define LOOP_VINFO_BBS(L) (L)->bbs #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1 #define LOOP_VINFO_NITERS(L) (L)->num_iters @@ -2162,6 +2164,7 @@ extern void vect_prepare_for_masked_peels (loop_vec_info); extern dump_user_location_t find_loop_location (class loop *); extern bool vect_can_advance_ivs_p (loop_vec_info); extern void vect_update_inits_of_drs (loop_vec_info, tree, tree_code); +extern void vec_init_exit_info (class loop *); /* In tree-vect-stmts.cc. */ extern tree get_related_vectype_for_scalar_type (machine_mode, tree,