From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-AM5-obe.outbound.protection.outlook.com (mail-eopbgr00056.outbound.protection.outlook.com [40.107.0.56]) by sourceware.org (Postfix) with ESMTPS id 2FFCF398B400 for ; Fri, 25 Sep 2020 14:28:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 2FFCF398B400 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=Tamar.Christina@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=KaeF7BRIA8pqHbeHsbsPOqZkl6JeLnIG5w7R+xyV7W4=; b=xsV+Adg+BQa305oAEYMkcxDEUVfCBdkjc5v38nGj3/HEHOsyjt7keFBSoLaL6pkULags7wiQ0z50ep3BhjRJ+g9pOehGRoQqNS5gCUTDONpGKsgDbPHb3eUXjE4mh3SYQ2tjnMZchE2v7XZYgk6Ujt7cJvKH6qLFMyYvc4GmIi4= Received: from AM6P192CA0096.EURP192.PROD.OUTLOOK.COM (2603:10a6:209:8d::37) by AM8PR08MB5585.eurprd08.prod.outlook.com (2603:10a6:20b:1c5::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3391.13; Fri, 25 Sep 2020 14:28:06 +0000 Received: from VE1EUR03FT022.eop-EUR03.prod.protection.outlook.com (2603:10a6:209:8d:cafe::15) by AM6P192CA0096.outlook.office365.com (2603:10a6:209:8d::37) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3412.22 via Frontend Transport; Fri, 25 Sep 2020 14:28:06 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; gcc.gnu.org; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;gcc.gnu.org; dmarc=bestguesspass 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; Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by VE1EUR03FT022.mail.protection.outlook.com (10.152.18.64) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3412.21 via Frontend Transport; Fri, 25 Sep 2020 14:28:05 +0000 Received: ("Tessian outbound 7fc8f57bdedc:v64"); Fri, 25 Sep 2020 14:28:05 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 4f76d2a5fc9f5bce X-CR-MTA-TID: 64aa7808 Received: from 4c64cc75e31f.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 04EBDA76-FB99-4D86-A2BC-08C659E59B58.1; Fri, 25 Sep 2020 14:27:59 +0000 Received: from EUR03-DB5-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 4c64cc75e31f.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Fri, 25 Sep 2020 14:27:59 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Ouli7vm3dNX6YR0TiheLiwIaOv1Kou3LswrrcTnRaQZarlnpaaYLbrjJrfzcHspd3VLuGxESNXA95O90cTDYdDZhvoVZxVkgDT1ZukCC76c8OoM369EuXFNpe7SVLppnIQcLWao37iH339jVCOQCOe1i7ecjTO7JXOPjXQf5IPTIND2wj6JAsK/mOSbFwRgzSR9frE6YCYHf+QGL/+TUzK0ZPtHJv/DmPwnOgAEqR8RUV2nSshluuZt/DC5qAOEqgFpsf2eRPW6ZoF6RLjTYhWsjeYIoHLrWJEDKjFSyMfTaINt8kmqX2Hk0tGDklZLltIhzp+KTZlkIS/v32mbbBg== 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-SenderADCheck; bh=KaeF7BRIA8pqHbeHsbsPOqZkl6JeLnIG5w7R+xyV7W4=; b=HpVBbGFjW3LCCdbnSvIkx/8NdEp8ygxNmeRT9BKFE26TU+/a/W46cCoo3Sxp1yfRfR5evwxxs5zN3J3aP5lK9x04fcr9OBNDoRqBDFhfaxF6uco43V/Jz80GLSzgZXPinfFLKSqG6gFcRyUvUhjG+AgyrjgzH6VUWJP1mDmO8NThZq8KifTW68wQNHxxBi24lQSW4aymUnsXaUYDoUwG+KLHFrwMRYhYQiKFYCiMGf3DTHWdADf+dlWgApy9XTWbSy7toPlFvXgl+miJtGeq1N21biKn1XPw48UqY90gKiO1SAxA7ExQ0DLyWkgJeCYqwJVRgSFYsTvHzbz96WdnsQ== 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=KaeF7BRIA8pqHbeHsbsPOqZkl6JeLnIG5w7R+xyV7W4=; b=xsV+Adg+BQa305oAEYMkcxDEUVfCBdkjc5v38nGj3/HEHOsyjt7keFBSoLaL6pkULags7wiQ0z50ep3BhjRJ+g9pOehGRoQqNS5gCUTDONpGKsgDbPHb3eUXjE4mh3SYQ2tjnMZchE2v7XZYgk6Ujt7cJvKH6qLFMyYvc4GmIi4= Authentication-Results-Original: gcc.gnu.org; dkim=none (message not signed) header.d=none;gcc.gnu.org; dmarc=none action=none header.from=arm.com; Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by VE1PR08MB5678.eurprd08.prod.outlook.com (2603:10a6:800:1a0::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3391.11; Fri, 25 Sep 2020 14:27:58 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::d0e7:49cd:4dae:a2a2]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::d0e7:49cd:4dae:a2a2%7]) with mapi id 15.20.3412.024; Fri, 25 Sep 2020 14:27:58 +0000 Date: Fri, 25 Sep 2020 15:27:55 +0100 From: Tamar Christina To: gcc-patches@gcc.gnu.org Cc: nd@arm.com, rguenther@suse.de, ook@ucw.cz Subject: [PATCH v2 3/16]middle-end Add basic SLP pattern matching scaffolding. Message-ID: <20200925142753.GA13692@arm.com> Content-Type: multipart/mixed; boundary="LZvS9be/3tNcYl/X" Content-Disposition: inline User-Agent: Mutt/1.9.4 (2018-02-28) X-ClientProxiedBy: LO2P265CA0066.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:60::30) To VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 Received: from arm.com (217.140.106.53) by LO2P265CA0066.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:60::30) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3412.21 via Frontend Transport; Fri, 25 Sep 2020 14:27:57 +0000 X-Originating-IP: [217.140.106.53] X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-HT: Tenant X-MS-Office365-Filtering-Correlation-Id: 8914fb13-1e7c-493d-a726-08d8615f37e6 X-MS-TrafficTypeDiagnostic: VE1PR08MB5678:|AM8PR08MB5585: X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true NoDisclaimer: true X-MS-Oob-TLC-OOBClassifiers: OLM:9508;OLM:9508; X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: c9ZXeu/fM2yJojM4egdyVE7GSZR6KfrhnloU0wAPPtFBsNIFS1Z3o/fOA0z8R3zJvBQEAYyjJO2/EWLMfQkMzIVqNMS2kDXSgHSiAUvgsCoVg092XJT5OsaR6wTdu0d2zA2y0o2kGGKt37Z2YDaxNHsTcF++2s7HidLfpK3QSFEc16pvgYCcyglbvLmkXtGVEkRV5Li/Rt2dUJH1m2S0khCUUs53WgHTmjmUenPZkB/3lZ0rIMrKfkXcfOg7A9ytIFVe+MjQNBQ+hczIusqWdZTYagms/QGbni2Morz6PWxoQmxLxppfwuhVT+E+nghsYTSRZ89Y3G7NKKm920Fu9j4S8lOXkfEpqx6D6jdRWG6acCM1H9Y7pMwaWVW6q/lxT5SuHJ3+W7qKtovHVX4FkPadhnG1L0ABwvCZQ2u4X3A= 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:(4636009)(396003)(366004)(136003)(39860400002)(346002)(376002)(8936002)(1076003)(55016002)(33656002)(8886007)(66946007)(66556008)(86362001)(66616009)(83380400001)(36756003)(66476007)(478600001)(6916009)(235185007)(44144004)(5660300002)(16526019)(186003)(4743002)(4326008)(33964004)(52116002)(44832011)(7696005)(316002)(2616005)(26005)(2906002)(8676002)(956004)(2700100001); DIR:OUT; SFP:1101; X-MS-Exchange-AntiSpam-MessageData: SqhKOtXzpmStlDLpRQ8UTtZ2VeuaAub+vuUjjP2XdkVfQWzsLLWOfYoB3IsHgUiPQnArW6centCWEsctrWKfdY5wBzTS84oXCcS4xRy/PoSbk8lagvCdgEvsibvizMdqmQGpfTA7BHRGNEalHeR7XUoKVVT4j9Gz9dQ97rbmUqufDmgc9j+bvswi0KY2jKo6g1nvCPIaQER7uimGHIEsI9lYOeEKjhzGZ3N/qXG4xfwgcofMaxFe7VacXx4Buvw1N5HtVCBGoBTxkfnwRWsVN5JfaoZXWU5oVz13StdW04x2a0SIM9+Y0NIKA/fH4NcW3quoiss1wHvPryAsYl4i2LWLwCJqAiW8itHsYhq8YaKUagWjFSkpCsLRe4etn/ohGm0dPY6ZyCuPANqmQVpt4rjny5lzw5lscUA+Euzafzihp2fIiTTzxKlUhqT3VNfqYRhN4j7+0LlnKZIehxnH7WucHsYrbvnPsXcSEnr9SPLT+UScgb9kiu+9WwxNftax2jMmPHch+WyrM0HXHGVe5FqApnuoFX6fU9b0hkzTw8bduQrOIL2jgz4asOKgQsNFVqAF+LL3XMdXwSM+P2GVXMQKLUcLRe9euPChZejmqK6+GRZMkNLL1h0cYQ16wuxwpg+QTKtXTWQHPDEZKoJ4jA== X-MS-Exchange-Transport-Forked: True X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB5678 Original-Authentication-Results: gcc.gnu.org; dkim=none (message not signed) header.d=none;gcc.gnu.org; dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: VE1EUR03FT022.eop-EUR03.prod.protection.outlook.com X-MS-Office365-Filtering-Correlation-Id-Prvs: da61759d-4163-49db-9ecb-08d8615f32f9 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: dF0QZTVrGa8bdVOo3/lyCFORSHqZev/Kv2xB99WT83ZS2cbfeom68lM/1EJjZGsykDGY4m0z6Zj/hcprXSY7/vyK+UWlQMueLRsiOaUPD+q+oBvhTmwusyZYx0y5Ixm5+q560JCqjJoOhCpKPQTdQiGG1fuAFNsMdJ/KOHBbXkBdund+hbdPeWbC8pjxsyfaF8Qn6rryae24wMybvOKWMTRBIXRsweA9D5WOjT+falsCnZCbhadw5yJEU2RtUGXXDN/DvG3pnCQyjyq2HmiqnCO8qyxQKYyITlrX2lPNDomz74ky7+vsCm/kcyFwJfWVZl8RKYNd04GeCzMfod7sfKoiTPhJrJVqBbVFKMVPsQtXaxhsxEhA9kE+j6Py01p0ZmBM42/QN51pL6sfFvSCpIEVmpV4SKwixu74xW1jBFg= 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:(4636009)(396003)(346002)(136003)(376002)(39860400002)(46966005)(70586007)(83380400001)(86362001)(70206006)(235185007)(36756003)(1076003)(16526019)(8676002)(82310400003)(2906002)(33656002)(44144004)(4326008)(33964004)(7696005)(478600001)(82740400003)(356005)(6916009)(55016002)(66616009)(186003)(5660300002)(2616005)(956004)(81166007)(47076004)(36906005)(316002)(336012)(44832011)(8936002)(4743002)(8886007)(26005)(2700100001); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Sep 2020 14:28:05.8638 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 8914fb13-1e7c-493d-a726-08d8615f37e6 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: VE1EUR03FT022.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM8PR08MB5585 X-Spam-Status: No, score=-9.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, INDUSTRIAL_BODY, INDUSTRIAL_SUBJECT, KAM_ASCII_DIVIDERS, KAM_LOTSOFHASH, KAM_SHORT, MSGID_FROM_MTA_HEADER, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_PASS, TXREP, UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 25 Sep 2020 14:28:11 -0000 --LZvS9be/3tNcYl/X Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Hi All, This patch adds the basic infrastructure for doing pattern matching on SLP trees. This is done immediately after the SLP tree creation because it can change the shape of the tree in radical ways and so we would like to do it before any analysis is performed on the tree. A new file tree-vect-slp-patterns.c is added which contains all the code for pattern matching on SLP trees. This cover letter is short because the changes are heavily commented. All pattern matchers need to implement the abstract type VectPatternMatch. The VectSimplePatternMatch abstract class provides some default functionality for pattern matchers that need to rebuild nodes. The pattern matcher requires if replacing a statement in a node, that ALL statements be replaced. Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. Ok for master? Thanks, Tamar gcc/ChangeLog: * Makefile.in (tree-vect-slp-patterns.o): New. * doc/passes.texi: Update documentation. * tree-vect-slp.c (vect_match_slp_patterns_2, vect_match_slp_patterns): New. (vect_analyze_slp_instance): Call pattern matcher. * tree-vectorizer.h (class VectPatternMatch, class VectPattern): New. * tree-vect-slp-patterns.c: New file. -- --LZvS9be/3tNcYl/X Content-Type: text/x-diff; charset=utf-8 Content-Disposition: attachment; filename="rb13507.patch" diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 9c6c1c93b976aaf350cc1f9b3bdc538308fdf08b..936202b73696c8529b32c05b2356c7316fabc542 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1638,6 +1638,7 @@ OBJS = \ tree-vect-loop.o \ tree-vect-loop-manip.o \ tree-vect-slp.o \ + tree-vect-slp-patterns.o \ tree-vectorizer.o \ tree-vector-builder.o \ tree-vrp.o \ diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi index a5ae4143a8c1293e674b499120372ee5fe5c412b..c86df5cd843084a5b7933ef99a23386891a7b0c1 100644 --- a/gcc/doc/passes.texi +++ b/gcc/doc/passes.texi @@ -709,7 +709,8 @@ loop. The pass is implemented in @file{tree-vectorizer.c} (the main driver), @file{tree-vect-loop.c} and @file{tree-vect-loop-manip.c} (loop specific parts and general loop utilities), @file{tree-vect-slp} (loop-aware SLP -functionality), @file{tree-vect-stmts.c} and @file{tree-vect-data-refs.c}. +functionality), @file{tree-vect-stmts.c}, @file{tree-vect-data-refs.c} and +@file{tree-vect-slp-patterns.c} containing the SLP pattern matcher. Analysis of data references is in @file{tree-data-ref.c}. SLP Vectorization. This pass performs vectorization of straight-line code. The diff --git a/gcc/tree-vect-slp-patterns.c b/gcc/tree-vect-slp-patterns.c new file mode 100644 index 0000000000000000000000000000000000000000..f605f68d2a14c4bf4941f97b7c1d57f6acb5ffb1 --- /dev/null +++ b/gcc/tree-vect-slp-patterns.c @@ -0,0 +1,310 @@ +/* SLP - Pattern matcher on SLP trees + Copyright (C) 2020 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "target.h" +#include "rtl.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "optabs-tree.h" +#include "insn-config.h" +#include "recog.h" /* FIXME: for insn_data */ +#include "fold-const.h" +#include "stor-layout.h" +#include "gimple-iterator.h" +#include "cfgloop.h" +#include "tree-vectorizer.h" +#include "langhooks.h" +#include "gimple-walk.h" +#include "dbgcnt.h" +#include "tree-vector-builder.h" +#include "vec-perm-indices.h" +#include "gimple-fold.h" +#include "internal-fn.h" + +/* SLP Pattern matching mechanism. + + This extension to the SLP vectorizer allows one to transform the generated SLP + tree based on any pattern. The difference between this and the normal vect + pattern matcher is that unlike the former, this matcher allows you to match + with instructions that do not belong to the same SSA dominator graph. + + The only requirement that this pattern matcher has is that you are only + only allowed to either match an entire group or none. + + As an example, the following simple loop: + + double a[restrict N]; double b[restrict N]; double c[restrict N]; + + for (int i=0; i < N; i+=2) + { + c[i] = a[i] - b[i+1]; + c[i+1] = a[i+1] + b[i]; + } + + which represents a complex addition on with a rotation of 90* around the + argand plane. i.e. if `a` and `b` were complex numbers then this would be the + same as `a + (b * I)`. + + Here the expressions for `c[i]` and `c[i+1]` are independent but have to be + both recognized in order for the pattern to work. As an SLP tree this is + represented as + + +--------------------------------+ + | stmt 0 *_9 = _10; | + | stmt 1 *_15 = _16; | + +--------------------------------+ + | + | + v + +--------------------------------+ + | stmt 0 _10 = _4 - _8; | + | stmt 1 _16 = _12 + _14; | + | lane permutation { 0[0] 1[1] } | + +--------------------------------+ + | | + | | + | | + +-----+ | | +-----+ + | | | | | | + +-----| { } |<-----+ +----->| { } --------+ + | | | +------------------| | | + | +-----+ | +-----+ | + | | | | + | | | | + | +------|------------------+ | + | | | | + v v v v + +--------------------------+ +--------------------------------+ + | stmt 0 _8 = *_7; | | stmt 0 _4 = *_3; | + | stmt 1 _14 = *_13; | | stmt 1 _12 = *_11; | + | load permutation { 1 0 } | | load permutation { 0 1 } | + +--------------------------+ +--------------------------------+ + + The pattern matcher allows you to replace both statements 0 and 1 or none at + all. You are also allowed to replace and match on any number of nodes. + + The pattern matcher uses a sliding window to handle unrolled cases. Every + pattern has to declare the number of statements that they consume. The + pattern matcher uses this to incrementally ask if the pattern can be applied. + This is done using the method `matches ()`. + + If the pattern can be applied a VecPatternMatch is returned which contains all + state information on where the match was found. This is stored in a list of + operations to perform. If the match cannot be applied then the current + pattern is aborted and no changes made to the tree. + + The pattern matcher has two modes: + + 1) pre-order traversal is used to perform a check to see if the pattern can be + applied or not. If the pattern can be applied then a second step is + performed that allows the pattern to rewrite it's children. This step is + required because the application of a pattern can change the layout of the + tree which affects the nodes that are still to be matched. This is + performed using `validate_p ()`. + + 2) post-order traversal is used to actually perform the rewriting of the + matches found earlier. This is done by calling `build ()` on all matches + that were found earlier. + + The pattern matcher currently only allows you to perform replacements to + internal functions. + + To add a new pattern, implement the VectPattern class and add the type to + slp_patterns. */ + +/* VectSimplePatternMatch holds contextual information about a single match + found in the SLP tree. The use of the class is to allow you to defer + performing any modifications to the SLP tree until they are to be done. By + calling build () the modifications are done in-place as to allow also re- + writing of the root node. */ + +class VectSimplePatternMatch : public VectPatternMatch +{ + protected: + uint8_t m_arity; + vec m_ifn_args; + internal_fn m_ifn; + vec_info *m_vinfo; + int m_idx, m_num_args; + tree m_type, m_vectype; + slp_tree m_node; + int m_pos; + + public: + VectSimplePatternMatch (uint8_t arity, vec ifn_args, + internal_fn ifn, vec_info *vinfo, int idx, + slp_tree node, tree type, tree vectype, + int num_args) + { + /* Number of statements the pattern matches against. */ + this->m_arity = arity; + + /* Arguments to be used when building the new stmts using the IFN. */ + this->m_ifn_args = ifn_args.copy (); + + /* The IFN to create the new statements with. */ + this->m_ifn = ifn; + + /* The vectorization information for the current loop. */ + this->m_vinfo = vinfo; + + /* The index in the sliding window where the statements were matched. */ + this->m_idx = idx; + + /* The number of arguments required to create the new IFN. */ + this->m_num_args = num_args; + + /* The original scalar type of the statement being replaced. */ + this->m_type = type; + + /* The vector type to create the IFN for. */ + this->m_vectype = vectype; + + /* The node that contains the statement that is being replaced. */ + this->m_node = node; + + /* The current position inside the arity of the statement being replaced. + generally the match can be cached and re-used for multiple stmts. */ + this->m_pos = 0; + + gcc_assert ((unsigned)(num_args * arity) == ifn_args.length ()); + } + + uint8_t get_arity () + { + return this->m_arity; + } + + internal_fn get_IFN () + { + return this->m_ifn; + } + + const vec get_IFN_args () + { + return this->m_ifn_args; + } + + /* Create a replacement pattern statement for STMT_INFO and inserts the new + statement into NODE. The statement is created as call to internal + function IFN with arguments ARGS. The arity of IFN needs to match the + amount of elements in ARGS. The scalar type of the statement as TYPE and + the corresponding vector type VECTYPE. These two types are used to + construct the new vector only replacement pattern statement. + + Futhermore the new pattern is also added to the vectorization information + structure VINFO and the old statement STMT_INFO is marked as unused while + the new statement is marked as used and the number of SLP uses of the new + statement is incremented. + + The newly created SLP nodes are marked as SLP only and will be dissolved + if SLP is aborted. + + The newly created gimple call is returned and the BB remains unchanged. + */ + + gcall *build () + { + stmt_vec_info stmt_info; + + /* Check if this call was made too often. */ + if (this->m_pos >= this->m_arity) + return NULL; + + auto_vec args; + args.create (this->m_num_args); + + /* Create the argument set for use by gimple_build_call_internal_vec. */ + stmt_vec_info arg; + for (int i = 0; i < this->m_num_args; i++) + { + arg = this->m_ifn_args[i + (this->m_pos * this->m_num_args)]; + args.quick_push (gimple_get_lhs (STMT_VINFO_STMT (arg))); + } + + /* Check to see if we haven't created all the nodes already. */ + if (args.is_empty ()) + return NULL; + + /* Calculate the location of the statement in NODE to replace. */ + int entry = this->m_idx - (this->m_arity - 1) + this->m_pos; + stmt_info = SLP_TREE_SCALAR_STMTS (this->m_node)[entry]; + + /* Create the new pattern statements. */ + gcall *call_stmt = gimple_build_call_internal_vec (this->m_ifn, args); + tree var = make_temp_ssa_name (this->m_type, call_stmt, "slp_patt"); + gimple* old_stmt = STMT_VINFO_STMT (stmt_info); + gimple_call_set_lhs (call_stmt, var); + gimple_set_location (call_stmt, gimple_location (old_stmt)); + gimple_call_set_nothrow (call_stmt, true); + + /* Adjust the book-keeping for the new and old statements for use during SLP. + This is required to get the right VF and statement during SLP analysis. + These changes are created after relevancy has been set for the nodes as + such we need to manually update them. Any changes will be undone if SLP + is cancelled. */ + stmt_vec_info call_stmt_info = this->m_vinfo->add_stmt (call_stmt); + vect_mark_pattern_stmts (this->m_vinfo, stmt_info, call_stmt, + this->m_vectype); + + /* We have to explicitly mark the old statement as unused because during + statement analysis the original and new pattern statement may require + different level of unrolling. As an example add/sub when vectorized + without a pattern requires 4 copies, whereas with a COMPLEX_ADD pattern + this only requires 2 copies and the two statement will be treated as + hand unrolled. That means that the analysis won't happen as it'll find + a mismatch. So we don't analyze the old statement and if we end up + needing it, e.g. SLP fails then we have to quickly re-analyze it. */ + STMT_VINFO_RELEVANT (stmt_info) = vect_unused_in_scope; + STMT_VINFO_SLP_VECT_ONLY (call_stmt_info) = true; + STMT_VINFO_RELATED_STMT (call_stmt_info) = stmt_info; + + /* Since we are replacing all the statements in the group with the same + thing it doesn't really matter. So just set it every time a new stmt + is created. */ + SLP_TREE_SCALAR_STMTS (this->m_node)[entry] = call_stmt_info; + SLP_TREE_REPRESENTATIVE (this->m_node) = call_stmt_info; + SLP_TREE_CODE (this->m_node) = gimple_expr_code (call_stmt);; + + this->m_pos++; + return call_stmt; + } + + ~VectSimplePatternMatch () + { + this->m_ifn_args.release (); + } +}; + +#define SLP_PATTERN(x) &x::create +VectPatternDecl slp_patterns[] +{ + /* For least amount of back-tracking and more efficient matching + order patterns from the largest to the smallest. Especially if they + overlap in what they can detect. */ +}; +#undef SLP_PATTERN + +size_t num__slp_patterns = sizeof(slp_patterns)/sizeof(VectPatternDecl); diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c index 01189d44d892fc42b132bbb7de1c471df45518ae..947b031a6d492e6a02621dbcf41ba60d96c606f0 100644 --- a/gcc/tree-vect-slp.c +++ b/gcc/tree-vect-slp.c @@ -2055,6 +2055,192 @@ calculate_unrolling_factor (poly_uint64 nunits, unsigned int group_size) return exact_div (common_multiple (nunits, group_size), group_size); } +/* Helper function of vect_match_slp_patterns. + + Attempts to match the given pattern PATT_INFO against the slp tree rooted in + NODE using VINFO and GROUP_SIZE. + + If matching is successful the value in NODE is updated and returned, if not + then it is returned unchanged. */ + +static bool +vect_match_slp_patterns_2 (slp_tree node, vec_info *vinfo, + unsigned int group_size, VectPatternDecl patt_fn, + poly_uint64 *max_nunits, bool *matches, + unsigned *npermutes, unsigned *tree_size, + scalar_stmts_to_slp_tree_map_t * bst_map) +{ + unsigned i; + stmt_vec_info stmt_info; + if (!node) + return false; + + vec scalar_stmts = SLP_TREE_SCALAR_STMTS (node); + bool found_p = false, found_rec_p = false; + VectPattern *pattern = patt_fn (node, vinfo); + uint8_t n = pattern->get_arity (); + + if (group_size % n != 0) + { + delete pattern; + return false; + } + + /* The data dependency orderings will force the nodes to be created in the + order of their data flow. Which means since we're matching specific + patterns in particular order we only have to do a linear scan here to match + the same instruction multiple times. The group size doesn't have to be + constrained. */ + + for (unsigned i = n - 1; i < scalar_stmts.length (); i += n) + { + stmt_info = scalar_stmts[i]; + + if (gimple_assign_load_p (STMT_VINFO_STMT (stmt_info)) + || gimple_store_p (STMT_VINFO_STMT (stmt_info)) + || gimple_assign_cast_p (STMT_VINFO_STMT (stmt_info))) + break; + + stmt_vec_info *stmt_infos = scalar_stmts.begin () + (i - (n - 1)); + + gcc_assert (stmt_infos); + + if (!pattern->matches (stmt_infos, i)) + { + /* We can only do replacements for entire groups, we must replace all + statements in a node as the argument list/children may not have + equal height then. Operations that don't rewrite the arguments + may be safe to do, so perhaps paramatrise it. */ + + found_p = false; + break; + } + + tree type = gimple_expr_type (STMT_VINFO_STMT (stmt_info)); + tree vectype = get_vectype_for_scalar_type (vinfo, type, node); + + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, + "Found %s pattern in SLP tree\n", + pattern->get_name ()); + + if (pattern->is_optab_supported_p (vectype, OPTIMIZE_FOR_SPEED)) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, + "Target supports %s vectorization with mode %T\n", + internal_fn_name (pattern->get_last_ifn ()), + vectype); + + found_p = true; + } + else + { + if (dump_enabled_p ()) + { + if (!vectype) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "Target does not support vector type for " + "%T\n", type); + else + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "Target does not support %s for " + "vector type %T\n", + internal_fn_name (pattern->get_last_ifn ()), + vectype); + } + found_p = false; + } + } + + if (found_p) + { + /* Find which nodes should be the children of the new node. */ + + if (!pattern->validate_p (max_nunits, matches, + npermutes, tree_size, bst_map)) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, + "transformation for %s not valid due to post " + "condition\n", internal_fn_name (pattern->get_last_ifn ())); + found_p = false; + } + } + + /* Perform recursive matching, it's important to do this after matching things + in the current node as the matches here may re-order the nodes below it. + As such the pattern that needs to be subsequently match may change. */ + + if (SLP_TREE_CHILDREN (node).exists ()) { + slp_tree child; + FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) + found_rec_p |= vect_match_slp_patterns_2 (child, vinfo, group_size, + patt_fn, max_nunits, matches, + npermutes, tree_size, bst_map); + } + + if (found_p) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, "Creating vec patterns\n"); + + while (gcall* call_stmt = pattern->build ()) + { + if (dump_enabled_p ()) + dump_printf_loc (MSG_NOTE, vect_location, "\t %p stmt: %G", + node, call_stmt); + } + + vect_mark_slp_stmts_relevant (node); + } + + delete pattern; + return found_p | found_rec_p; +} + +/* Applies pattern matching to the given SLP tree rooted in NODE using vec_info + VINFO and group size GROUP_SIZE. + + The modified tree is returned. Patterns are tried in order and multiple + patterns may match. If the permutes need to be cancelled then + CANCEL_PERMUTE is set. */ + +static bool +vect_match_slp_patterns (slp_tree node, vec_info *vinfo, + unsigned int group_size, poly_uint64 *max_nunits, + bool *matches, unsigned *npermutes, + unsigned *tree_size, + scalar_stmts_to_slp_tree_map_t * bst_map) +{ + DUMP_VECT_SCOPE ("vect_match_slp_patterns"); + bool found_p = false; + + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_NOTE, vect_location, "-- before patt match --\n"); + vect_print_slp_graph (MSG_NOTE, vect_location, node); + dump_printf_loc (MSG_NOTE, vect_location, "-- end patt --\n"); + } + + for (unsigned x = 0; x < num__slp_patterns; x++) + found_p |= vect_match_slp_patterns_2 (node, vinfo, group_size, + slp_patterns[x], max_nunits, matches, + npermutes, tree_size, bst_map); + + /* TODO: Remove in final version, only here for generating debug dot graphs + from SLP tree. */ + + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_NOTE, vect_location, "-- start dot --\n"); + vect_print_slp_graph (MSG_NOTE, vect_location, node); + dump_printf_loc (MSG_NOTE, vect_location, "-- end dot --\n"); + } + + return found_p; +} + /* Analyze an SLP instance starting from a group of grouped stores. Call vect_build_slp_tree to build a tree of packed stmts if possible. Return FALSE if it's impossible to SLP any stmt in the loop. */ @@ -2192,6 +2378,17 @@ vect_analyze_slp_instance (vec_info *vinfo, &tree_size, bst_map); if (node != NULL) { + /* Temporarily allow add_stmt calls again. */ + vinfo->stmt_vec_info_ro = false; + + /* See if any patterns can be found in the constructed SLP tree + before we do any analysis on it. */ + vect_match_slp_patterns (node, vinfo, group_size, &max_nunits, + matches, &npermutes, &tree_size, bst_map); + + /* After this no more add_stmt calls are allowed. */ + vinfo->stmt_vec_info_ro = true; + /* Calculate the unrolling factor based on the smallest type. */ poly_uint64 unrolling_factor = calculate_unrolling_factor (max_nunits, group_size); diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index 79926f1a43534635ddca85556a928e364022c40a..95bbf13b1c733c07b7deb8515c1b17c6979cff21 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -26,6 +26,7 @@ typedef class _stmt_vec_info *stmt_vec_info; #include "tree-data-ref.h" #include "tree-hash-traits.h" #include "target.h" +#include "internal-fn.h" /* Used for naming of new temporaries. */ @@ -2100,6 +2101,99 @@ typedef hash_map , slp_tree, simple_hashmap_traits > scalar_stmts_to_slp_tree_map_t; +/* SLP Pattern matcher types, tree-vect-slp-patterns.c. */ + +class VectPatternMatch +{ + public: + virtual gcall *build () = 0; + virtual internal_fn get_IFN () = 0; + virtual const vec get_IFN_args () = 0; + virtual uint8_t get_arity () = 0; + virtual ~VectPatternMatch () {}; +}; + +class VectPattern +{ + protected: + uint8_t m_arity; + uint8_t m_num_args; + internal_fn m_last_ifn; + int m_last_idx; + slp_tree m_node; + vec_info *m_vinfo; + vec m_matches; + VectPattern (slp_tree node, vec_info *vinfo) + { + this->m_last_ifn = IFN_LAST; + this->m_node = node; + this->m_vinfo = vinfo; + this->m_matches.create (0); + this->m_curr_match = 0; + } + + private: + unsigned m_curr_match; + + public: + static VectPattern* create (slp_tree node, vec_info *vinfo); + virtual bool matches (stmt_vec_info *stmts, int idx) = 0; + + virtual const char* get_name () = 0; + virtual ~VectPattern () + { + int i; + VectPatternMatch *match; + FOR_EACH_VEC_ELT (this->m_matches, i, match) + delete match; + this->m_matches.release (); + } + + virtual gcall *build () + { + if (this->m_curr_match >= this->m_matches.length ()) + return NULL; + + gcall *entry = + this->m_matches[this->m_curr_match]->build (); + + if (entry) + return entry; + + this->m_curr_match++; + return build (); + } + + virtual bool validate_p (poly_uint64 *, bool *, unsigned *, unsigned *, + scalar_stmts_to_slp_tree_map_t *) + { + return true; + } + + virtual uint8_t get_arity () + { + return this->m_arity; + } + + virtual bool is_optab_supported_p ( tree vectype, optimization_type opt_type) + { + if (!vectype) + return false; + + return direct_internal_fn_supported_p (this->m_last_ifn, vectype, + opt_type); + } + + internal_fn get_last_ifn () + { + return this->m_last_ifn; + } +}; + +typedef VectPattern* (*VectPatternDecl) (slp_tree, vec_info *); +extern VectPatternDecl slp_patterns[]; +extern size_t num__slp_patterns; + extern void vect_free_slp_tree (slp_tree node); --LZvS9be/3tNcYl/X--