From patchwork Sat Nov 23 01:50:45 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 21720 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-vb0-f69.google.com (mail-vb0-f69.google.com [209.85.212.69]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 7B4B523FDC for ; Sat, 23 Nov 2013 01:50:54 +0000 (UTC) Received: by mail-vb0-f69.google.com with SMTP id m10sf3808972vbh.4 for ; Fri, 22 Nov 2013 17:50:53 -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=Us5jC9nOoSALwVdFd896FN1qanoM0xPTf1L826sXa1Q=; b=dEAfrNm7bypUBcT1NF43ezXJDAdTZzF69R6pqcX9kCQfCdxokz9/z550YmexWiQvP9 WQKYJwWaUDs2gHE1x+lPDRDQsa4Ku2XwJtPxPuoaxW90jfI0wG+aFi8Ou2RvUzLnVp/f UO93/JEMrL5QEeBK33rV2xzYRfRJNx/SNODZS+rkKt2Fz+UQ7xpjr4+vrwbaQ23jbeOZ uXATM5jSJJIWTxzV4zrl6gPcUeJWmLDqkCvgTvnKs1A5DbdbLOj3+fcz6jTVi2CRRqq2 kkIwmOTSH+dJbp7/gvvvgKLqyDoBpJqhv7r1tkMNBsfQXYjqUpDPSCzMYqm5yTEyG/vn SY1Q== X-Gm-Message-State: ALoCoQlIXhWXA+0GeNpkYN+K42+DPIJXFN+1FqjMrM30+eHJZt41BlUplTBi/DLBLyEH25IH6faY X-Received: by 10.58.109.226 with SMTP id hv2mr4824695veb.33.1385171453671; Fri, 22 Nov 2013 17:50:53 -0800 (PST) X-BeenThere: patchwork-forward@linaro.org Received: by 10.49.53.3 with SMTP id x3ls1173728qeo.78.gmail; Fri, 22 Nov 2013 17:50:53 -0800 (PST) X-Received: by 10.52.32.66 with SMTP id g2mr12309767vdi.14.1385171453543; Fri, 22 Nov 2013 17:50:53 -0800 (PST) Received: from mail-vc0-f171.google.com (mail-vc0-f171.google.com [209.85.220.171]) by mx.google.com with ESMTPS id dj3si13529251vcb.119.2013.11.22.17.50.53 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 22 Nov 2013 17:50:53 -0800 (PST) Received-SPF: neutral (google.com: 209.85.220.171 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=209.85.220.171; Received: by mail-vc0-f171.google.com with SMTP id ik5so1440233vcb.30 for ; Fri, 22 Nov 2013 17:50:53 -0800 (PST) X-Received: by 10.220.86.69 with SMTP id r5mr14202903vcl.9.1385171453185; Fri, 22 Nov 2013 17:50:53 -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 u4csp80529vcz; Fri, 22 Nov 2013 17:50:51 -0800 (PST) X-Received: by 10.68.29.72 with SMTP id i8mr5687294pbh.116.1385171450714; Fri, 22 Nov 2013 17:50:50 -0800 (PST) Received: from mail-pb0-f50.google.com (mail-pb0-f50.google.com [209.85.160.50]) by mx.google.com with ESMTPS id xj9si16200979pab.150.2013.11.22.17.50.50 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 22 Nov 2013 17:50:50 -0800 (PST) Received-SPF: neutral (google.com: 209.85.160.50 is neither permitted nor denied by best guess record for domain of kugan.vivekanandarajah@linaro.org) client-ip=209.85.160.50; Received: by mail-pb0-f50.google.com with SMTP id rr13so2104715pbb.9 for ; Fri, 22 Nov 2013 17:50:50 -0800 (PST) X-Received: by 10.68.251.133 with SMTP id zk5mr5640492pbc.69.1385171450182; Fri, 22 Nov 2013 17:50:50 -0800 (PST) Received: from [192.168.0.100] ([1.145.232.183]) by mx.google.com with ESMTPSA id xv2sm56284078pbb.39.2013.11.22.17.50.47 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 22 Nov 2013 17:50:49 -0800 (PST) Message-ID: <529009F5.10208@linaro.org> Date: Sat, 23 Nov 2013 12:50:45 +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: "gcc-patches@gcc.gnu.org" CC: ian@airs.com, 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> In-Reply-To: <52900902.9020602@linaro.org> 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.220.171 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: , Hi All, 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. + diff --git a/libgcc/libgcc2.c b/libgcc/libgcc2.c index bec411b..a1d3fbc 100644 --- a/libgcc/libgcc2.c +++ b/libgcc/libgcc2.c @@ -934,6 +934,74 @@ __parityDI2 (UDWtype x) #endif #ifdef L_udivmoddi4 +#ifdef HAVE_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