From owner-freebsd-hackers@FreeBSD.ORG Sun Jun 7 16:37:25 2015 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 47451EAF for ; Sun, 7 Jun 2015 16:37:25 +0000 (UTC) (envelope-from davide.italiano@gmail.com) Received: from mail-qk0-x22a.google.com (mail-qk0-x22a.google.com [IPv6:2607:f8b0:400d:c09::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 0177C1588 for ; Sun, 7 Jun 2015 16:37:25 +0000 (UTC) (envelope-from davide.italiano@gmail.com) Received: by qkhg32 with SMTP id g32so66825026qkh.0 for ; Sun, 07 Jun 2015 09:37:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=ub7p7sZLXy5JI3o/CF6vhQIuopszJ2SuHxlLXtBqyYA=; b=DJ46ffHFURNl5PVAfGPmX2BgInLdz6CWdA1+j43M8EPqQGlrAyI6OmvmmXzyjdK00i btOApBJPWHe8OAvGekoHw+XOp4vjsYgUOxWg4/FDY4eUzO9rh6PXfPbU30UlMKSAQrVP +d3B7tFGVmNoMxQofFDJeYBEo+3IyY/NNIFS0tomFYl+ynBxfsC0SDlh5n8kkVVySQxv atq0ABJCiwnmRx5Ma3lxiCdFTUp84bREvtFiCopF+Ik3JMUunEU/lLXPieeC3AABfWR8 UgoasRiIbmw+d0hKdttERdD2fGV20YT6vQaQHPWsGPdPC/8Y/Bz0ttk4TKnBXC3gfDQR /oAA== MIME-Version: 1.0 X-Received: by 10.229.185.68 with SMTP id cn4mr15761139qcb.12.1433695043803; Sun, 07 Jun 2015 09:37:23 -0700 (PDT) Sender: davide.italiano@gmail.com Received: by 10.96.106.234 with HTTP; Sun, 7 Jun 2015 09:37:23 -0700 (PDT) In-Reply-To: <20150607135453.GH2499@kib.kiev.ua> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> <20150607135453.GH2499@kib.kiev.ua> Date: Sun, 7 Jun 2015 09:37:23 -0700 X-Google-Sender-Auth: oQLOZVQ2kvTOEuP88jc2p7QVRwg Message-ID: Subject: Re: allow ffs & co. a binary search From: Davide Italiano To: Konstantin Belousov Cc: Erich Dollansky , Hans Petter Selasky , "freebsd-hackers@freebsd.org" Content-Type: text/plain; charset=UTF-8 X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Jun 2015 16:37:25 -0000 On Sun, Jun 7, 2015 at 6:54 AM, Konstantin Belousov wrote: > On Sun, Jun 07, 2015 at 07:52:45PM +0800, Erich Dollansky wrote: >> What I saw is that all CPUs except ARM uses the software version [of ffs]. > > Without quantifiers, this statement is not true. i386 libc function ffs(3) > uses bsfl instruction to do the job. Compilers know about ffs(3) and friends > as well, so e.g. gcc 5.1.0 generates the following code for the given > fragment: > return (ffs(x) + 1); > is translated to > 0: 0f bc c7 bsf %edi,%eax > 3: ba ff ff ff ff mov $0xffffffff,%edx > 8: 0f 44 c2 cmove %edx,%eax > b: 83 c0 02 add $0x2,%eax > (arg in %edi, result in %eax). > > I wrote a patch for amd64 libc long time ago to convert ffs/fls etc to use > of the bitstring instruction, but Bruce Evans argued that this would be > excessive. Your patch is excessive for the similar reasons. > > My guess is that significantly clever compiler would recognize a pattern > used by native ffs implementation and automatically use bitstring > instructions. E.g., this already happens with popcnt and recent > gcc/clang, I am just lazy to verify ffs. > _______________________________________________ > freebsd-hackers@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-hackers > To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org" Clang trunk to the best of my knowledgde hasn't a way to recognize ffs() pattern. http://llvm.org/docs/doxygen/html/LoopIdiomRecognize_8cpp_source.html I can't comment about gcc as long as I'm not familiar with the implementation. -- Davide "There are no solved problems; there are only problems that are more or less solved" -- Henri Poincare