From patchwork Mon Feb 26 06:52:32 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 206276 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7300:a81b:b0:108:e6aa:91d0 with SMTP id bq27csp1904876dyb; Sun, 25 Feb 2024 22:53:15 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCVxaEvuKXJb+2qnkQgMDwk4ljuF+s8QkJ0/CiUscsJfpZe61PvyWmQnlmbDhXI9l+vrZIbtI0nNn3NetIK/WZnnccw+9g== X-Google-Smtp-Source: AGHT+IEQUoLeOGWhA8KU33vvfOZ/P6KO6DAHHSrzrOSpxdFfL7fBGODDh3W0NPRE8/gJEdsI521s X-Received: by 2002:a05:620a:444a:b0:787:d516:d28 with SMTP id w10-20020a05620a444a00b00787d5160d28mr1491184qkp.14.1708930395207; Sun, 25 Feb 2024 22:53:15 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708930395; cv=pass; d=google.com; s=arc-20160816; b=XF9tdrPbADjTOPLdR1sr7KIGvAHzNDAQIuod+YRH0I1KLy7CZm8uXlvbFPdzu+ekb9 0vzR96D/T0sbfITp8X1I7kVbVjKR5o1YeBpth0WNIzHFVO5skALukmCZ13U/q3rOImvr nklGulmdGyM7EpoOWnoLoPP4CR0Ij5uwuxsVsHNCAbAcp78htK7PMtZ91ZW1MpcwKiLG yMC6zAaJvokT188ozEIRYC63GjFurFGo8jTLHs4EmoWawDQ+jvZH4cFXFBeV04SQqXZA hplwvZsR8b0kCnowSnk1Bv/JGX3oG7iIpfoWT4V6Ky59LMcxMjDDAL27wBGUQq+t7wK/ XlqA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:reply-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-disposition :mime-version:message-id:subject:cc:to:from:date:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=eEMNCC+ZVVcB2TtFaODlFRvJckC0Rm5gVlQ9F1nbY2I=; fh=FCjeRajqaQYHMkQtfIia8KT5yBac53mYOLLyJhYG/AY=; b=JIHQ7SGmdWA9Txlr5D7Cha5vHPnuGxS6q9I+xXEhw8tAfi1P2a1Zf0IX6vfvTi3GcB eOKS5XAbXOjdL3/McIzJjR8sxTV5HCNiBJ7Krbk8fbxHtZZAuDpE2yTevPDmVODyaEXr EPr7T5xzT4/zMiv3VprWgv0qXSDu8YyV/9vRoHU1SGYRSDRblSwOVN7MenHtlkG98lNA UjD2w14SesH+pPfk+Qu8q2o7W7gAddwHdd/U1jWpwkxVKd1XQ2NUNbBnQSmOpEA2a8jC koZFiQKvtdQf5Feq1CYFxgRPvlC8NvacLByDIdhYfCKScbj0x4ws+/3BJWBhjc4Ndrsn SNxg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=PdEy4FTe; arc=pass (i=1); 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=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id b3-20020a05620a088300b0078715ed4c26si4686657qka.35.2024.02.25.22.53.15 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 25 Feb 2024 22:53:15 -0800 (PST) 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=@redhat.com header.s=mimecast20190719 header.b=PdEy4FTe; arc=pass (i=1); 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=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E3B9C3858CDB for ; Mon, 26 Feb 2024 06:53:14 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 0244B3858D3C for ; Mon, 26 Feb 2024 06:52:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0244B3858D3C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0244B3858D3C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1708930360; cv=none; b=QAciOPspfzlGPSUwbIB0CpArdT1NXCojGMBpmcadBZnfXLmtDHoT6qtlafdmVss6RrFOkDBnchDjM4XmTGQIxWr86+5ZRiLq7Q5tGMt5gxKQXGB6OJYmWWQWe4oLxqvx2oooCjVoJoJVKf+tOMbYHCMySPrCdPCAo+exj5hJi0M= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1708930360; c=relaxed/simple; bh=64qKJ2mGPkmXqi84e18eEjekxzQyU9FfehpWL9lVodU=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=BXYJhmjtZY90Eau6cixW4wfsoyoZGmpUoSD4SI0n91efuu2UHf8ouQIGD2cejdVJXHoF5KOuue2JPJdjYGmWsFFn27jbrP/0cb+e64ec+6Xyiz9gf7HTQB2g6qJPFKh3p95ucJQXUm4Z7PlH28CZywLvPVHTtBnN6uLRMz/bqvo= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1708930358; h=from:from:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=eEMNCC+ZVVcB2TtFaODlFRvJckC0Rm5gVlQ9F1nbY2I=; b=PdEy4FTeuxtJqJL4yRGerf7jNvN+c5oFQ0l6k8dvGF35xL8cAmtduMVTHMtAxttv27v8Q1 YuZiRw+3kvRPCZPIMvA+QruGl+U2Br4v3eE4VJd/b2ozX8sAFkmKxBw/Ze47OLjroIvhAe 6BISWCNM3wfkhqc6nQg9GxIyO802jwE= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-433-bZ6lFYe8O0S2lI8yCKYHoQ-1; Mon, 26 Feb 2024 01:52:37 -0500 X-MC-Unique: bZ6lFYe8O0S2lI8yCKYHoQ-1 Received: from smtp.corp.redhat.com (int-mx10.intmail.prod.int.rdu2.redhat.com [10.11.54.10]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 76AC684AF83; Mon, 26 Feb 2024 06:52:36 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.192.25]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 3A700492BD7; Mon, 26 Feb 2024 06:52:36 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 41Q6qXXF1346686 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Mon, 26 Feb 2024 07:52:33 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 41Q6qWO91346685; Mon, 26 Feb 2024 07:52:32 +0100 Date: Mon, 26 Feb 2024 07:52:32 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] fold-const: Avoid infinite recursion in +-*&|^minmax reassociation [PR114084] Message-ID: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.10 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-3.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Jakub Jelinek Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791943398191020236 X-GMAIL-MSGID: 1791943398191020236 Hi! In the following testcase we infinitely recurse during BIT_IOR_EXPR reassociation. One operand is (unsigned _BitInt(31)) a << 4 and another operand 2147483647 >> 1 | 80 where both the right shift and the | 80 trees have TREE_CONSTANT set, but weren't folded because of delayed folding, where some foldings are apparently done even in that case unfortunately. Now, the fold_binary_loc reassocation code splits both operands into variable part, minus variable part, constant part, minus constant part, literal part and minus literal parts, to prevent infinite recursion punts if there are just 2 parts altogether from the 2 operands and then goes on with reassociation, merges first the corresponding parts from both operands and then some further merges. The problem with the above expressions is that we get 3 different objects, var0 (the left shift), con1 (the right shift) and lit1 (80), so the infinite recursion prevention doesn't trigger, and we eventually merge con1 with lit1, which effectively reconstructs the original op1 and then associate that with var0 which is original op0, and associate_trees for that case calls fold_binary. There are some casts involved there too (the T typedef type and the underlying _BitInt type which are stripped with STRIP_NOPS). The following patch attempts to prevent this infinite recursion by tracking the origin (if certain var comes from nothing - 0, op0 - 1, op1 - 2 or both - 3) and propagates it through all the associate_tree calls which merge the vars. If near the end we'd try to merge what comes solely from op0 with what comes solely from op1 (or vice versa), the patch punts, because then it isn't any kind of reassociation between the two operands, if anything it should be handled when folding the suboperands. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2024-02-26 Jakub Jelinek PR middle-end/114084 * fold-const.cc (fold_binary_loc): Avoid the final associate_trees if all subtrees of var0 come from one of the op0 or op1 operands and all subtrees of con0 come from the other one. Don't clear variables which are never used afterwards. * gcc.dg/bitint-94.c: New test. Jakub --- gcc/fold-const.cc.jj 2024-02-24 09:49:09.098815803 +0100 +++ gcc/fold-const.cc 2024-02-24 11:08:56.036223491 +0100 @@ -11779,6 +11779,15 @@ fold_binary_loc (location_t loc, enum tr + (lit0 != 0) + (lit1 != 0) + (minus_lit0 != 0) + (minus_lit1 != 0)) > 2) { + int var0_origin = (var0 != 0) + 2 * (var1 != 0); + int minus_var0_origin + = (minus_var0 != 0) + 2 * (minus_var1 != 0); + int con0_origin = (con0 != 0) + 2 * (con1 != 0); + int minus_con0_origin + = (minus_con0 != 0) + 2 * (minus_con1 != 0); + int lit0_origin = (lit0 != 0) + 2 * (lit1 != 0); + int minus_lit0_origin + = (minus_lit0 != 0) + 2 * (minus_lit1 != 0); var0 = associate_trees (loc, var0, var1, code, atype); minus_var0 = associate_trees (loc, minus_var0, minus_var1, code, atype); @@ -11791,15 +11800,19 @@ fold_binary_loc (location_t loc, enum tr if (minus_var0 && var0) { + var0_origin |= minus_var0_origin; var0 = associate_trees (loc, var0, minus_var0, MINUS_EXPR, atype); minus_var0 = 0; + minus_var0_origin = 0; } if (minus_con0 && con0) { + con0_origin |= minus_con0_origin; con0 = associate_trees (loc, con0, minus_con0, MINUS_EXPR, atype); minus_con0 = 0; + minus_con0_origin = 0; } /* Preserve the MINUS_EXPR if the negative part of the literal is @@ -11815,15 +11828,19 @@ fold_binary_loc (location_t loc, enum tr /* But avoid ending up with only negated parts. */ && (var0 || con0)) { + minus_lit0_origin |= lit0_origin; minus_lit0 = associate_trees (loc, minus_lit0, lit0, MINUS_EXPR, atype); lit0 = 0; + lit0_origin = 0; } else { + lit0_origin |= minus_lit0_origin; lit0 = associate_trees (loc, lit0, minus_lit0, MINUS_EXPR, atype); minus_lit0 = 0; + minus_lit0_origin = 0; } } @@ -11833,37 +11850,51 @@ fold_binary_loc (location_t loc, enum tr return NULL_TREE; /* Eliminate lit0 and minus_lit0 to con0 and minus_con0. */ + con0_origin |= lit0_origin; con0 = associate_trees (loc, con0, lit0, code, atype); - lit0 = 0; + minus_con0_origin |= minus_lit0_origin; minus_con0 = associate_trees (loc, minus_con0, minus_lit0, code, atype); - minus_lit0 = 0; /* Eliminate minus_con0. */ if (minus_con0) { if (con0) - con0 = associate_trees (loc, con0, minus_con0, - MINUS_EXPR, atype); + { + con0_origin |= minus_con0_origin; + con0 = associate_trees (loc, con0, minus_con0, + MINUS_EXPR, atype); + } else if (var0) - var0 = associate_trees (loc, var0, minus_con0, - MINUS_EXPR, atype); + { + var0_origin |= minus_con0_origin; + var0 = associate_trees (loc, var0, minus_con0, + MINUS_EXPR, atype); + } else gcc_unreachable (); - minus_con0 = 0; } /* Eliminate minus_var0. */ if (minus_var0) { if (con0) - con0 = associate_trees (loc, con0, minus_var0, - MINUS_EXPR, atype); + { + con0_origin |= minus_var0_origin; + con0 = associate_trees (loc, con0, minus_var0, + MINUS_EXPR, atype); + } else gcc_unreachable (); - minus_var0 = 0; } + /* Reassociate only if there has been any actual association + between subtrees from op0 and subtrees from op1 in at + least one of the operands, otherwise we risk infinite + recursion. See PR114084. */ + if (var0_origin != 3 && con0_origin != 3) + return NULL_TREE; + return fold_convert_loc (loc, type, associate_trees (loc, var0, con0, code, atype)); --- gcc/testsuite/gcc.dg/bitint-94.c.jj 2024-02-24 11:18:32.607018363 +0100 +++ gcc/testsuite/gcc.dg/bitint-94.c 2024-02-24 11:19:09.023500121 +0100 @@ -0,0 +1,12 @@ +/* PR middle-end/114084 */ +/* { dg-do compile { target bitint } } */ +/* { dg-options "-std=c23 -pedantic-errors" } */ + +typedef unsigned _BitInt(31) T; +T a, b; + +void +foo (void) +{ + b = (T) ((a | (-1U >> 1)) >> 1 | (a | 5) << 4); +}