From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by sourceware.org (Postfix) with ESMTPS id 4DF103937430 for ; Tue, 4 Jun 2024 13:41:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4DF103937430 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 4DF103937430 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::329 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1717508492; cv=none; b=ZxAOZzdjdhMdi9hNOJqARgY9zdmifXaW6kickfBlQn0odfecc5uVDc5eiEmdqZn0jJR6rMOGD+0UlAwRJNq0wjh2t654+BgGkU+ydiFgFL1F0TRS0ArdHa7PmrLY3YthR0RKWP8rdTa/C8xNqGk0IDUISraPG0Uv7MovTskEDWw= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1717508492; c=relaxed/simple; bh=+etthFilU7PZrcEiOXF8gUdi/hycO70ZT7lmijGq+34=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=c2FyN66Q2B4oPUznfV67b8x2cQS5ll8E3drgJp65YwuiZi9bYwiEws4lQxcA5elfgK9A+llJqzHMnpUEDQLJzr8imIVH+sYCosdKG/aWIOT1LbOh9SpdOj1/vWLvPBT8gJ9aFxr42W1lZNZIya+23w3YWI4CrOIIjZIntQHjdQU= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x329.google.com with SMTP id 5b1f17b1804b1-421140314d5so50570855e9.0 for ; Tue, 04 Jun 2024 06:41:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717508489; x=1718113289; darn=gcc.gnu.org; h=cc:to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=NI9FGMkJJog5FZZfSzVRV28koDA9V7CuJqtkpcZ5N/A=; b=QXPZqSrBFOdtzKgZwXMBIcFmnP5FAvi4yF90f1ORRpt5aKEjbYNfTLGZWkwVcFqy5j 6NM19MsUw2ZqoIj3kCym2HRLXG+wHruXXEWESwBr0176s2pwJM35eaKveRi+gnKHu9pZ yRuAefSehw3rj4t4xnq6iILDbZKfHNIqMZ64y74l1CLqUJRIZynbxNWqXLy4wMjVdXI5 4y0lmKlw1AimdtXT15z/jajHEans7kMc1Fu4QKg/ayvjL0Q5T20vAig/XarQyzNjkfWf wc8DXjokhUzUmRgSkpBo3E4nOWTS4kESW5kwx3cK7+YUAx7yNStiidWlYuDQaLSM4ZWy FnWw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717508489; x=1718113289; h=cc:to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=NI9FGMkJJog5FZZfSzVRV28koDA9V7CuJqtkpcZ5N/A=; b=L+ZnLEjaVgIvxweTdvQEs2ucKPc1AZ/+TMOn9/fu/ClQOiUZe4EBRsFLrbBXB7577V cJqrtduWJDD7ENljmldEzuOfDUwRhGOMNAREwPRqKWz5PhzbphM0zuQA86T1wBBzaKFh c6bT6djvwwD9AJFV417jPD+JEe8QZhnnvDFhizuUXXbaDpQznRFBEl+4niDCbvnnNCYG 5F5ieI50vWWBiIHmH/ELCvctLxltLyxnWND9lQeDRBsjncQyFK/zFhptcUrAUuU0lnuP NZiPooqoSuNN+A7XGxK9pKJP6GE58XDyxApNrLbCMQneeFpuY8QuAYEyM418lZLkxdvX 7PLw== X-Gm-Message-State: AOJu0YwUwPGYJzC3GPkN/9UT6KBSLJtf1edb+STAEulNFf7xZT5Z6yX5 941vhp46R9c+a5eO4smcGmxy4MW9DbW3pd48fxh8iPYnKDWSbWvYjTbTHNpCWU8oBlDhAe5Q+f0 FD4YndBYzoUCqWCZjGtXczPqtA6JO1w== X-Google-Smtp-Source: AGHT+IHZC1qwFQ/HG/3WnWDcgyDlEIfsk3X1BYG+sBFvH/TR6RUYNx0mEpcW8KQJ+Jk4R+89T1RTpePSGgwIX02ec4o= X-Received: by 2002:a05:600c:3c91:b0:418:f760:abfb with SMTP id 5b1f17b1804b1-4212e0461cemr100085145e9.5.1717508488798; Tue, 04 Jun 2024 06:41:28 -0700 (PDT) MIME-Version: 1.0 From: Mariam Arutunian Date: Tue, 4 Jun 2024 17:41:17 +0400 Message-ID: Subject: Re: [RFC/RFA] [PATCH 08/12] Add a new pass for naive CRC loops detection To: Richard Biener Cc: GCC Patches , Jeff Law Content-Type: multipart/alternative; boundary="0000000000005fa908061a109bb8" X-Spam-Status: No, score=-0.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,FREEMAIL_REPLY,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: --0000000000005fa908061a109bb8 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Sorry for the late response; somehow, I didn't receive the last few message= s. >>* Am 30.05.2024 um 00:31 schrieb Jeff Law >: *>> >>* =EF=BB=BF *>> >>>* On 5/28/24 1:01 AM, Richard Biener wrote: *>>>>* On Fri, May 24, 2024 at 10:46=E2=80=AFAM Mariam Arutunian *>>>>* > wrote: *>>>> >>>>* This patch adds a new compiler pass aimed at identifying naive CRC implementations, *>>>>* characterized by the presence of a loop calculating a CRC (polynomial long division). *>>>>* Upon detection of a potential CRC, the pass prints an informational message. *>>>> >>>>* Performs CRC optimization if optimization level is >=3D 2, *>>>>* besides optimizations for size and if fno_gimple_crc_optimization gi= ven. *>>>> >>>>* This pass is added for the detection and optimization of naive CRC implementations, *>>>>* improving the efficiency of CRC-related computations. *>>>> >>>>* This patch includes only initial fast checks for filtering out non-CRCs, *>>>>* detected possible CRCs verification and optimization parts will be provided in subsequent patches. *>>>* Just a few quick questions - I'm waiting for a revision with Jeffs comments cleared before having a closer look. The patch does *>>>* nothing but analyze right now, correct? I assume a later patch will *>>>* fill in stuff in ::execute and use the return value of *>>>* loop_may_calculate_crc (it's a bit odd to review such a "split" *>>>* thing). *>>* We split it up on functional chunks. I think if it gets approved it probably should go in atomically since it makes no sense to commit the first pass recognition filter without the validation step or the validation step without the codegen step. *>> >>* So consider the break down strictly for review convenience. *>> >> >>>* I think what this does fits final value replacement which lives in tree-scalar-evolution.cc and works from the loop-closed PHIs, trying *>>>* to replace those. I'm not sure we want to have a separate pass for *>>>* this. Consider a loop calculating two or four CRCs in parallel, replacing LC PHIs one-by-one should be able to handle this. *>>* I suspect that'll be quite hard for both the "does this generally look like a CRC loop" code as well as the "validate this is a CRC loop" code. *>> >>* Mariam, your thoughts on whether or not those two phases could handle a loop with two CRC calculations inside, essentially creating two calls to our new builtins? * It is feasible, but it would likely demand considerable effort and additional work to implement effectively. >The key would be to only simulate the use-def cycle from the loop-closed P= HI (plus the loop control of course, but miter/SCEV should be enough there)= and just replace that LC PHI, leaving loop DCE to DCE. Thank you, this is a good idea to just replace the PHI and leave the loop to DCE to remove only single CRC parts. However, if you mean using the symbolic executor to only simulate the use-def cycle and loop control, instead of the whole control flow of the loop, it won't be sufficient. Some calculations may occur under certain conditions, which must also be taken into account. This situation is solvable, but it requires more complex work to create a graph of the statements that must be executed. We can consider this as a potential improvement for later. The current pass only verifies cases where a single CRC calculation is performed within the loop. During the verification phase, I ensure that there are no other calculations aside from those necessary for the considered CRC computation. Also, when I was investigating the bitwise CRC implementations used in different software, in all cases the loop was calculating just one CRC and no other calculations were done. Thus, in almost all cases, the first phase will filter out non-CRCs, and during the second phase, only real CRCs with no other calculations will be executed. This ensures that unnecessary statements won't be executed in most cases. Leaving the loop to DCE will simplify the process of removing parts connected to a single CRC calculation. However, since now we detect a loop that only calculates a single CRC, we can entirely remove it at this stage without additional checks. >If we really want a separate pass (or utility to work on a single loop) th= en we might consider moving some of the final value replacement code that d= oesn=E2=80=99t work with only SCEV there as well. There=E2=80=99s also spe= cial code in loop distribution for strlen recognition now, not exactly fitt= ing in. > >Note I had patches to do final value replacement on demand from CD-DCE whe= n it figures a loop has no side effects besides of its reduction outputs (s= till want to pick this up at some point again). Oh, this could provide useful insights for our implementation. Thanks, Mariam >Richard > >>* Jeff *>> --0000000000005fa908061a109bb8--