{"id":2232136,"url":"http://patchwork.ozlabs.org/api/1.2/patches/2232136/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/20260503053451.48504-2-herumi@nifty.com/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/1.2/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":"<20260503053451.48504-2-herumi@nifty.com>","list_archive_url":null,"date":"2026-05-03T05:34:49","name":"[v2,1/3] expmed: Optimize 32-bit unsigned division by constants on 64-bit targets","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"61a555b2ff09cde368f61089ac3b313696e9b772","submitter":{"id":92964,"url":"http://patchwork.ozlabs.org/api/1.2/people/92964/?format=json","name":null,"email":"herumi@nifty.com"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/20260503053451.48504-2-herumi@nifty.com/mbox/","series":[{"id":502562,"url":"http://patchwork.ozlabs.org/api/1.2/series/502562/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=502562","date":"2026-05-03T05:34:51","name":"Optimize 32-bit unsigned constant division for 64-bit targets","version":2,"mbox":"http://patchwork.ozlabs.org/series/502562/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2232136/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2232136/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=nifty.com header.i=@nifty.com header.a=rsa-sha256\n header.s=default-1th84yt82rvi header.b=p7KnRyCl;\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=nifty.com header.i=@nifty.com header.a=rsa-sha256\n header.s=default-1th84yt82rvi header.b=p7KnRyCl","sourceware.org;\n dmarc=pass (p=none dis=none) header.from=nifty.com","sourceware.org; spf=pass smtp.mailfrom=nifty.com","server2.sourceware.org;\n arc=none smtp.remote-ip=106.153.227.39"],"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 4g7YRj71yZz1yJV\n\tfor ; Sun, 03 May 2026 15:36:33 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 036C74BB58AB\n\tfor ; Sun, 3 May 2026 05:36:32 +0000 (GMT)","from mta-snd-w07.mail.nifty.com (mta-snd-w07.mail.nifty.com\n [106.153.227.39])\n by sourceware.org (Postfix) with ESMTPS id AC29D4BB5883\n for ; Sun, 3 May 2026 05:35:43 +0000 (GMT)","from sapp by mta-snd-w07.mail.nifty.com with ESMTP\n id <20260503053541099.UGI.19957.sapp@nifty.com>;\n Sun, 3 May 2026 14:35:41 +0900"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 036C74BB58AB","OpenDKIM Filter v2.11.0 sourceware.org AC29D4BB5883"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org AC29D4BB5883","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org AC29D4BB5883","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1777786544; cv=none;\n b=oAs7PuSktcrS/S/cLif7bC+yn3Ua/wXNnEzrF3osfVae+2jm1aSKqNeLa+9ZabP7uribjo5oZ3wl6hx9PhsrkL0jFD3mUNGl9TaiLSZjskfksuBx5gHt99U1DXjO6kvHV9nSq6ZQeKYWgMfNO86ShKCNoG6MtjBM4c9dkJBT7Uc=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1777786544; c=relaxed/simple;\n bh=VJKnghihuZdub1MpcDEsmC61fVSiu8+RKyzjjpbT3tQ=;\n h=From:To:Subject:Date:Message-ID:MIME-Version:DKIM-Signature;\n b=V1QvLP6RRVjp4t2uQR2ZwHxvNeDI3tghG2o+US3s+uWfzTUWCX5szA8+tsKV1HLxHKp03h54soElx4wSfCM3laOacWrPZeyMM8Deoxlym6GJgKDXW7LYk6j7EsXSsLGBTEQi7GLq26hlBNaJPhTrdNfDuXfVYXPzSUGz2s/JUIo=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"herumi@nifty.com","To":"gcc-patches@gcc.gnu.org","Cc":"rguenther@suse.de, jeffreyalaw@gmail.com, ubizjak@gmail.com,\n MITSUNARI Shigeo ","Subject":"[PATCH v2 1/3] expmed: Optimize 32-bit unsigned division by constants\n on 64-bit targets","Date":"Sun, 3 May 2026 14:34:49 +0900","Message-ID":"<20260503053451.48504-2-herumi@nifty.com>","X-Mailer":"git-send-email 2.43.0","In-Reply-To":"<20260503053451.48504-1-herumi@nifty.com>","References":"<727728f8-76e5-457b-ab9f-d650550e0702@gmail.com>\n <20260503053451.48504-1-herumi@nifty.com>","MIME-Version":"1.0","Content-Transfer-Encoding":"8bit","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed; d=nifty.com;\n s=default-1th84yt82rvi; t=1777786541;\n bh=1YmUeMqvRCe6uAj/q0Ww6fH2OllQqusYY4u723BkxkM=;\n h=From:To:Cc:Subject:Date:In-Reply-To:References;\n b=p7KnRyClCuqJRNmM/rwpnZwmCnGdksAkj6NU5wX7KoGmnuAJLlYZvcoLD+aqd2mAFREVFTD2\n xbCxmIWGJa+SKBBf8VX09S1Ustn34IKhbI1kh0JPG+n6qiFCQYbenkRZ3y1SytsbQqlQE3W/fu\n eEzf5CLz8Sd9/2zKcNCrU6w3CVIvDAtyhU2J4FwyLLzsA6kdkJB4K59BlzSWPaEb7Nex0CbNwp\n 970TtGlq+GfTn9LkZ9iAbVYh8vDVLHtnUeW3XG5QeaEcZrUB9v5vbKNtZT6ozvgeabNpND8CRQ\n XhlFLPKuZuACbW+B2vQiJM9oFPXCCpE5S4MKdY21QQLd+j5g==","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":"From: MITSUNARI Shigeo \n\nFor 32-bit unsigned integer division by constants that require 33-bit\nmagic multipliers (mh != 0, IsAdd case), use a pre-shifted 64-bit magic\nconstant and a single 64-bit high-part multiply instead of the traditional\nsub/shift/add sequence.\n\nThe 33-bit magic constant (2^32 + ml) is pre-shifted by (32 - post_shift)\nbits, allowing the quotient to be obtained directly from the upper 64 bits\nof a 64x64 multiplication, then truncated to 32 bits.\n\nThis reduces the instruction count for divisions like x/7 from 7\ninstructions to 4 on x86_64.\n\nBefore (x / 7):\n movl %edi, %eax\n imulq $613566757, %rax, %rax\n shrq $32, %rax\n subl %eax, %edi\n shrl %edi\n addl %edi, %eax\n shrl $2, %eax\n\nAfter:\n movabsq $2635249153617166336, %rcx\n movl %edi, %eax\n mulq %rcx\n movl %edx, %eax\n\ngcc/ChangeLog:\n\n* expmed.cc (expand_divmod): For 32-bit unsigned division with\n33-bit magic on 64-bit targets, use pre-shifted 64-bit multiply.\n---\n gcc/expmed.cc | 86 ++++++++++++++++++++++++++++++++++++---------------\n 1 file changed, 61 insertions(+), 25 deletions(-)","diff":"diff --git a/gcc/expmed.cc b/gcc/expmed.cc\nindex d57ea78d6b1..443ac09caeb 100644\n--- a/gcc/expmed.cc\n+++ b/gcc/expmed.cc\n@@ -4523,31 +4523,67 @@ expand_divmod (int rem_flag, enum tree_code code, machine_mode mode,\n \n \t\t\tif (mh != 0)\n \t\t\t {\n-\t\t\t rtx t1, t2, t3, t4;\n-\n-\t\t\t if (post_shift - 1 >= BITS_PER_WORD)\n-\t\t\t goto fail1;\n-\n-\t\t\t extra_cost\n-\t\t\t = (shift_cost (speed, int_mode, post_shift - 1)\n-\t\t\t\t + shift_cost (speed, int_mode, 1)\n-\t\t\t\t + 2 * add_cost (speed, int_mode));\n-\t\t\t t1 = expmed_mult_highpart\n-\t\t\t (int_mode, op0, gen_int_mode (ml, int_mode),\n-\t\t\t NULL_RTX, 1, max_cost - extra_cost);\n-\t\t\t if (t1 == 0)\n-\t\t\t goto fail1;\n-\t\t\t t2 = force_operand (gen_rtx_MINUS (int_mode,\n-\t\t\t\t\t\t\t op0, t1),\n-\t\t\t\t\t\tNULL_RTX);\n-\t\t\t t3 = expand_shift (RSHIFT_EXPR, int_mode,\n-\t\t\t\t\t t2, 1, NULL_RTX, 1);\n-\t\t\t t4 = force_operand (gen_rtx_PLUS (int_mode,\n-\t\t\t\t\t\t\t t1, t3),\n-\t\t\t\t\t\tNULL_RTX);\n-\t\t\t quotient = expand_shift\n-\t\t\t (RSHIFT_EXPR, int_mode, t4,\n-\t\t\t post_shift - 1, tquotient, 1);\n+\t\t\t bool did_64bit_opt = false;\n+\n+\t\t\t /* For 32-bit unsigned division on 64-bit targets,\n+\t\t\t pre-shift the 33-bit magic constant (2^32 + ml)\n+\t\t\t into a 64-bit value and use a single 64-bit\n+\t\t\t high-part multiply instead of the sub/shift/add\n+\t\t\t sequence.\n+\t\t\t Pre-shift by (32 - post_shift) so that the high\n+\t\t\t 64 bits of (x64 * magic) give the quotient\n+\t\t\t directly.\n+\t\t\t Note: mh!=0 implies pre_shift==0. */\n+\t\t\t if (size == 32 && post_shift >= 1)\n+\t\t\t {\n+\t\t\t\tscalar_int_mode wide_mode\n+\t\t\t\t = GET_MODE_WIDER_MODE (int_mode).require ();\n+\t\t\t\tunsigned HOST_WIDE_INT magic\n+\t\t\t\t = (ml + (HOST_WIDE_INT_1U << 32))\n+\t\t\t\t << (32 - post_shift);\n+\t\t\t\tstart_sequence ();\n+\t\t\t\trtx x64 = convert_to_mode (wide_mode, op0, 1);\n+\t\t\t\trtx hi = expmed_mult_highpart (wide_mode, x64,\n+\t\t\t\t gen_int_mode (magic, wide_mode),\n+\t\t\t\t NULL_RTX, 1, max_cost);\n+\t\t\t\trtx_insn *insns = end_sequence ();\n+\t\t\t\tif (hi != NULL_RTX)\n+\t\t\t\t {\n+\t\t\t\t emit_insn (insns);\n+\t\t\t\t quotient = gen_lowpart (int_mode, hi);\n+\t\t\t\t did_64bit_opt = true;\n+\t\t\t\t }\n+\t\t\t }\n+\n+\t\t\t if (!did_64bit_opt)\n+\t\t\t {\n+\t\t\t\trtx t1, t2, t3, t4;\n+\n+\t\t\t\tif (post_shift - 1 >= BITS_PER_WORD)\n+\t\t\t\t goto fail1;\n+\n+\t\t\t\textra_cost\n+\t\t\t\t = (shift_cost (speed, int_mode,\n+\t\t\t\t\t\t post_shift - 1)\n+\t\t\t\t + shift_cost (speed, int_mode, 1)\n+\t\t\t\t + 2 * add_cost (speed, int_mode));\n+\t\t\t\tt1 = expmed_mult_highpart\n+\t\t\t\t (int_mode, op0, gen_int_mode (ml, int_mode),\n+\t\t\t\t NULL_RTX, 1, max_cost - extra_cost);\n+\t\t\t\tif (t1 == 0)\n+\t\t\t\t goto fail1;\n+\t\t\t\tt2 = force_operand (gen_rtx_MINUS (int_mode,\n+\t\t\t\t\t\t\t\t op0, t1),\n+\t\t\t\t\t\t\tNULL_RTX);\n+\t\t\t\tt3 = expand_shift (RSHIFT_EXPR, int_mode,\n+\t\t\t\t\t\t t2, 1, NULL_RTX, 1);\n+\t\t\t\tt4 = force_operand (gen_rtx_PLUS (int_mode,\n+\t\t\t\t\t\t\t\t t1, t3),\n+\t\t\t\t\t\t\tNULL_RTX);\n+\t\t\t\tquotient = expand_shift\n+\t\t\t\t (RSHIFT_EXPR, int_mode, t4,\n+\t\t\t\t post_shift - 1, tquotient, 1);\n+\t\t\t }\n \t\t\t }\n \t\t\telse\n \t\t\t {\n","prefixes":["v2","1/3"]}