From patchwork Tue Nov 26 00:29:16 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 21759 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-pb0-f69.google.com (mail-pb0-f69.google.com [209.85.160.69]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 2DBD120299 for ; Tue, 26 Nov 2013 00:29:26 +0000 (UTC) Received: by mail-pb0-f69.google.com with SMTP id md12sf12747787pbc.4 for ; Mon, 25 Nov 2013 16:29:26 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:message-id:date:from:user-agent :mime-version:to:cc:subject:references:in-reply-to:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-unsubscribe:content-type; bh=zwscMrV7HVsAPqwgZMu/HgXZ+HAfzMJC2/Ik9SnQOJU=; b=WYUb2BjR8XohG6QyM1MRofziBLfThx5mjgkEeyiQfLaE5N3dcj0nCY+/VYaYdtZZII by9oI1Bpw0dhQuTGetGvriJDpHDTx6V1z4sdKoDdHRzf9M/EmWQUXixgenxf5Q1rzicO tvBcg9yB9sBQIVYu94NS2kvwCdpAHUyP7/MA+SflyesfETdE/uaopNE0wF+5ghBh+czL yJoLG6lYJoGNra0zmWnCRW0xoPdLJEw5w1FQxsXDjHxto/+79M1Tt1rMrd6xZfVBvn0V nQ1UErbwgU4W7c3+rLEyi4iTXApLxQIhB7BCN9dW/RWcvHwj4nMoyBi/kySpLQgpwEFn /YjA== X-Gm-Message-State: ALoCoQkaMN607EgHuEwiw3CY2S0KNMqE9WUrWhmSLaSHQ67kbncqo89qzmINN70NCLtH4n79S0HB X-Received: by 10.66.117.170 with SMTP id kf10mr9728612pab.35.1385425766028; Mon, 25 Nov 2013 16:29:26 -0800 (PST) X-BeenThere: patchwork-forward@linaro.org Received: by 10.49.104.40 with SMTP id gb8ls2313570qeb.27.gmail; Mon, 25 Nov 2013 16:29:25 -0800 (PST) X-Received: by 10.52.113.194 with SMTP id ja2mr23858vdb.61.1385425765855; Mon, 25 Nov 2013 16:29:25 -0800 (PST) Received: from mail-vb0-f52.google.com (mail-vb0-f52.google.com [209.85.212.52]) by mx.google.com with ESMTPS id im16si16474922vec.54.2013.11.25.16.29.25 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 25 Nov 2013 16:29:25 -0800 (PST) Received-SPF: neutral (google.com: 209.85.212.52 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=209.85.212.52; Received: by mail-vb0-f52.google.com with SMTP id f13so3252764vbg.25 for ; Mon, 25 Nov 2013 16:29:25 -0800 (PST) X-Received: by 10.58.54.69 with SMTP id h5mr3595791vep.25.1385425765563; Mon, 25 Nov 2013 16:29:25 -0800 (PST) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patches@linaro.org Received: by 10.220.174.196 with SMTP id u4csp173326vcz; Mon, 25 Nov 2013 16:29:24 -0800 (PST) X-Received: by 10.68.189.34 with SMTP id gf2mr20649944pbc.91.1385425763792; Mon, 25 Nov 2013 16:29:23 -0800 (PST) Received: from mail-pb0-f42.google.com (mail-pb0-f42.google.com [209.85.160.42]) by mx.google.com with ESMTPS id bo6si6884016pab.230.2013.11.25.16.29.23 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 25 Nov 2013 16:29:23 -0800 (PST) Received-SPF: neutral (google.com: 209.85.160.42 is neither permitted nor denied by best guess record for domain of kugan.vivekanandarajah@linaro.org) client-ip=209.85.160.42; Received: by mail-pb0-f42.google.com with SMTP id uo5so6959824pbc.1 for ; Mon, 25 Nov 2013 16:29:23 -0800 (PST) X-Received: by 10.68.197.73 with SMTP id is9mr20630916pbc.75.1385425763240; Mon, 25 Nov 2013 16:29:23 -0800 (PST) Received: from [192.168.0.100] ([1.130.208.44]) by mx.google.com with ESMTPSA id hw10sm76117336pbc.24.2013.11.25.16.29.19 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 25 Nov 2013 16:29:22 -0800 (PST) Message-ID: <5293EB5C.3090402@linaro.org> Date: Tue, 26 Nov 2013 11:29:16 +1100 From: Kugan User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.1.0 MIME-Version: 1.0 To: Ian Lance Taylor CC: "gcc-patches@gcc.gnu.org" , Richard Earnshaw , "patches@linaro.org" Subject: Re: [RFC][LIBGCC][1 of 2] 64 bit divide implementation for processor without hw divide instruction References: <52900902.9020602@linaro.org> <529009F5.10208@linaro.org> In-Reply-To: X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: kugan.vivekanandarajah@linaro.org X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 209.85.212.52 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Precedence: list Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org List-ID: X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , On 24/11/13 02:14, Ian Lance Taylor wrote: > Kugan writes: > >> This RFC patch series implements a simple align divisor shift dividend >> method. >> >> Regression tested on arm-none-linux-gnueabi with no issues. >> >> OK? >> >> Thanks, >> Kugan >> >> +2013-11-22 Kugan Vivekanandarajah >> + >> + * libgcc/libgcc2.c (__udivmoddi4): Define new implementation when >> + HAVE_NO_HW_DIVIDE is defined, for processors without any divide >> + instructions. > > > The code looks fine to me. > > You should document HAVE_NO_HW_DIVIDE in gcc/doc/tm.texi in the Library > Calls section. The macro should probably be something like > TARGET_HAS_NO_HW_DIVIDE. > Thanks for the review. Is this OK for trunk now? +2013-11-26 Kugan Vivekanandarajah + + * libgcc/libgcc2.c (__udivmoddi4): Define new implementation when + TARGET_HAS_NO_HW_DIVIDE is defined, for processors without any divide + instructions. + +2013-11-26 Kugan Vivekanandarajah + + * doc/tm.texi.in (TARGET_HAS_NO_HW_DIVIDE): Define. + * doc/tm.texi (TARGET_HAS_NO_HW_DIVIDE): Regenerate. + Thanks, Kugan diff --git a/gcc/doc/tm.texi b/gcc/doc/tm.texi index 925d93f..c9697f1 100644 --- a/gcc/doc/tm.texi +++ b/gcc/doc/tm.texi @@ -5365,6 +5365,14 @@ If this macro evaluates to @code{false} the comparison functions return in @file{libgcc.a}, you do not need to define this macro. @end defmac +@defmac TARGET_HAS_NO_HW_DIVIDE +This macro should be defined if the target has no hardware divide +instructions. If this macro is defined, GCC will use an algorithm which +make use of simple logical and arithmetic operations for 64-bit +division. If the macro is not defined, GCC will use an algorithm which +make use of a 64-bit by 32-bit divide primitive. +@end defmac + @cindex @code{EDOM}, implicit usage @findex matherr @defmac TARGET_EDOM diff --git a/gcc/doc/tm.texi.in b/gcc/doc/tm.texi.in index edca600..03e6662 100644 --- a/gcc/doc/tm.texi.in +++ b/gcc/doc/tm.texi.in @@ -4205,6 +4205,14 @@ If this macro evaluates to @code{false} the comparison functions return in @file{libgcc.a}, you do not need to define this macro. @end defmac +@defmac TARGET_HAS_NO_HW_DIVIDE +This macro should be defined if the target has no hardware divide +instructions. If this macro is defined, GCC will use an algorithm which +make use of simple logical and arithmetic operations for 64-bit +division. If the macro is not defined, GCC will use an algorithm which +make use of a 64-bit by 32-bit divide primitive. +@end defmac + @cindex @code{EDOM}, implicit usage @findex matherr @defmac TARGET_EDOM diff --git a/libgcc/libgcc2.c b/libgcc/libgcc2.c index bec411b..8c4cc6a 100644 --- a/libgcc/libgcc2.c +++ b/libgcc/libgcc2.c @@ -934,6 +934,74 @@ __parityDI2 (UDWtype x) #endif #ifdef L_udivmoddi4 +#ifdef TARGET_HAS_NO_HW_DIVIDE + +#if (defined (L_udivdi3) || defined (L_divdi3) || \ + defined (L_umoddi3) || defined (L_moddi3)) +static inline __attribute__ ((__always_inline__)) +#endif +UDWtype +__udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp) +{ + UDWtype q = 0, r = n, y = d; + UWtype lz1, lz2, i, k; + + /* Implements align divisor shift dividend method. This algorithm + aligns the divisor under the dividend and then perform number of + test-subtract iterations which shift the dividend left. Number of + iterations is k + 1 where k is the number of bit positions the + divisor must be shifted left to align it under the dividend. + quotient bits can be saved in the rightmost positions of the dividend + as it shifts left on each test-subtract iteration. */ + + if (y <= r) + { + lz1 = __builtin_clzll (d); + lz2 = __builtin_clzll (n); + + k = lz1 - lz2; + y = (y << k); + + /* Dividend can exceed 2 ^ (width − 1) − 1 but still be less than the + aligned divisor. Normal iteration can drops the high order bit + of the dividend. Therefore, first test-subtract iteration is a + special case, saving its quotient bit in a separate location and + not shifting the dividend. */ + if (r >= y) + { + r = r - y; + q = (1ULL << k); + } + + if (k > 0) + { + y = y >> 1; + + /* k additional iterations where k regular test subtract shift + dividend iterations are done. */ + i = k; + do + { + if (r >= y) + r = ((r - y) << 1) + 1; + else + r = (r << 1); + i = i - 1; + } while (i != 0); + + /* First quotient bit is combined with the quotient bits resulting + from the k regular iterations. */ + q = q + r; + r = r >> k; + q = q - (r << k); + } + } + + if (rp) + *rp = r; + return q; +} +#else #if (defined (L_udivdi3) || defined (L_divdi3) || \ defined (L_umoddi3) || defined (L_moddi3)) @@ -1152,6 +1220,7 @@ __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp) return ww.ll; } #endif +#endif #ifdef L_divdi3 DWtype