From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 3BAFA3858C5F; Thu, 18 May 2023 00:43:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3BAFA3858C5F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684370594; bh=fdT173nyG5naWYaYWiJJ1014xyoV3uI46qLAjenuPT0=; h=From:To:Subject:Date:From; b=OtZB2MVIZLJxyY8V4Z6vcRsMLZ8lOLKcOkzmm+YWMB9lsbsTds29XKfhjRgxXVKCV LxE8F3r5/dS1Cpz/1bCqgDm4AoxPTjycOFNtrc1FJEFJAfRBr2arONlMF/+heUAnPU vDWF2HJdyUucU8vyakHmGDrMPARB6EQWihDeJ6d8= From: "richard.yao at alumni dot stonybrook.edu" To: gcc-bugs@gcc.gnu.org Subject: [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) Date: Thu, 18 May 2023 00:43:13 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: middle-end X-Bugzilla-Version: 14.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: richard.yao at alumni dot stonybrook.edu X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter target_milestone Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D109901 Bug ID: 109901 Summary: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) Product: gcc Version: 14.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: middle-end Assignee: unassigned at gcc dot gnu.org Reporter: richard.yao at alumni dot stonybrook.edu Target Milestone: --- LLVM/Clang also misses this optimization opportunity, so I also filed an is= sue with them: https://github.com/llvm/llvm-project/issues/62790 The following transformations can be done as an optimization: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) ((((a) > (b)) - ((a) < (b))) <=3D 0) -> ((a) <=3D (b)) ((((a) > (b)) - ((a) < (b))) =3D=3D -1) -> ((a) < (b)) ((((a) > (b)) - ((a) < (b))) =3D=3D 1) -> ((a) > (b)) ((((a) > (b)) - ((a) < (b))) =3D=3D 0) -> ((a) =3D=3D (b)) ((((a) > (b)) - ((a) < (b))) > 0) -> ((a) > (b)) ((((a) > (b)) - ((a) < (b))) >=3D 0) -> ((a) >=3D (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) < 0) -> ((a) < (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) <=3D 0) -> ((a) <=3D (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) =3D=3D -1) -> ((a) < (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) =3D=3D 1) -> ((a) > (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) =3D=3D 0) -> ((a) =3D=3D (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) > 0) -> ((a) > (b)) ((((a) >=3D (b)) - ((a) <=3D (b))) >=3D 0) -> ((a) >=3D (b)) Both (((a) > (b)) - ((a) < (b))) and (((a) >=3D (b)) - ((a) <=3D (b))) will generate -1, 0 or 1 when comparing two integers (signed or unsigned). When comparators using this trick are inlined into the caller, the above transformations become applicable. I noticed that neither compiler exploits this high level optimization opportunity when I was working on using a faster binary search implementati= on for the OpenZFS b-tree code. It relied on a macro to achieve C++-style inli= ning of the comparator into the implementation by making different versions of t= he same function. The following example at godbolt does not use a macro to make it easier to = see which lines of assembly correspond to which lines of high level C: https://gcc.godbolt.org/z/cdedccxae On amd64, GCC generates 15 instructions for the loop. If you comment out li= ne 35 and uncomment line 37, GCC will generate 11 instructions for the loop. T= his is the output GCC would produce if it supported that high level optimizatio= n. Had the comparator returned 1 for less than and 0 for greater than or equal= to, we would have had the 11-instruction version of the loop without any need f= or this optimization. Changing the semantics because our compilers lack this optimization would be painful in part because the entire code base expects = the -1, 0 or 1 return value semantics and other code depends on these comparato= rs. It would be nice if GCC implemented this optimization.=