1353358Sdim//===-- clzdi2.c - Implement __clzdi2 -------------------------------------===//
2353358Sdim//
3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4353358Sdim// See https://llvm.org/LICENSE.txt for license information.
5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6353358Sdim//
7353358Sdim//===----------------------------------------------------------------------===//
8353358Sdim//
9353358Sdim// This file implements count leading zeros for 64bit arguments.
10353358Sdim//
11353358Sdim//===----------------------------------------------------------------------===//
12353358Sdim
13276789Sdim#include "../assembly.h"
14276789Sdim
15276789Sdim	.syntax unified
16276789Sdim	.text
17327952Sdim	DEFINE_CODE_STATE
18276789Sdim
19276789Sdim	.p2align	2
20276789SdimDEFINE_COMPILERRT_FUNCTION(__clzdi2)
21276789Sdim#ifdef __ARM_FEATURE_CLZ
22276789Sdim#ifdef __ARMEB__
23276789Sdim	cmp	r0, 0
24276789Sdim	itee ne
25276789Sdim	clzne	r0, r0
26276789Sdim	clzeq	r0, r1
27276789Sdim	addeq	r0, r0, 32
28276789Sdim#else
29276789Sdim	cmp	r1, 0
30276789Sdim	itee ne
31276789Sdim	clzne	r0, r1
32276789Sdim	clzeq	r0, r0
33276789Sdim	addeq	r0, r0, 32
34276789Sdim#endif
35276789Sdim	JMP(lr)
36276789Sdim#else
37353358Sdim	// Assumption: n != 0
38276789Sdim
39353358Sdim	// r0: n
40353358Sdim	// r1: upper half of n, overwritten after check
41353358Sdim	// r1: count of leading zeros in n + 1
42353358Sdim	// r2: scratch register for shifted r0
43276789Sdim#ifdef __ARMEB__
44276789Sdim	cmp	r0, 0
45276789Sdim	moveq	r0, r1
46276789Sdim#else
47276789Sdim	cmp	r1, 0
48276789Sdim	movne	r0, r1
49276789Sdim#endif
50276789Sdim	movne	r1, 1
51276789Sdim	moveq	r1, 33
52276789Sdim
53353358Sdim	// Basic block:
54353358Sdim	// if ((r0 >> SHIFT) == 0)
55353358Sdim	//   r1 += SHIFT;
56353358Sdim	// else
57353358Sdim	//   r0 >>= SHIFT;
58353358Sdim	// for descending powers of two as SHIFT.
59276789Sdim#define BLOCK(shift) \
60276789Sdim	lsrs	r2, r0, shift; \
61276789Sdim	movne	r0, r2; \
62276789Sdim	addeq	r1, shift \
63276789Sdim
64276789Sdim	BLOCK(16)
65276789Sdim	BLOCK(8)
66276789Sdim	BLOCK(4)
67276789Sdim	BLOCK(2)
68276789Sdim
69353358Sdim	// The basic block invariants at this point are (r0 >> 2) == 0 and
70353358Sdim	// r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1.
71353358Sdim	//
72353358Sdim	// r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1)
73353358Sdim	// ---+----------------+----------------+------------+--------------
74353358Sdim	// 1  | 1              | 0              | 0          | 1
75353358Sdim	// 2  | 0              | 1              | -1         | 0
76353358Sdim	// 3  | 0              | 1              | -1         | 0
77353358Sdim	//
78353358Sdim	// The r1's initial value of 1 compensates for the 1 here.
79276789Sdim	sub	r0, r1, r0, lsr #1
80276789Sdim
81276789Sdim	JMP(lr)
82276789Sdim#endif // __ARM_FEATURE_CLZ
83276789SdimEND_COMPILERRT_FUNCTION(__clzdi2)
84309124Sdim
85309124SdimNO_EXEC_STACK_DIRECTIVE
86309124Sdim
87