From patchwork Fri Nov 11 13:46:25 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Carlotti X-Patchwork-Id: 18742 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp750487wru; Fri, 11 Nov 2022 05:51:30 -0800 (PST) X-Google-Smtp-Source: AA0mqf4rT1k1j5Dns1N7QU2SvlltsPhhO9e6xngZAsswJkhf90W62wj545+tLOfsHvt6tTirZt1O X-Received: by 2002:a17:907:c683:b0:787:8884:78df with SMTP id ue3-20020a170907c68300b00787888478dfmr1851940ejc.246.1668174690118; Fri, 11 Nov 2022 05:51:30 -0800 (PST) Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id xh10-20020a170906da8a00b0077e04f856a2si2164150ejb.541.2022.11.11.05.51.29 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 11 Nov 2022 05:51:30 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=pJOcr1rF; arc=fail (signature failed); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 B87FA3858033 for ; Fri, 11 Nov 2022 13:51:28 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B87FA3858033 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1668174688; bh=RqtOi7Gadx7ikaItofBYHINiwWQKpAIm9hIHZ0t1SEg=; h=Date:To:Subject:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=pJOcr1rFGAtR94DjSgHuAqFKaQdOW+hG3UfNriBRSaUWP7VylBbCK3CDhn8rl8t1C EKgM+uKurxF4/gtRmMt5i3oOFRMTFPE0Tlch+VU/Q4bIfKb/kULqa+IwDMhOrioRin tRCpPMPjhDLGNbov17uWxIckCADc76DiuKLkxqlM= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from EUR01-DB5-obe.outbound.protection.outlook.com (mail-eopbgr150058.outbound.protection.outlook.com [40.107.15.58]) by sourceware.org (Postfix) with ESMTPS id 7BB603858D1E for ; Fri, 11 Nov 2022 13:50:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7BB603858D1E ARC-Seal: i=2; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=pass; b=c5ilo1o9C7H/8czb8e5rB50ztR8EW+ydpaiywQgxgp6U1v2K9nryb6JHp+CECs1WYJjRz+hYmYeo5HCMAP4+lg81hTUnDGLRRPTHhNibO6BUBmHchXkY2IwDgpiezafCYsShq+kvscMFh115DnaDPZLFXZfochUtUpvu2dq1X+mP3+NVjfDSVM12kyYzGrZm3Yf28fEc1L6xq+zOsbjjTZWhlgy3ZkSQn/moOaa6UZG6IU7nzI70KriwrjGbyHNWatYT5bz4sqCD+lbRrSvg7jYkU3E1u1IkkonOpDoHWxjtGORK0O4BERouhluZlsA1NQJNLDLQjRQ1Lz/VmDBMmA== 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=RqtOi7Gadx7ikaItofBYHINiwWQKpAIm9hIHZ0t1SEg=; b=j5CiTOr6s6+B++3HnI5OoV/Axrgjf3zpIQCgvtAZjr3NBQdaFpkIc+JhQRKj0fLBtec1kWmy+uOmhbh/krXNzg7RsCaHCOE7p/7j9juMKCYkHxPepr8vo+9Vm1HfdQSkkEkBaU9fdct9VTL4fcr7ayEGtXNrCkwzCD6GAy0M3gTBWZ8B37qFzLvNOIqlSzyf24S/LoZxP4mIBk4xZnsMsdqXE3nJVL29HGGNaKa/F13wHaAcqM3S3JRQUFijGkIdq8ycB38ZWSVApTmp0IU1B12NBjwPZVlLoQ63XsFXUHHNBkeiDUOK6uCQCWKoqJ7IXMYDiG+e9hfEkkIh81dFfQ== 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]) Received: from DB6P18901CA0012.EURP189.PROD.OUTLOOK.COM (2603:10a6:4:16::22) by AS8PR08MB10152.eurprd08.prod.outlook.com (2603:10a6:20b:63e::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5746.28; Fri, 11 Nov 2022 13:50:37 +0000 Received: from DBAEUR03FT003.eop-EUR03.prod.protection.outlook.com (2603:10a6:4:16:cafe::b3) by DB6P18901CA0012.outlook.office365.com (2603:10a6:4:16::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5813.13 via Frontend Transport; Fri, 11 Nov 2022 13:50:37 +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 DBAEUR03FT003.mail.protection.outlook.com (100.127.142.89) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5813.12 via Frontend Transport; Fri, 11 Nov 2022 13:50:37 +0000 Received: ("Tessian outbound aeae1c7b66fd:v130"); Fri, 11 Nov 2022 13:50:37 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 6ec3167a3b9b29de X-CR-MTA-TID: 64aa7808 Received: from 12bd5c436923.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 834F99B2-A3E5-4114-9F59-DBACEBFE7043.1; Fri, 11 Nov 2022 13:50:30 +0000 Received: from EUR04-HE1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 12bd5c436923.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Fri, 11 Nov 2022 13:50:30 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=nsxwb8rzflw4w6yyc0+dDoELR6Z8tYTYTokBIwWWRTN5uHGq1+asekVmarCCOAHDCrWa+PLax16xZYps4OxpS2BgSwKWctgUwC6nh58yI2dwnvt5DqMlzErvAxzaJR0hmh6CSfMkun2elacnn/N+Lke7a24Nscr2fTQhBK7yRU40JabhyPhQrSm2zc36ZtTs6ng6yNqudWfOXX7DqqWqZOdq6vD/uLg/VdkgptjW12l5Qdu4Uqt9GYMLumgVbvxv/P9d1l02sIJHKTmogx5rj6R4hEiUyo9c8N+t1z6WaRkC/fBoYf14vxcYCNtp+o7pTtjS+Pm9Sy5jWkmZx7zgnA== 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=RqtOi7Gadx7ikaItofBYHINiwWQKpAIm9hIHZ0t1SEg=; b=VHVyQ0kd/pKhkv5o/eL9CAVOf1VmtDMJ0iBI4vkeMyZJazHCZ98SAhAGZjMZJQ5KMPrAMDraRq8rzCIL6dlLgWsT4znppplrIeOHpIJJe/alYHbMP/reopvmUMWAjXfdM8k84KjovahMgTiIAroJF3u2vqdrBPWa8qn3f2FqGpXn/IGlhV5WjG4nJSlrW220FI4+l1eH0nM6mcOY2CnueALXQqvZPLLqhGuyhUC1GUJmFFp9PCmeEcjemOamXpry+kUpevIh/V0mIa3lM453EteZA3gFC4gc9O/5K5hlcsrMnjyryDVESw7C+70YxaqfDGeoe3pTiwBftcMUZY1STQ== 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 AS8PR08MB6678.eurprd08.prod.outlook.com (2603:10a6:20b:398::8) by AS4PR08MB7504.eurprd08.prod.outlook.com (2603:10a6:20b:4e8::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5813.13; Fri, 11 Nov 2022 13:50:28 +0000 Received: from AS8PR08MB6678.eurprd08.prod.outlook.com ([fe80::8256:29ca:bcd8:b754]) by AS8PR08MB6678.eurprd08.prod.outlook.com ([fe80::8256:29ca:bcd8:b754%7]) with mapi id 15.20.5813.013; Fri, 11 Nov 2022 13:50:28 +0000 Date: Fri, 11 Nov 2022 13:46:25 +0000 To: gcc-patches@gcc.gnu.org Subject: [PATCH 2/8] middle-end: Remove prototype for number_of_iterations_popcount Message-ID: References: Content-Disposition: inline In-Reply-To: X-ClientProxiedBy: LO2P265CA0172.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:a::16) To AS8PR08MB6678.eurprd08.prod.outlook.com (2603:10a6:20b:398::8) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: AS8PR08MB6678:EE_|AS4PR08MB7504:EE_|DBAEUR03FT003:EE_|AS8PR08MB10152:EE_ X-MS-Office365-Filtering-Correlation-Id: 0fb6786f-40d6-49df-feb9-08dac3ebb67d 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: dNV4xAqjQEJTR3/2vbvSHY2fPgcVrjxdr6lD9+53+k8aMWO+kOOzuet1//FoiotvhQ6ZchZJmUW/vrNOJEQQN6/1Igfgxu0dNP7E0c4bFX2b03HloRskdM3pnpR8L+CnWqqG+4iWIeiojsEAZxoqKI2GADlAkbWq4/oWqJPtPp6RTMp4rE9A6VoTasXtMjMP+0udtqtQt2yNEkMfAEbm6TlEfRe4E6XnMZ/XKqtcDP1uz6Z6nffiR185UKM3GYQjcYvVBTck4mwrjd7VWA4iJ8vV9Cy2jqp5467Hxstip8sFBPohLrenipd+at+zPqTzqI1uAyOziJTTPmcEzHNGa6N0H9yGyx4Vx+AuoXzFoq/rmoThk+O9A2TeXY2U2GkD4ytMlPksCrTOCfGNSLzDcYuK/ww0jZ5cmZhZsmIe5xzetRS20ksLjhcugIUxyCXf9iH9+zEqd8JG+kKMsKA6eHc1zvoXDBwfdUGowEiIFqusrNdECypnnZvbEBJir1ygrAxtrWnQ1H3G+CosfHjIOyAwFOK69/jVGbXpLsgAJLfiwB7QPZjjrNvDovnH3wE09yT4WN3umnTVySPZpzMlhlIyIzkqFD7nqTwn5njzlUNhhFzcJHeqjohhtY3rRD3H5hEtmwO+chuEHrVEowEATYjd0Hd0Bi/Y+4pRF0er36sdg1oHZs2tvj/GWFLoHN/V0TijBmFNXVev8xzb4n/bkw== X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AS8PR08MB6678.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(4636009)(396003)(136003)(366004)(346002)(39860400002)(376002)(451199015)(316002)(6916009)(186003)(66556008)(66476007)(66946007)(6512007)(26005)(6666004)(6506007)(478600001)(2906002)(6486002)(86362001)(8676002)(41300700001)(30864003)(5660300002)(38100700002)(44832011)(8936002)(83380400001); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS4PR08MB7504 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: DBAEUR03FT003.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: dc4d0428-b59e-468c-551d-08dac3ebb137 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: iWdbjlggLIda4nQf+SP5CWDqIuHdIsRJiox+0mhozm3UDweG70S6pfwSNTLlOoKYyhxMaGg+Tsw9lLadb+gh+2ujpFPtjMW/iEYNYiDyuMU9SDwijqZUeQX9Ak8j1Bs0g7q5jfqYOxWUAhnoz8U0V2gt0PsS/Jr7IJVMwVlgNCQVFGmzYnzfACRlgpIt5SSrwX2gR5401OK/8sTFUxtBcqFsJlxV81FW4hld6lpJyPV1vhpLu39dqhNw/tvW4vNWA170Gd4N9ED4+xYXdHKOehRGQqQt6vVvoiYBcM78l+/hNPmP6rKn7dKJ8nwrW+nfck6T3zAIjCq2iSlUDmefbT4DxpPqrntq/JW0RQ/4eygbt6ClCe1TbK7Ot/xYvI5yIr/ytUi9wEtolEQfrINp2fVnrj/4FeSka5k4MMOSAgHw2AfMWRK/HPw+qOVuwSYZACs3YlZ7Ygg6le5WtgVYZc44s9IHx8CDIGxZMMKZJkcPI6ygukMGOn0aRSb2hfjEV4SKQ4PG1ddD3aYZRvmFGFDd/08nKtuzQChthPVPJEo7JtkiJRdRLnEq/LW7wJ5H27EWUSwWjgR7pvcTydP0jBWi9PIm6DULb0qzm3mR0MjR2eaU5Mu5/H3rkL/dWmjvlJeW9v9z9P160tSA3bCr1/mFWzEtTDv4VBW3rWU/z7Pld35IBBxWabmPp2wrWUgsPly7wbZTzOpfWGBl1PTCFwNOtn8R6qTluONzrA6IMZYn/oyK+oSqwqoZuHqhOP+A7iOLIZ49Iskg7nyg4u5sCg== 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:(13230022)(4636009)(376002)(136003)(39860400002)(346002)(396003)(451199015)(46966006)(40470700004)(36840700001)(336012)(36860700001)(6512007)(44832011)(81166007)(478600001)(47076005)(6506007)(82740400003)(6916009)(83380400001)(2906002)(186003)(41300700001)(356005)(26005)(8676002)(40460700003)(316002)(40480700001)(82310400005)(30864003)(70206006)(86362001)(6666004)(8936002)(6486002)(5660300002)(70586007); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 11 Nov 2022 13:50:37.2787 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 0fb6786f-40d6-49df-feb9-08dac3ebb67d 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: DBAEUR03FT003.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR08MB10152 X-Spam-Status: No, score=-13.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, KAM_DMARC_NONE, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP, 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: Andrew Carlotti via Gcc-patches From: Andrew Carlotti Reply-To: Andrew Carlotti 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?1749207943551804422?= X-GMAIL-MSGID: =?utf-8?q?1749207943551804422?= gcc/ChangeLog: * tree-ssa-loop-niter.c (ssa_defined_by_minus_one_stmt_p): Move (number_of_iterations_popcount): Move, and remove separate prototype. diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index cdbb924216243ebcabe6c695698a4aee71882c49..c23643fd9dd8b27ff11549e1f28f585534e84cd3 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -63,11 +63,6 @@ struct bounds mpz_t below, up; }; -static bool number_of_iterations_popcount (loop_p loop, edge exit, - enum tree_code code, - class tree_niter_desc *niter); - - /* Splits expression EXPR to a variable part VAR and constant OFFSET. */ static void @@ -2031,6 +2026,200 @@ number_of_iterations_cond (class loop *loop, return ret; } +/* Utility function to check if OP is defined by a stmt + that is a val - 1. */ + +static bool +ssa_defined_by_minus_one_stmt_p (tree op, tree val) +{ + gimple *stmt; + return (TREE_CODE (op) == SSA_NAME + && (stmt = SSA_NAME_DEF_STMT (op)) + && is_gimple_assign (stmt) + && (gimple_assign_rhs_code (stmt) == PLUS_EXPR) + && val == gimple_assign_rhs1 (stmt) + && integer_minus_onep (gimple_assign_rhs2 (stmt))); +} + +/* See if LOOP is a popcout implementation, determine NITER for the loop + + We match: + + goto + + + _1 = b_11 + -1 + b_6 = _1 & b_11 + + + b_11 = PHI + + exit block + if (b_11 != 0) + goto + else + goto + + OR we match copy-header version: + if (b_5 != 0) + goto + else + goto + + + b_11 = PHI + _1 = b_11 + -1 + b_6 = _1 & b_11 + + exit block + if (b_6 != 0) + goto + else + goto + + If popcount pattern, update NITER accordingly. + i.e., set NITER to __builtin_popcount (b) + return true if we did, false otherwise. + + */ + +static bool +number_of_iterations_popcount (loop_p loop, edge exit, + enum tree_code code, + class tree_niter_desc *niter) +{ + bool adjust = true; + tree iter; + HOST_WIDE_INT max; + adjust = true; + tree fn = NULL_TREE; + + /* Check loop terminating branch is like + if (b != 0). */ + gimple *stmt = last_stmt (exit->src); + if (!stmt + || gimple_code (stmt) != GIMPLE_COND + || code != NE_EXPR + || !integer_zerop (gimple_cond_rhs (stmt)) + || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME) + return false; + + gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt)); + + /* Depending on copy-header is performed, feeding PHI stmts might be in + the loop header or loop latch, handle this. */ + if (gimple_code (and_stmt) == GIMPLE_PHI + && gimple_bb (and_stmt) == loop->header + && gimple_phi_num_args (and_stmt) == 2 + && (TREE_CODE (gimple_phi_arg_def (and_stmt, + loop_latch_edge (loop)->dest_idx)) + == SSA_NAME)) + { + /* SSA used in exit condition is defined by PHI stmt + b_11 = PHI + from the PHI stmt, get the and_stmt + b_6 = _1 & b_11. */ + tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx); + and_stmt = SSA_NAME_DEF_STMT (t); + adjust = false; + } + + /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */ + if (!is_gimple_assign (and_stmt) + || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR) + return false; + + tree b_11 = gimple_assign_rhs1 (and_stmt); + tree _1 = gimple_assign_rhs2 (and_stmt); + + /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1). + Also make sure that b_11 is the same in and_stmt and _1 defining stmt. + Also canonicalize if _1 and _b11 are revrsed. */ + if (ssa_defined_by_minus_one_stmt_p (b_11, _1)) + std::swap (b_11, _1); + else if (ssa_defined_by_minus_one_stmt_p (_1, b_11)) + ; + else + return false; + /* Check the recurrence: + ... = PHI . */ + gimple *phi = SSA_NAME_DEF_STMT (b_11); + if (gimple_code (phi) != GIMPLE_PHI + || (gimple_bb (phi) != loop_latch_edge (loop)->dest) + || (gimple_assign_lhs (and_stmt) + != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))) + return false; + + /* We found a match. Get the corresponding popcount builtin. */ + tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx); + if (TYPE_PRECISION (TREE_TYPE (src)) <= TYPE_PRECISION (integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNT); + else if (TYPE_PRECISION (TREE_TYPE (src)) + == TYPE_PRECISION (long_integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL); + else if (TYPE_PRECISION (TREE_TYPE (src)) + == TYPE_PRECISION (long_long_integer_type_node) + || (TYPE_PRECISION (TREE_TYPE (src)) + == 2 * TYPE_PRECISION (long_long_integer_type_node))) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL); + + if (!fn) + return false; + + /* Update NITER params accordingly */ + tree utype = unsigned_type_for (TREE_TYPE (src)); + src = fold_convert (utype, src); + if (TYPE_PRECISION (TREE_TYPE (src)) < TYPE_PRECISION (integer_type_node)) + src = fold_convert (unsigned_type_node, src); + tree call; + if (TYPE_PRECISION (TREE_TYPE (src)) + == 2 * TYPE_PRECISION (long_long_integer_type_node)) + { + int prec = TYPE_PRECISION (long_long_integer_type_node); + tree src1 = fold_convert (long_long_unsigned_type_node, + fold_build2 (RSHIFT_EXPR, TREE_TYPE (src), + unshare_expr (src), + build_int_cst (integer_type_node, + prec))); + tree src2 = fold_convert (long_long_unsigned_type_node, src); + call = build_call_expr (fn, 1, src1); + call = fold_build2 (PLUS_EXPR, TREE_TYPE (call), call, + build_call_expr (fn, 1, src2)); + call = fold_convert (utype, call); + } + else + call = fold_convert (utype, build_call_expr (fn, 1, src)); + if (adjust) + iter = fold_build2 (MINUS_EXPR, utype, call, build_int_cst (utype, 1)); + else + iter = call; + + if (TREE_CODE (call) == INTEGER_CST) + max = tree_to_uhwi (call); + else + max = TYPE_PRECISION (TREE_TYPE (src)); + if (adjust) + max = max - 1; + + niter->niter = iter; + niter->assumptions = boolean_true_node; + + if (adjust) + { + tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, + build_zero_cst (TREE_TYPE (src))); + niter->may_be_zero + = simplify_using_initial_conditions (loop, may_be_zero); + } + else + niter->may_be_zero = boolean_false_node; + + niter->max = max; + niter->bound = NULL_TREE; + niter->cmp = ERROR_MARK; + return true; +} + /* Substitute NEW_TREE for OLD in EXPR and fold the result. If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead all SSA names are replaced with the result of calling the VALUEIZE @@ -2648,203 +2837,6 @@ number_of_iterations_exit_assumptions (class loop *loop, edge exit, return (!integer_zerop (niter->assumptions)); } - -/* Utility function to check if OP is defined by a stmt - that is a val - 1. */ - -static bool -ssa_defined_by_minus_one_stmt_p (tree op, tree val) -{ - gimple *stmt; - return (TREE_CODE (op) == SSA_NAME - && (stmt = SSA_NAME_DEF_STMT (op)) - && is_gimple_assign (stmt) - && (gimple_assign_rhs_code (stmt) == PLUS_EXPR) - && val == gimple_assign_rhs1 (stmt) - && integer_minus_onep (gimple_assign_rhs2 (stmt))); -} - - -/* See if LOOP is a popcout implementation, determine NITER for the loop - - We match: - - goto - - - _1 = b_11 + -1 - b_6 = _1 & b_11 - - - b_11 = PHI - - exit block - if (b_11 != 0) - goto - else - goto - - OR we match copy-header version: - if (b_5 != 0) - goto - else - goto - - - b_11 = PHI - _1 = b_11 + -1 - b_6 = _1 & b_11 - - exit block - if (b_6 != 0) - goto - else - goto - - If popcount pattern, update NITER accordingly. - i.e., set NITER to __builtin_popcount (b) - return true if we did, false otherwise. - - */ - -static bool -number_of_iterations_popcount (loop_p loop, edge exit, - enum tree_code code, - class tree_niter_desc *niter) -{ - bool adjust = true; - tree iter; - HOST_WIDE_INT max; - adjust = true; - tree fn = NULL_TREE; - - /* Check loop terminating branch is like - if (b != 0). */ - gimple *stmt = last_stmt (exit->src); - if (!stmt - || gimple_code (stmt) != GIMPLE_COND - || code != NE_EXPR - || !integer_zerop (gimple_cond_rhs (stmt)) - || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME) - return false; - - gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt)); - - /* Depending on copy-header is performed, feeding PHI stmts might be in - the loop header or loop latch, handle this. */ - if (gimple_code (and_stmt) == GIMPLE_PHI - && gimple_bb (and_stmt) == loop->header - && gimple_phi_num_args (and_stmt) == 2 - && (TREE_CODE (gimple_phi_arg_def (and_stmt, - loop_latch_edge (loop)->dest_idx)) - == SSA_NAME)) - { - /* SSA used in exit condition is defined by PHI stmt - b_11 = PHI - from the PHI stmt, get the and_stmt - b_6 = _1 & b_11. */ - tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx); - and_stmt = SSA_NAME_DEF_STMT (t); - adjust = false; - } - - /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */ - if (!is_gimple_assign (and_stmt) - || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR) - return false; - - tree b_11 = gimple_assign_rhs1 (and_stmt); - tree _1 = gimple_assign_rhs2 (and_stmt); - - /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1). - Also make sure that b_11 is the same in and_stmt and _1 defining stmt. - Also canonicalize if _1 and _b11 are revrsed. */ - if (ssa_defined_by_minus_one_stmt_p (b_11, _1)) - std::swap (b_11, _1); - else if (ssa_defined_by_minus_one_stmt_p (_1, b_11)) - ; - else - return false; - /* Check the recurrence: - ... = PHI . */ - gimple *phi = SSA_NAME_DEF_STMT (b_11); - if (gimple_code (phi) != GIMPLE_PHI - || (gimple_bb (phi) != loop_latch_edge (loop)->dest) - || (gimple_assign_lhs (and_stmt) - != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))) - return false; - - /* We found a match. Get the corresponding popcount builtin. */ - tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx); - if (TYPE_PRECISION (TREE_TYPE (src)) <= TYPE_PRECISION (integer_type_node)) - fn = builtin_decl_implicit (BUILT_IN_POPCOUNT); - else if (TYPE_PRECISION (TREE_TYPE (src)) - == TYPE_PRECISION (long_integer_type_node)) - fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL); - else if (TYPE_PRECISION (TREE_TYPE (src)) - == TYPE_PRECISION (long_long_integer_type_node) - || (TYPE_PRECISION (TREE_TYPE (src)) - == 2 * TYPE_PRECISION (long_long_integer_type_node))) - fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL); - - if (!fn) - return false; - - /* Update NITER params accordingly */ - tree utype = unsigned_type_for (TREE_TYPE (src)); - src = fold_convert (utype, src); - if (TYPE_PRECISION (TREE_TYPE (src)) < TYPE_PRECISION (integer_type_node)) - src = fold_convert (unsigned_type_node, src); - tree call; - if (TYPE_PRECISION (TREE_TYPE (src)) - == 2 * TYPE_PRECISION (long_long_integer_type_node)) - { - int prec = TYPE_PRECISION (long_long_integer_type_node); - tree src1 = fold_convert (long_long_unsigned_type_node, - fold_build2 (RSHIFT_EXPR, TREE_TYPE (src), - unshare_expr (src), - build_int_cst (integer_type_node, - prec))); - tree src2 = fold_convert (long_long_unsigned_type_node, src); - call = build_call_expr (fn, 1, src1); - call = fold_build2 (PLUS_EXPR, TREE_TYPE (call), call, - build_call_expr (fn, 1, src2)); - call = fold_convert (utype, call); - } - else - call = fold_convert (utype, build_call_expr (fn, 1, src)); - if (adjust) - iter = fold_build2 (MINUS_EXPR, utype, call, build_int_cst (utype, 1)); - else - iter = call; - - if (TREE_CODE (call) == INTEGER_CST) - max = tree_to_uhwi (call); - else - max = TYPE_PRECISION (TREE_TYPE (src)); - if (adjust) - max = max - 1; - - niter->niter = iter; - niter->assumptions = boolean_true_node; - - if (adjust) - { - tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, - build_zero_cst (TREE_TYPE (src))); - niter->may_be_zero - = simplify_using_initial_conditions (loop, may_be_zero); - } - else - niter->may_be_zero = boolean_false_node; - - niter->max = max; - niter->bound = NULL_TREE; - niter->cmp = ERROR_MARK; - return true; -} - - /* Like number_of_iterations_exit_assumptions, but return TRUE only if the niter information holds unconditionally. */