From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f42.google.com (mail-wr1-f42.google.com [209.85.221.42]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C3D1027602C for ; Mon, 12 Jan 2026 13:23:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.42 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768224206; cv=none; b=liRrx28Zmu/eNpUvWYLszWVAdz+QljdGmc+NtLSSsDU9PwUPLe+Xm5j6dTGFhPU0YpUD5skF/3ttNw6w2BuCoLU3mUFDl/eW6zJk4IrlzbAlPHdm4lFGREVzhgk+jAjuGYJ/jo+2aNqjUtOXfFcOT6Zgf6P8jYG/+D1l05NLiv0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768224206; c=relaxed/simple; bh=+pvkVgNC7r59/mTg+cUE9cqE/l9YvtiuVxga6PvQ/ts=; h=Date:From:To:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=AIbSOCxnSOyBTdALnjggX2NKFwPqMpyh9oZOkIC1BuzsJDJfecVtfvxtZmAGqhWmvAvhMPnGSdrjH3fAmwEpHpmCHilLlX4pMu4q+GwSn9Eq277kUbnl+5vdvRx7R9/Eg4Hje9t0S2Z5htIZtQxMAHQFttK236wKz1kFkKgWshQ= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ANVGPF/l; arc=none smtp.client-ip=209.85.221.42 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ANVGPF/l" Received: by mail-wr1-f42.google.com with SMTP id ffacd0b85a97d-42fb2314eb0so5319039f8f.2 for ; Mon, 12 Jan 2026 05:23:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768224203; x=1768829003; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:subject:cc:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=gD0Nf2K75Ik3M+lS+6xa+Cr0dUXpU/U5rKzOZ67uqHU=; b=ANVGPF/ltRT0rvKQGLPsIMcy3zo6a1v9IP1UGc6mSwNeVh16FKAQ4shebeEjWVoDBf EnnYHPoHIZihlQaX45Lm6p4J0xnjvX7MRn9s6aQRWzi5TZuME8tig2l0eVOBEeStXVl0 kraAz9IQ96ykC2lzMSPLx9kBvMqBvzKE+jqDRT+MKyf5JY4tqEfvz6DG4UiOfY8KlyCR 6iW66HEsIkcIoRTAMkJjx9OeKWXyD6dz35gkWZZMRFEBYZnAKNcu6lin8WnOpJPTGM6X HNtbgIS833i/Lengrdn+NNYqVko3tw6p14SPcR8xezw0F1aLBjX7GqsPOY+zJFt98gMn 0Gbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768224203; x=1768829003; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:subject:cc:to:from:date:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=gD0Nf2K75Ik3M+lS+6xa+Cr0dUXpU/U5rKzOZ67uqHU=; b=Bst7vhZhPCfDpGzrPcnGOctmchXjN3o7ipJAyWsT6vCWg1HpPX+6fFvwQXUfTab5ol HTA32V4OBGiyxERutt46y3H0Kb+TvMH8sk6+4pyzrBSbjnsIHTV+SY3vSjV+kVu/0k5x kD5ZonAw6aBs6+bcaVV0/gBna+3xhDGs7biSXR1si2NKvLCaZ2j6xMtrgad5lhQ0lmFi BKb219jzUUkgD0hU/V7fTIDthAg80n3kpmw3tKYrF/rteucuoGxLskPHjnQxFo7STWZw DQmq+wd8ruPyG7pferil+IiExdfQPstsEk5keie1b22VRjdg89G6F1ZS0q9m53MfRZja SrYQ== X-Forwarded-Encrypted: i=1; AJvYcCURQGKPPg8Z6rm0o1dtuF0xq/4yDu3qd4+H7OudWr2du9TieSAbcWuRHbjamc+sOIPmgPThiFR4FxeSCIE=@vger.kernel.org X-Gm-Message-State: AOJu0YwlhKFodsg+osEM2uB3TeSLlIXzdKYN51ENW9TwALqy5wZmRTtn YdVqmKhMQxhlV21fba+HemAylqf+lGX5pwnFkNqaDQ6rSTu4d0XDBDyU X-Gm-Gg: AY/fxX55WBQ69mqCmWSTo3ptOeRP1l9tNNzFu1fqoLpr0xrQw2DzGV3O7f0ARTeREet bHjYFwRep6jiaVv47/R/T6sGFnNYuLARumQDXMW2T+7E2wavuxA+INaAAx7OLCK4epCuU3wxvLJ aoG0puF0vqRYb15h9iqiiOFzQNOxP8U+54DP87AzvkgbkmJ/vytUz5xQ7hqmaDe+7Y5agxBDpTT gTZIGuoF3ZvnEkQnrXgO8xokM/lXH0ZyNsD9ZpDn0iswQ5GbjNixhthSxrWLcoAAwLOXGSbZnwu 4dBd7s7VRES8KZaX0EXFEua5miFsAIG9DN0myx8cQcZKrrrwygu8Y80JCsp8Qd0h0HeVysjD0H5 Db+Vy9t8cBSwgT6ZQ7QvxHmYUbbhtbz1cCeVbv00GjfAQPq/2DbI4sARwb4knfjryvQxCaIqudr KdM/LjTGmRIGA4bwrJSlMbpdsrJJDUZGmyr3OIjRfZTDk+CW1bzNz2 X-Google-Smtp-Source: AGHT+IERZzUB5Iol89xU26ETxQE2VtD0kNzXSD6V/KUIKjkzy3MKJlsCDx6HTQ6WKsuL94wilwO1hA== X-Received: by 2002:a05:6000:2305:b0:431:a33:d864 with SMTP id ffacd0b85a97d-432c3790a14mr21446483f8f.18.1768224202851; Mon, 12 Jan 2026 05:23:22 -0800 (PST) Received: from pumpkin (82-69-66-36.dsl.in-addr.zen.co.uk. [82.69.66.36]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-432bd5fe67csm38590842f8f.40.2026.01.12.05.23.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Jan 2026 05:23:22 -0800 (PST) Date: Mon, 12 Jan 2026 13:23:20 +0000 From: David Laight To: "Maciej W. Rozycki" Cc: Yury Norov , Petr Tesarik , Yury Norov , Rasmus Villemoes , Richard Henderson , Matt Turner , Magnus Lindholm , Vineet Gupta , Geert Uytterhoeven , Thomas Bogendoerfer , Madhavan Srinivasan , Michael Ellerman , Heiko Carstens , Vasily Gorbik , Alexander Gordeev , Chris Zankel , Max Filippov , Patrik Jakobsson , Maarten Lankhorst , Maxime Ripard , Thomas Zimmermann , David Airlie , Simona Vetter , Robin Murphy , Joerg Roedel , Will Deacon , Jakub Kicinski , Andrew Lunn , "David S. Miller" , Eric Dumazet , Paolo Abeni , Oliver Neukum , Arnd Bergmann , Kuan-Wei Chiu , Andrew Morton , Marcel Holtmann , Johan Hedberg , Luiz Augusto von Dentz , Pablo Neira Ayuso , Florian Westphal , linux-kernel@vger.kernel.org Subject: Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded Message-ID: <20260112132320.1a1ddbd7@pumpkin> In-Reply-To: References: <1ce341045ad0487c66ca21003f9974916aba0bce.1767975412.git.ptesarik@suse.com> <20260110115439.184b7a66@pumpkin> <20260111104002.3e017fe2@pumpkin> <20260111235745.53d16a59@pumpkin> X-Mailer: Claws Mail 4.1.1 (GTK 3.24.38; arm-unknown-linux-gnueabihf) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit On Mon, 12 Jan 2026 11:21:59 +0000 (GMT) "Maciej W. Rozycki" wrote: > On Sun, 11 Jan 2026, David Laight wrote: > > > > If you have a population count instruction such as CTPOP on EV67 Alpha, > > > you can do it in two instructions, such as: > > > > > > ctpop $16, $0 > > > cmpeq $0, 1, $0 > > > > > > so there seems to be room for improvement here, but GCC stubbornly refuses > > > to produce this instruction sequence for this code: > > > > > > bool is_power_of_2(unsigned long n) > > > { > > > return __builtin_popcountl(n) == 1; > > > } > > > > > > apparently owing to no insn cost set for the POPCOUNT RTX in the backend > > > causing the middle end to pick up some default. Instead GCC comes up with > > > what can be coded in C as: > > > > > > bool is_power_of_2(unsigned long n) > > > { > > > return n - 1 < (n ^ (n - 1)); > > > } > > > > Not seen that one - and not thought of popcnt, far too new for me. > > (I learnt asm for a pdp11 first...) > > It does show up as an RTL operation in the compiler; it's a good way to > discover stuff. > > > > which seems an interesting alternative that produces 3 instructions only > > > across Alpha, MIPS and RISC-V targets. It's 5 instructions on POWER and > > > x86-64 vs 8 and 9 respectively with our current implementation. There are > > > no branches produced here, although an inline expansion will likely end > > > with one. > > > > I'm seeing: > > is_power_of_2: > > leaq -1(%rdi), %rax > > xorq %rax, %rdi > > cmpq %rdi, %rax > > setb %al > > retq > > on x86-64 - which is really 3 instructions. > > Ack, this is `unsigned long' vs `bool' return type. I'm just too used to > RISC psABIs. FWIW I have this: > > leaq -1(%rdi), %rax > xorq %rax, %rdi > cmpq %rdi, %rax > setb %al > movzbl %al, %eax > ret > > in the former case and I take it `bool' is 8-bit on x86. That was _Bool on godbolt, it you return 'int' the extra 'zero extend' is needed. SETcc was added for 386 (I still forget about it) and someone assumed you wouldn't want the 'word' variant. (It isn't as though they couldn't have allocated another row of the 0F opcode to it.) I sort of hate 'bool' types, something sane has to happen for 'a & b' when the bit patterns are unexpected - and it ought to be well defined. The traditional C where 'a > b' generates 0 or 1 is fine. > > While using the popcnt instruction would reduce it by one, it will only > > be faster on amd zen cpu, on intel cpu popcnt has a latency of 3 and only > > executes on p1 (according to Agner). > > Ack. I've lost track of x86 after ~Pentium Pro. Those were the days :-) I do remember something from one of the Intel manuals of that period about not intermixing data with code because of the possibility of the cpu speculatively executing the data following a branch and if the data happened to be a floating point trig function it had to wait for it to finish. SLS isn't a modern thing. > > > > I suspect there may not be one, but all these 'tricks' come from the 1970s > > > > (or earlier) and don't allow for the behaviour of modern cpu with multiple > > > > execution units and long pipelines. > > > > > > As we can see you never know. I've sent a code update proposal. > > > > I'd suggest moving is_power_of_2() to bits.h as: > > #define is_power_of_2(n) ({ auto _n = n; _n - 1 < _n ^ (_n - 1); }) > > and add: > > #define is_zero_or_power_of_2(n) ({ auto _n = n; _n & (_n - 1) != 0; }) > > I'll leave it as an exercise for someone else. I might add it to the patchset I'm writing - mostly bits.h > > > The use of the population count operation can be considered separately, > > > but we'd have to be careful here as the quality of code produced by the > > > intrinsic varies, e.g. with pre-EV67 Alpha, RISC-V and VAX (!) GCC emits > > > code equivalent to my proposal, but with MIPS or x86-64 it resorts to a > > > libcall, so a guarding condition would be required. So I'd leave it for > > > another occasion. > > > > I'd guess that many of those popcnt instructions aren't actually as fast > > as the dec/xor pair. > > With EV67 Alpha and POWER being proper RISC architectures I'd expect the > instruction to be implemented using a dedicated logic gate network. After > all the population count operation is just an n-operand addition of 1-bit > inputs, so not a big deal. The propagation delay is probably on the same > order of magnitude as with a 2-operand n-bit adder, so the operation ought > to fit in a single pipeline stage. There are some tricks that can be done to reduce the propagation delay of a 64bit add from ~64 (for the ripple carry) to nearer 16 (add each byte with and without a carry input and then use a mux to select the correct output). That may not work for popcnt. Also I suspect that multiply isn't single clock, so multicycle instructions have to be supported. Throw silicon at multiply and you can reduce it to full-adders with a carry- chain the length of the result, not sure you can do much better. For my sins I re-implemented the Nios-II cpu a couple of years ago (because Intel had deprecated it), the single 64bit add needed at the end of multiply (done by fgpa DSP blocks) made it impossible to feed the product straight back into the ALU for the next cycle. My version is about the same size, 1 clock faster in a few places (like predicted taken branches and the stall if a multiply result (and I think memory reads) is needed in the next-but-one instruction. FMax is a bit lower, but we were constrained by the PCIe interface to 67.5MHz and it was fast enough. David > > I suppose it's just a matter of whether you want to dedicate a piece of > silicon just for this somewhat exotic operation, and in the old days the > answer would be no for a general-purpose CPU owing to manufacturing cost > and die size limitation, while nowadays with process shrinkage and power > consumption reduction it may have become worthwhile. > > > But the libcall is just plain stupid. > > It could just be that it's a recent addition as my compilation of GCC for > x86-64 and MIPS turns out to be version 11 and 13 respectively, while I > have version 15 for the remaining targets. Indeed when I tried now GCC 14 > that I have at hand for another MIPS configuration the libcall is gone, so > the optimisation must have been added in that version. > > Of course you still need a libcall for a plain `__builtin_popcountl' call > where there's no suitable hardware instruction available. > > Maciej >