{"id":2221970,"url":"http://patchwork.ozlabs.org/api/patches/2221970/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/20260410134310.3088893-1-philipp.tomsich@vrull.eu/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/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,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"<20260410134310.3088893-1-philipp.tomsich@vrull.eu>","list_archive_url":null,"date":"2026-04-10T13:43:09","name":"[GCC17-stage1,1/2] tree-optimization/122569 - fix DeBruijn CLZ table validator shift-by-64 UB","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"ce910fb4ec267da582895480fca3e4ba27ef2a18","submitter":{"id":80556,"url":"http://patchwork.ozlabs.org/api/people/80556/?format=json","name":"Philipp Tomsich","email":"philipp.tomsich@vrull.eu"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/20260410134310.3088893-1-philipp.tomsich@vrull.eu/mbox/","series":[{"id":499463,"url":"http://patchwork.ozlabs.org/api/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/2221970/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2221970/checks/","tags":{},"related":[],"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=kHTmgdPE;\n\tdkim-atps=neutral","legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=38.145.34.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=kHTmgdPE","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.175"],"Received":["from vm01.sourceware.org (vm01.sourceware.org [38.145.34.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 4fsdM90QZWz1yGS\n\tfor ; Fri, 10 Apr 2026 23:44:21 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 3697A4BA23C4\n\tfor ; Fri, 10 Apr 2026 13:44:19 +0000 (GMT)","from mail-lj1-f175.google.com (mail-lj1-f175.google.com\n [209.85.208.175])\n by sourceware.org (Postfix) with ESMTPS id BA77D4BA2E0F\n for ; Fri, 10 Apr 2026 13:43:14 +0000 (GMT)","by mail-lj1-f175.google.com with SMTP id\n 38308e7fff4ca-38ddeffc1b1so2015761fa.1\n for ; Fri, 10 Apr 2026 06:43:14 -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.11\n (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);\n Fri, 10 Apr 2026 06:43:12 -0700 (PDT)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 3697A4BA23C4","OpenDKIM Filter v2.11.0 sourceware.org BA77D4BA2E0F"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org BA77D4BA2E0F","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org BA77D4BA2E0F","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1775828595; cv=none;\n b=vKt9CH4wYv6+T4xSzD5Rei43S9xZHg9n1mK1Bfcq777IPxYPW2bDphlDd/KAIo5pb4vGJBSnlgm6Y5GmAvKWMfAIz7jK/pfHbdY4UAYqTlSOv4nvcse37h0jfbm1ZFAGAWQO91ztVnFKXKYwjMmUOopwTeqKV16MbFhOCvaeLcU=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1775828595; c=relaxed/simple;\n bh=c8BlPv3PstAsjOLcgxTfYnvHPj+mNrfrq1RfhNHtZZ8=;\n h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version;\n b=QOJBaYAVARTXnznJ/iBVUEh3uj7O+Bc94yFf0yzialCDmmrL6ByBNvq1ewXpgyOCEshGPICQEY9wmwuZa4FOwtgQ45uPDihKpLyIxIBb6bo+KmvEMRZDhdsRMTy75yft64FFRp/QKNbTFavS/6dHGcqhM6kzWXJSIgQNRx6X2po=","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=1775828593; x=1776433393; darn=gcc.gnu.org;\n h=content-transfer-encoding:mime-version:message-id:date:subject:cc\n :to:from:from:to:cc:subject:date:message-id:reply-to;\n bh=hAgZsoo9dYZroEZzNM/+LnlbjO4XEX7SPx76QlqCWeM=;\n b=kHTmgdPEOi45yfntQ6MrGM4kINfss8ArKkJmReE81nNPy7Xdjx6JpcGRcdPLxezlEg\n Q8nk6SJ8YrLmT9o2GIfXA3sShyO7OCZ3TtJu0hKmqOvdUfu4M68PKNd7He3koZDER1Ku\n kwE4nGd0cUiz6vxcziWPsnZVuJJTjGtY4pXcc1YUi3oxTsGr+TANrPSfgv5Z08BNlhKj\n NL9oe6tyEm7vx6TVA5xIUToH7/Kr4Z2ZInYaJVenv2n4Ach1b4WAbnBhX81LNTtHKL9j\n nzGH02d3DyqdL2VZlqkjX6lazKuMnXCH0PE6AXaQ8FaJwGv9gA5owMXSm0N3HCZpI7E0\n J16g==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=1e100.net; s=20251104; t=1775828593; x=1776433393;\n h=content-transfer-encoding:mime-version:message-id:date:subject:cc\n :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date\n :message-id:reply-to;\n bh=hAgZsoo9dYZroEZzNM/+LnlbjO4XEX7SPx76QlqCWeM=;\n b=NQb9TOAMoMXXMZuVwNptlNgXHXtYrt/M2p/cLu+uw3v2sfOkLaq7wq5L41Pyknm6Oi\n TMkUpEGjxOhqpUvPEjPByYUko8DMm+Kx9XoUvLXt5d7cstezf3e7v2UzmF04/7Rg4YAG\n qj6g3U0NnKK/jxUhpvPsFvrlkZaeWlh27u/xd1HYM8h0ce4/tDtMKhky+wqpU684rObL\n TENS5MH3ZLw4rb6AIYuM5MZzKsxlm/t6pVOHZMPIkYyVS1msXAuKxpFZ3y88ovZ9WzRb\n Gp0+An2Lj0XMPhTLQl/mgq4HvSdxN7ZD+mwiVNtWgDJY5xE3QgAIp7m/7mO4PCvnic19\n IBmw==","X-Gm-Message-State":"AOJu0YxtERnvwpLbNC09RBqzuOfYGX8K8kaDpDMqiFl9au0BkowbEY1L\n +rfeAIyi3jyP5JadBM8/QYVa3otEpCYbU4k7GEJC+1ntdZX3HJ2HZ9awz2peDEh5wQ8Ps+4545y\n FsmmFuxU=","X-Gm-Gg":"AeBDiesU0LmyWde6kecFGKQKNt2K4HPeLws0g6+qVeZff21JHUdZpm/YcL2MiHy9pUQ\n WU+8gNERwrdYp4OLQ7vlyEnC4z/ogWxpagV2lkpqtRNs6ma+b9ueiJeW3rOsWIJfmADP7Fq5tda\n dfbsiaWK/9mw5n8iSNL77qfgJNDRaczYER2dhPKAprAyB3PB+6ull3ot/Q9EYp7FiCzQ6c8F4FO\n +MuS183NwxR5oJGHlnb97FLKoIvLMVHFiR+o6TKId5BE5eGRWKwoQhV0FkXGJxgL1gBGn8vOjKD\n jLErKP/bqV8pds+hcjaKfzJBdywFyatPR5mZYotxcwNs/xJ+Jtfd6QKTaO+cWUJ6HxZMihoeTOr\n l/WXKWIsa6CkSMidPQxf3cUKpnYXWa4rz0/kt4oX+5kyajj/c+Wk4alpE0V8Hhj3flU88SJctJz\n 0Z4wDHKwYUoAu98o2ViI7s6IwxahtBMxhYGbwHLBypf/exMPkvTl6w","X-Received":"by 2002:a05:651c:2119:b0:38d:ea91:f4e4 with SMTP id\n 38308e7fff4ca-38e4eaeff08mr3488851fa.0.1775828592911;\n Fri, 10 Apr 2026 06:43:12 -0700 (PDT)","From":"Philipp Tomsich ","To":"gcc-patches@gcc.gnu.org","Cc":"Philipp Tomsich ","Subject":"[GCC17-stage1 PATCH 1/2] tree-optimization/122569 - fix DeBruijn CLZ\n table validator shift-by-64 UB","Date":"Fri, 10 Apr 2026 15:43:09 +0200","Message-Id":"<20260410134310.3088893-1-philipp.tomsich@vrull.eu>","X-Mailer":"git-send-email 2.34.1","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":"simplify_count_zeroes validates DeBruijn CLZ tables by computing\n(1 << (data + 1)) - 1 to simulate the value produced by the OR-cascade\nb |= b >> 1; ... b |= b >> 32. For 64-bit input with data == 63 (the\nMSB bit), data + 1 equals HOST_BITS_PER_WIDE_INT, making the shift\n(HOST_WIDE_INT_1U << 64) undefined behavior. Hosts typically produce\n0, so the check (0 * magic) >> 58 == 63 fails and check_table_array\nreturns false.\n\nEvery well-formed 64-bit DeBruijn CLZ table has an entry mapping the\nall-ones value to bit 63, so this UB rejected every such table --\nincluding the magic 0x03f79d71b4cb0a89 used in Stockfish's msb(),\nzstd's bits.h, and cpython's pycore_bitutils.h.\n\nFix by special-casing data + 1 == HOST_BITS_PER_WIDE_INT to use\nHOST_WIDE_INT_M1U. Only the 64-bit CLZ path is affected.\n\ngcc/ChangeLog:\n\n\tPR tree-optimization/122569\n\t* tree-ssa-forwprop.cc (simplify_count_zeroes): Avoid\n\tshift-by-HOST_BITS_PER_WIDE_INT UB when computing the all-ones\n\tvalue for the CLZ validator.\n\ngcc/testsuite/ChangeLog:\n\n\tPR tree-optimization/122569\n\t* gcc.dg/tree-ssa/pr122569-1.c: New test.\n\t* gcc.dg/tree-ssa/pr122569-2.c: New test.\nSigned-off-by: Philipp Tomsich \n---\nRef: vrull/gcc#450\n\n gcc/testsuite/gcc.dg/tree-ssa/pr122569-1.c | 30 +++++++++++++++\n gcc/testsuite/gcc.dg/tree-ssa/pr122569-2.c | 43 ++++++++++++++++++++++\n gcc/tree-ssa-forwprop.cc | 16 +++++++-\n 3 files changed, 87 insertions(+), 2 deletions(-)\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr122569-1.c\n create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr122569-2.c","diff":"diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr122569-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-1.c\nnew file mode 100644\nindex 000000000000..f400505bc18a\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-1.c\n@@ -0,0 +1,30 @@\n+/* PR tree-optimization/122569 */\n+/* { dg-do compile } */\n+/* { dg-options \"-O2 -fdump-tree-forwprop1-details\" } */\n+\n+/* Test that the forwprop DeBruijn CTZ matcher recognizes the 64-bit\n+ (x & -x) * magic >> 58 + table-lookup idiom used in Stockfish-style\n+ bitboard lsb() functions and many portable-C codebases that predate\n+ __builtin_ctzll. */\n+\n+typedef unsigned long long uint64_t;\n+\n+static const int magictable[64] = {\n+ 0, 1, 48, 2, 57, 49, 28, 3,\n+ 61, 58, 50, 42, 38, 29, 17, 4,\n+ 62, 55, 59, 36, 53, 51, 43, 22,\n+ 45, 39, 33, 30, 24, 18, 12, 5,\n+ 63, 47, 56, 27, 60, 41, 37, 16,\n+ 54, 35, 52, 21, 44, 32, 23, 11,\n+ 46, 26, 40, 15, 34, 20, 31, 10,\n+ 25, 14, 19, 9, 13, 8, 7, 6\n+};\n+\n+int\n+stockfish_lsb (uint64_t b)\n+{\n+ const uint64_t magic = 0x03f79d71b4cb0a89ULL;\n+ return magictable[((b & -b) * magic) >> 58];\n+}\n+\n+/* { dg-final { scan-tree-dump \"__builtin_ctz|\\\\.CTZ\" \"forwprop1\" } } */\ndiff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr122569-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-2.c\nnew file mode 100644\nindex 000000000000..e61586cbd560\n--- /dev/null\n+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-2.c\n@@ -0,0 +1,43 @@\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 64-bit\n+ OR-cascade + magic-multiply + table-lookup idiom used in\n+ Stockfish-style bitboard msb() functions and many portable-C\n+ codebases that predate __builtin_clzll.\n+\n+ The critical edge case is magictable[63] == 63 (the MSB reached\n+ when the OR-cascade input has bit 63 set, so all 64 bits are set).\n+ The validator's CLZ checkfn computed (1 << (data + 1)) - 1 to\n+ simulate that all-ones value, which invoked shift-by-64 UB when\n+ data was 63, causing the transformation to be rejected for any\n+ valid 64-bit DeBruijn CLZ table. */\n+\n+typedef unsigned long long uint64_t;\n+\n+static const int magictable[64] = {\n+ 0, 47, 1, 56, 48, 27, 2, 60,\n+ 57, 49, 41, 37, 28, 16, 3, 61,\n+ 54, 58, 35, 52, 50, 42, 21, 44,\n+ 38, 32, 29, 23, 17, 11, 4, 62,\n+ 46, 55, 26, 59, 40, 36, 15, 53,\n+ 34, 51, 20, 43, 31, 22, 10, 45,\n+ 25, 39, 14, 33, 19, 30, 9, 24,\n+ 13, 18, 8, 12, 7, 6, 5, 63\n+};\n+\n+int\n+stockfish_msb (uint64_t b)\n+{\n+ const uint64_t magic = 0x03f79d71b4cb0a89ULL;\n+ b |= b >> 1;\n+ b |= b >> 2;\n+ b |= b >> 4;\n+ b |= b >> 8;\n+ b |= b >> 16;\n+ b |= b >> 32;\n+ return magictable[(b * magic) >> 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 f060275d72d9..26d1430b5252 100644\n--- a/gcc/tree-ssa-forwprop.cc\n+++ b/gcc/tree-ssa-forwprop.cc\n@@ -3464,8 +3464,20 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)\n \t{\n \t unsigned HOST_WIDE_INT mask\n \t = ((HOST_WIDE_INT_1U << (input_bits - shiftval)) - 1) << shiftval;\n-\t return (((((HOST_WIDE_INT_1U << (data + 1)) - 1) * mulval) & mask)\n-\t\t >> shiftval) == i;\n+\t /* The OR-cascade produces a value with all bits from 0 to the\n+\t original MSB set. Compute (1 << (data + 1)) - 1 to simulate\n+\t that value. When data + 1 equals HOST_BITS_PER_WIDE_INT\n+\t (i.e. data is the MSB position of a 64-bit input) the shift\n+\t is undefined behavior, so handle that case explicitly using\n+\t all-ones. Without this, any well-formed 64-bit DeBruijn CLZ\n+\t table is rejected because its entry for the all-ones input\n+\t correctly maps to the MSB (e.g. table[...] == 63).\n+\t PR tree-optimization/122569. */\n+\t unsigned HOST_WIDE_INT all_bits_below\n+\t = (data + 1 == HOST_BITS_PER_WIDE_INT)\n+\t ? HOST_WIDE_INT_M1U\n+\t : ((HOST_WIDE_INT_1U << (data + 1)) - 1);\n+\t return (((all_bits_below * mulval) & mask) >> shiftval) == i;\n \t};\n if (!check_table (ctor, type, zero_val, input_bits, checkfn))\n return false;\n","prefixes":["GCC17-stage1","1/2"]}