{"id":2221969,"url":"http://patchwork.ozlabs.org/api/1.1/patches/2221969/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/20260410134310.3088893-2-philipp.tomsich@vrull.eu/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/1.1/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null},"msgid":"<20260410134310.3088893-2-philipp.tomsich@vrull.eu>","date":"2026-04-10T13:43:10","name":"[GCC17-stage1,2/2] tree-optimization/122569 - recognize CLZ via isolated MSB DeBruijn lookup","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"202fd6a629bf54f2f5d2e7475ef9919b4c3057e3","submitter":{"id":80556,"url":"http://patchwork.ozlabs.org/api/1.1/people/80556/?format=json","name":"Philipp Tomsich","email":"philipp.tomsich@vrull.eu"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/20260410134310.3088893-2-philipp.tomsich@vrull.eu/mbox/","series":[{"id":499463,"url":"http://patchwork.ozlabs.org/api/1.1/series/499463/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=499463","date":"2026-04-10T13:43:10","name":"[GCC17-stage1,1/2] tree-optimization/122569 - fix DeBruijn CLZ table validator shift-by-64 UB","version":1,"mbox":"http://patchwork.ozlabs.org/series/499463/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2221969/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2221969/checks/","tags":{},"headers":{"Return-Path":"","X-Original-To":["incoming@patchwork.ozlabs.org","gcc-patches@gcc.gnu.org"],"Delivered-To":["patchwork-incoming@legolas.ozlabs.org","gcc-patches@gcc.gnu.org"],"Authentication-Results":["legolas.ozlabs.org;\n\tdkim=pass (2048-bit key;\n unprotected) header.d=vrull.eu header.i=@vrull.eu header.a=rsa-sha256\n header.s=google header.b=Xq/qG5rq;\n\tdkim-atps=neutral","legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)","sourceware.org;\n\tdkim=pass (2048-bit key,\n unprotected) header.d=vrull.eu header.i=@vrull.eu header.a=rsa-sha256\n header.s=google header.b=Xq/qG5rq","sourceware.org;\n dmarc=none (p=none dis=none) header.from=vrull.eu","sourceware.org; spf=pass smtp.mailfrom=vrull.eu","server2.sourceware.org;\n arc=none smtp.remote-ip=209.85.208.172"],"Received":["from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4fsdM21D77z1yGS\n\tfor ; Fri, 10 Apr 2026 23:44:12 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 53E674BA2E2D\n\tfor ; Fri, 10 Apr 2026 13:44:10 +0000 (GMT)","from mail-lj1-f172.google.com (mail-lj1-f172.google.com\n [209.85.208.172])\n by sourceware.org (Postfix) with ESMTPS id 3B7CE4BA2E10\n for ; Fri, 10 Apr 2026 13:43:16 +0000 (GMT)","by mail-lj1-f172.google.com with SMTP id\n 38308e7fff4ca-38e0a8a2ef4so2851721fa.1\n for ; Fri, 10 Apr 2026 06:43:16 -0700 (PDT)","from ubuntu-focal.. ([2a01:4f9:3a:1e26::2])\n by smtp.gmail.com with ESMTPSA id\n 38308e7fff4ca-38e4957eb1esm6498261fa.35.2026.04.10.06.43.13\n (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);\n Fri, 10 Apr 2026 06:43:13 -0700 (PDT)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 53E674BA2E2D","OpenDKIM Filter v2.11.0 sourceware.org 3B7CE4BA2E10"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 3B7CE4BA2E10","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 3B7CE4BA2E10","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1775828596; cv=none;\n b=Dzq1HWXn/64xEyj1/MsRzRXLhnd7Osv+8ThKDkCbWcdCBOgPBJXBzwtiV3Ps/3DQvFfSdJaqxF/LQBrYcfdV33qNQ7g+5p1jkDQdUoesiBzY/tKghW7w6K/4UtcP4kq33VIhWGYQTbOZEur0lv4TJ4NEATEN4rMIAS4hLB/alIc=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1775828596; c=relaxed/simple;\n bh=2hUPCCfYQA80/sDboiPYhumZZgO1jDBtwjO08iTp05s=;\n h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version;\n b=pOjmkCcZJcbRlOa3IT1582QpDZBHLLTSM2nHBto1RpaD3AenNM+RDwrg3edwVtf3OqBJId1yH/3RoqFhEtFoXAqIEivQT4HBViD3iLo1rQROkSlNBr+VcWwEd2rBJA3DfmKiN/ibhldVdOpfrKN9AF/bp+psDeM7NmXoBlnpVu4=","ARC-Authentication-Results":"i=1; server2.sourceware.org","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=vrull.eu; s=google; t=1775828594; x=1776433394; darn=gcc.gnu.org;\n h=content-transfer-encoding:mime-version:references:in-reply-to\n :message-id:date:subject:cc:to:from:from:to:cc:subject:date\n :message-id:reply-to;\n bh=lpr1QCdrwk9FDzDvG31mt20FwEr7FlhvMtsaBlx/Nvg=;\n b=Xq/qG5rqd2178ZpcbH64s6XRtV7gpobhQgbKRNOEzHbIy7PtakS0v0rj+cxHQMqTFQ\n p5RoSDUhP/6ubZUuf9FYFXGezlahz5AMlOp6UeEkx0WQ2M6TvnhevlbKKwkrI1AXEGQw\n pPSsrHNbeuB/8DuNvQm26ixVEPfMzRDqa9N4sSbw5K4OzCGIZIWU60bLpc+wCgdM//zc\n ZSrKa8uSb2S/wkMpa/Lq0vqkgP/wff08fWz0dIw43gD2wc6ZICigm3hyGWODUntV5rr+\n A1SqsDEkxMBlH1TpdTmGOK9BuBqJiyKClvA7hiQstTDGkseAIvviSB2GXeUXMJ6tjGvu\n tAfA==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=1e100.net; s=20251104; t=1775828594; x=1776433394;\n h=content-transfer-encoding:mime-version:references:in-reply-to\n :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from\n :to:cc:subject:date:message-id:reply-to;\n bh=lpr1QCdrwk9FDzDvG31mt20FwEr7FlhvMtsaBlx/Nvg=;\n b=mYrG6xIWc5AkOIjQQbMUv79Gi1u0XOY/GixvvWNK8D40fcC/dsD8S6TP6B/Q9/p10a\n +o3L0ohPX8n3QqVDSRcbshxVOv6pnZbUxl1i2pfeh6kuEi0tMVWDpm6M4q5kUyj2zW0j\n UZo4/2N5w6nxF6Qk7XOi+HqJalOjxzwcO3dsesvJyV45hudsIkPlFw2Vna4PcxjyN4LI\n +Hy1mIoFgKwBs4U5s2hXAlIcgDZU6BcS8kNQQS4HFsPmdqdJ3I9R4CO5KCHUNqwBMyIe\n rnB4u+ZfbX9dhUCXk3BhGw2za3cwufLV8ue3AKUXRtfb5dDBfpnbjA8VFeJcJ8YfvYsD\n b3ZA==","X-Gm-Message-State":"AOJu0Yz/4q3mZg4gD9qojZKrEoXq85B8h77SophJw0r1TjbfFbPyFX8v\n Cp8HFEz0B+nUspOM4Ip9wishuRZelW2/6s0cK5+X0BYgAdQH5D8wp662fifcukirsSFfTnLuuhz\n YizBO7ZA=","X-Gm-Gg":"AeBDieuIa/yHaljFttqt7LAxvfwvJmC+cmVCNFjh5bYEu+hMNQ75/kl4anXnCtPSOdf\n CH0ThZjN35ys82zk6vm0Dzxk7CJJMJ1YhL0khBzsj2Mi602jXUNganray3V0vlwyC4K0TnHhXpd\n gD2YXp9JyCPXPtTFg7YIkx/JjAERNcn+1R5fSTCleFDnxavB4RUiwV7KGDEbl0IrLEGHpBtlv9X\n 2byYkxWpDJYmNIshMpIava1SCIjEpmp0TX0+pOjbDtMVhgka0wLrhjAdZc5kl5oykS/CEv+K7vm\n 9LluCShJoa2K/c3mLshlADg/LkLKzuDXB+C+1eNVXBcB41O1YKRZu4kg4YLb/FHjDchhEtdIx05\n HfvdYPNIcLOWfBCGS/lqFgKjE+1RDqm6RiDYz4xJH54YJUOZ5xPlqO/rqX6dyy4/rkl2Zbeaj2v\n R5lSm50vP9HWzyaFr88Q3aIuU2svoMZrGAdsPh8c/U1nfzJIMHhy6p","X-Received":"by 2002:a2e:be89:0:b0:37e:566d:7fb9 with SMTP id\n 38308e7fff4ca-38e4bbbee47mr4893251fa.1.1775828593753;\n Fri, 10 Apr 2026 06:43:13 -0700 (PDT)","From":"Philipp Tomsich ","To":"gcc-patches@gcc.gnu.org","Cc":"Philipp Tomsich ","Subject":"[GCC17-stage1 PATCH 2/2] tree-optimization/122569 - recognize CLZ via\n isolated MSB DeBruijn lookup","Date":"Fri, 10 Apr 2026 15:43:10 +0200","Message-Id":"<20260410134310.3088893-2-philipp.tomsich@vrull.eu>","X-Mailer":"git-send-email 2.34.1","In-Reply-To":"<20260410134310.3088893-1-philipp.tomsich@vrull.eu>","References":"<20260410134310.3088893-1-philipp.tomsich@vrull.eu>","MIME-Version":"1.0","Content-Transfer-Encoding":"8bit","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list ","List-Unsubscribe":",\n ","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n ","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"Recognize a variant CLZ idiom where the OR-cascade is followed by\n(value - (value >> 1)) to isolate the MSB as a power of two (2^k),\nthen a DeBruijn multiply-and-shift maps 2^k back to k:\n\n value |= value >> 1;\n ...\n value |= value >> 32;\n result = table[((value - (value >> 1)) * MAGIC) >> 58];\n\nAfter the OR-cascade value equals 2^(k+1) - 1, so (value - (value >> 1))\nequals 2^k. The multiply-and-shift is therefore a CTZ-style DeBruijn\nlookup, and the table satisfies table[(magic << k) >> shift] == k.\n\nAdd match.pd pattern clz_msb_iso_table_index matching the full chain.\nIn simplify_count_zeroes, validate the table with the existing CTZ\ncheckfn (which implements the direct-form check) while still emitting\nIFN_CLZ code -- both forms store MSB positions, so the existing CLZ\nemission path including zero_val pre-compensation works unchanged.\n\nAlso relax the element-type check from \"precision <= 32\" to \"integral\nand precision <= 64\" so tables declared as unsigned long (64-bit on\nLP64) are handled. Table values are bit positions in [0, input_bits - 1]\nand fit in any integer type with at least 6 bits of precision.\n\nOnly a 64-bit variant is added: all known uses of this idiom\n(Stockfish, zstd, cpython, the PR122569 comment 3 reproducer) are\n64-bit. A 32-bit variant is a straightforward copy if a real-world\ncase appears.\n\ngcc/ChangeLog:\n\n\tPR tree-optimization/122569\n\t* match.pd (clz_msb_iso_table_index): New match pattern.\n\t* tree-ssa-forwprop.cc (gimple_clz_msb_iso_table_index): Declare.\n\t(simplify_count_zeroes): Recognize the new pattern; route its\n\ttable validation through the CTZ checkfn. Relax the element\n\ttype check to accept integer types up to 64 bits.\n\ngcc/testsuite/ChangeLog:\n\n\tPR tree-optimization/122569\n\t* gcc.dg/tree-ssa/pr122569-3.c: New test.\nSigned-off-by: Philipp Tomsich \n---\nRef: vrull/gcc#450\n\n gcc/match.pd | 35 ++++++++++++++++++++\n gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c | 38 ++++++++++++++++++++++\n gcc/tree-ssa-forwprop.cc | 32 +++++++++++++++---\n 3 files changed, 101 insertions(+), 4 deletions(-)\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c","diff":"diff --git a/gcc/match.pd b/gcc/match.pd\nindex 7b652afb43de..e64cddee9188 100644\n--- a/gcc/match.pd\n+++ b/gcc/match.pd\n@@ -11968,6 +11968,41 @@ and,\n && compare_tree_int (@c16, 16) == 0\n && compare_tree_int (@c32, 32) == 0)))\n \n+/* Match count leading zeros for simplify_count_zeroes in forwprop,\n+ variant that isolates the MSB as a power of two via (s - (s >> 1))\n+ after the OR-cascade has set all bits from 0 to the original MSB.\n+ For such a value s = 2^(k+1) - 1, (s - (s >> 1)) equals 2^k, so the\n+ subsequent DeBruijn multiply-and-shift is a CTZ-style lookup on the\n+ isolated MSB. The table therefore has to satisfy the direct CTZ\n+ DeBruijn property (validated by the CTZ checkfn in\n+ simplify_count_zeroes). PR tree-optimization/122569. */\n+(match (clz_msb_iso_table_index @1 @2 @3)\n+ (rshift (mult\n+ (minus\n+ (bit_ior@f (rshift\n+ (bit_ior@e (rshift\n+ (bit_ior@d (rshift\n+ (bit_ior@c (rshift\n+ (bit_ior@b (rshift\n+\t (bit_ior@a (rshift @1 INTEGER_CST@c1) @1)\n+\t INTEGER_CST@c2) @a)\n+\t INTEGER_CST@c4) @b)\n+ INTEGER_CST@c8) @c)\n+ INTEGER_CST@c16) @d)\n+ INTEGER_CST@c32) @e)\n+ (rshift @f INTEGER_CST@sub1))\n+ INTEGER_CST@2) INTEGER_CST@3)\n+ (if (INTEGRAL_TYPE_P (type)\n+ && TYPE_UNSIGNED (type)\n+ && TYPE_PRECISION (type) == 64\n+ && compare_tree_int (@c1, 1) == 0\n+ && compare_tree_int (@c2, 2) == 0\n+ && compare_tree_int (@c4, 4) == 0\n+ && compare_tree_int (@c8, 8) == 0\n+ && compare_tree_int (@c16, 16) == 0\n+ && compare_tree_int (@c32, 32) == 0\n+ && compare_tree_int (@sub1, 1) == 0)))\n+\n /* Floatint point/integer comparison and integer->integer\n or floating point -> float point conversion. */\n (match (cond_expr_convert_p @0 @2 @3 @6)\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c\nnew file mode 100644\nindex 000000000000..8cbffbe07465\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c\n@@ -0,0 +1,38 @@\n+/* PR tree-optimization/122569 */\n+/* { dg-do compile } */\n+/* { dg-options \"-O2 -fdump-tree-forwprop1-details\" } */\n+\n+/* Test that the forwprop DeBruijn CLZ matcher recognizes the variant\n+ idiom that isolates the MSB as a power of two via (s - (s >> 1))\n+ after the OR-cascade. This pattern uses a CTZ-style DeBruijn magic\n+ applied to 2^MSB, not to the all-bits-below value directly.\n+ Reported on PR 122569 as a second reproducer.\n+\n+ The table element type here is unsigned long (64-bit on LP64 targets)\n+ rather than int, which exercises the relaxed element-type check. */\n+\n+typedef unsigned long long uint64_t;\n+\n+void\n+get_msb_index (unsigned long *result, uint64_t value)\n+{\n+ static const unsigned long deBruijnTable64[64] = {\n+ 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54,\n+ 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30,\n+ 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32,\n+ 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31,\n+ 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5\n+ };\n+\n+ value |= value >> 1;\n+ value |= value >> 2;\n+ value |= value >> 4;\n+ value |= value >> 8;\n+ value |= value >> 16;\n+ value |= value >> 32;\n+\n+ *result = deBruijnTable64[((value - (value >> 1))\n+\t\t\t * (uint64_t) 0x07EDD5E59A4E28C2ULL) >> 58];\n+}\n+\n+/* { dg-final { scan-tree-dump \"__builtin_clz|\\\\.CLZ\" \"forwprop1\" } } */\ndiff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc\nindex 26d1430b5252..2490e1e9dfa5 100644\n--- a/gcc/tree-ssa-forwprop.cc\n+++ b/gcc/tree-ssa-forwprop.cc\n@@ -3380,6 +3380,7 @@ check_table (tree ctor, tree type, HOST_WIDE_INT &zero_val, unsigned bits,\n /* Match.pd function to match the ctz expression. */\n extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree));\n extern bool gimple_clz_table_index (tree, tree *, tree (*)(tree));\n+extern bool gimple_clz_msb_iso_table_index (tree, tree *, tree (*)(tree));\n \n /* Recognize count leading and trailing zeroes idioms.\n The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic\n@@ -3399,6 +3400,12 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)\n gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF);\n \n internal_fn fn = IFN_LAST;\n+ /* When true, the matched idiom is a CLZ using DeBruijn CTZ on the\n+ isolated MSB -- see clz_msb_iso_table_index in match.pd. The\n+ table stores MSB positions and must satisfy the direct CTZ\n+ DeBruijn property, so we validate it with the CTZ checkfn even\n+ though we emit IFN_CLZ code. */\n+ bool clz_via_ctz = false;\n /* For CTZ we recognize ((x & -x) * C) >> SHIFT where the array data\n represents the number of trailing zeros. */\n if (gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL))\n@@ -3414,6 +3421,17 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)\n else if (gimple_clz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0],\n \t\t\t\t NULL))\n fn = IFN_CLZ;\n+ /* Variant CLZ idiom: after the OR-cascade sets all bits from 0 to\n+ the original MSB, (value - (value >> 1)) isolates the MSB as a\n+ power of two (2^k), and the subsequent DeBruijn multiply-and-\n+ shift is a CTZ-style lookup on 2^k. The table stores MSB\n+ positions directly. */\n+ else if (gimple_clz_msb_iso_table_index (TREE_OPERAND (array_ref, 1),\n+\t\t\t\t\t &res_ops[0], NULL))\n+ {\n+ fn = IFN_CLZ;\n+ clz_via_ctz = true;\n+ }\n else\n return false;\n \n@@ -3423,9 +3441,13 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)\n tree input_type = TREE_TYPE (res_ops[0]);\n unsigned input_bits = tree_to_shwi (TYPE_SIZE (input_type));\n \n- /* Check the array element type is not wider than 32 bits and the input is\n- an unsigned 32-bit or 64-bit type. */\n- if (TYPE_PRECISION (type) > 32 || !TYPE_UNSIGNED (input_type))\n+ /* Check the array element type is integral and not wider than 64 bits,\n+ and the input is an unsigned 32-bit or 64-bit type. The table values\n+ are bit positions in [0, input_bits - 1], so any integer element type\n+ with at least 6 bits of precision suffices; the cap is just to keep\n+ the transformation simple. */\n+ if (!INTEGRAL_TYPE_P (type) || TYPE_PRECISION (type) > 64\n+ || !TYPE_UNSIGNED (input_type))\n return false;\n if (input_bits != 32 && input_bits != 64)\n return false;\n@@ -3447,7 +3469,9 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)\n if (!ctor)\n return false;\n unsigned HOST_WIDE_INT mulval = tree_to_uhwi (res_ops[1]);\n- if (fn == IFN_CTZ)\n+ /* CTZ and the MSB-isolation CLZ variant both use the direct CTZ\n+ DeBruijn check (table[(magic << data) >> shift] == data). */\n+ if (fn == IFN_CTZ || clz_via_ctz)\n {\n auto checkfn = [&](unsigned data, unsigned i) -> bool\n \t{\n","prefixes":["GCC17-stage1","2/2"]}