From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mailrelay2-1.pub.mailoutpod1-cph3.one.com (mailrelay2-1.pub.mailoutpod1-cph3.one.com [46.30.210.183]) by sourceware.org (Postfix) with ESMTPS id 297BC3857C55 for ; Fri, 7 Aug 2020 20:30:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 297BC3857C55 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=amylaar.uk Authentication-Results: sourceware.org; spf=none smtp.mailfrom=gnu@amylaar.uk DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amylaar.uk; s=20191106; h=content-transfer-encoding:content-type:in-reply-to:references:subject:cc:to: mime-version:from:date:message-id:from; bh=TrK3Suvbiu67yht5IkwspvuEAm31VaT6mYlb5HQI/QA=; b=QMHki/P7uhWFzXTdorCiCVFGmvh6+RDk0qvcZbd1q7UbfNSw/vyXuYRFm8Z3gqhp52A4dk1x3FBZr eyR2kukq1vpege6ttAI+1X8BwB61jSYLtUZbX9TsC09426mLkW/Q256RvzcBhTPc9ApcCuqdLLwa9L QRQz8BBewol2dWZiUrvDFeIwIZfYMqnrR5jfW4TtRFOaa0xry3uK5uuBLbRyGJfvTLxsTv90qCAx52 nvcx8erqysUqGr1TpQ8cmnFaUJAYuzCOU0zzb+zAUe42NfVjSLfm8SagXns2NSUy5CF8kJ/nDvlo3f NYketHHoFSa7uzxVnY0r0JUt6p2kuyQ== X-HalOne-Cookie: c710ea6677d98eaffe30be44769f41e56eacc154 X-HalOne-ID: d5ac7ac7-d8ec-11ea-8889-d0431ea8a290 Received: from [192.168.1.129] (cust213-dsl91-135-11.idnet.net [91.135.11.213]) by mailrelay2.pub.mailoutpod1-cph3.one.com (Halon) with ESMTPSA id d5ac7ac7-d8ec-11ea-8889-d0431ea8a290; Fri, 07 Aug 2020 20:30:30 +0000 (UTC) Message-ID: <5F2DB9E5.7070104@amylaar.uk> Date: Fri, 07 Aug 2020 21:30:29 +0100 From: Joern Wolfgang Rennecke User-Agent: Mozilla/5.0 (X11; Linux i686; rv:31.0) Gecko/20100101 Thunderbird/31.3.0 MIME-Version: 1.0 To: Marc Glisse CC: GCC Patches Subject: Re: Simplify X * C1 == C2 with undefined overflow References: <5F2D51A5.3070006@amylaar.uk> In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP 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, 07 Aug 2020 20:30:48 -0000 On 07/08/20 19:21, Marc Glisse wrote: > > If we are going to handle the wrapping case, we shouldn't limit to the > non-wrapping meaning of multiplicity. 3*X==5 should become > X==1431655767 (for a 32 bit type), etc. > > Do we have an extended gcd somewhere in gcc, to help compute 1431655767? I don't quite see yet how this relates to gcd, but how how about this: First, we divide the right hand side of the comparison by the constant factor. 5 divided by 3 is one, with rest 2. Now we want to express this rest two by wrapping overflow. 0x100000000 divided by 3 is 0x55555555 rest 1. When we multiply 0x55555555 again by three, the rest is missing, so we get -1 in 32 bit. So we try to express 2 as a multiple of -1: 2/-1 = -2 Thus, the quotient is 1 + 0x55555555 * -2 , which, using 32 bit wrapping arithmetic, is 0x55555557, i.e. 1431655767 . Again, because the constant factor (3) is odd, there can be no other solution. However, there are cases were the second division will not be possible without rest. Consider : 7*X == 3 3/7 is 0 rest 3. 0x100000000 / 7 is 0x24924924 rest 4 Since 3 cannot be represented as an integer multiple of -4, we can conclude that the predicate is always false. Also: 14*X == 28 has a non-zero power of two in the constant factor, so we have to factor out the power of two (if the right hand side has a lower power of two, the predicate is always false) and consider in modulo arithmetic with a number of bits less by the factored out power of two, i.e. 31 bit here: 7*X == 14 which is solved as above - but in 32 bit arithmetic - to X == 2 and to convert back to 32 bit arithmetic, we get: X & 0x7fffffff == 2 or 2*x == 4 Likewise, 14*X == 30 would be reduced to 7*X == 15 in 31 bit arithmetic, then we find that we can't express the rest of 1 as an integer multiple of -2, so the predicate is always false. . > >> (Even if the variable factor is wider than equality comparison, that >> is not a problem as long as the comparison is not widened by the >> transformation.) >> >> On the other hand, the following generalizations would work only >> without overflow: >> - handling of inequality-comparisons - merely have to account for the >> sign of the factor reversing the sense of >> the inequality, e.g. -3*X >= 15 ---> X <= 5 > > And again for this one, we have to be careful how we round the > division, but we don't have to limit to the case where 15 is a > multiple of 3. 3*X>7 can be replaced with X>2. > > > Those are two nice suggestions. Do you intend to write a patch? No, I just couldn't resist applying a smidge of number theory to a compiler problem. I still have to herd other patches. > Otherwise I'll try to do it eventually (no promise). Would be nice.