1/*
2 * arch/alpha/lib/ev6-divide.S
3 *
4 * 21264 version contributed by Rick Gorton <rick.gorton@alpha-processor.com>
5 *
6 * Alpha division..
7 */
8
9/*
10 * The alpha chip doesn't provide hardware division, so we have to do it
11 * by hand.  The compiler expects the functions
12 *
13 *	__divqu: 64-bit unsigned long divide
14 *	__remqu: 64-bit unsigned long remainder
15 *	__divqs/__remqs: signed 64-bit
16 *	__divlu/__remlu: unsigned 32-bit
17 *	__divls/__remls: signed 32-bit
18 *
19 * These are not normal C functions: instead of the normal
20 * calling sequence, these expect their arguments in registers
21 * $24 and $25, and return the result in $27. Register $28 may
22 * be clobbered (assembly temporary), anything else must be saved.
23 *
24 * In short: painful.
25 *
26 * This is a rather simple bit-at-a-time algorithm: it's very good
27 * at dividing random 64-bit numbers, but the more usual case where
28 * the divisor is small is handled better by the DEC algorithm
29 * using lookup tables. This uses much less memory, though, and is
30 * nicer on the cache.. Besides, I don't know the copyright status
31 * of the DEC code.
32 */
33
34/*
35 * My temporaries:
36 *	$0 - current bit
37 *	$1 - shifted divisor
38 *	$2 - modulus/quotient
39 *
40 *	$23 - return address
41 *	$24 - dividend
42 *	$25 - divisor
43 *
44 *	$27 - quotient/modulus
45 *	$28 - compare status
46 *
47 * Much of the information about 21264 scheduling/coding comes from:
48 *	Compiler Writer's Guide for the Alpha 21264
49 *	abbreviated as 'CWG' in other comments here
50 *	ftp.digital.com/pub/Digital/info/semiconductor/literature/dsc-library.html
51 * Scheduling notation:
52 *	E	- either cluster
53 *	U	- upper subcluster; U0 - subcluster U0; U1 - subcluster U1
54 *	L	- lower subcluster; L0 - subcluster L0; L1 - subcluster L1
55 * Try not to change the actual algorithm if possible for consistency.
56 */
57
58#define halt .long 0
59
60/*
61 * Select function type and registers
62 */
63#define mask	$0
64#define divisor	$1
65#define compare $28
66#define tmp1	$3
67#define tmp2	$4
68
69#ifdef DIV
70#define DIV_ONLY(x,y...) x,##y
71#define MOD_ONLY(x,y...)
72#define func(x) __div##x
73#define modulus $2
74#define quotient $27
75#define GETSIGN(x) xor $24,$25,x
76#define STACK 48
77#else
78#define DIV_ONLY(x,y...)
79#define MOD_ONLY(x,y...) x,##y
80#define func(x) __rem##x
81#define modulus $27
82#define quotient $2
83#define GETSIGN(x) bis $24,$24,x
84#define STACK 32
85#endif
86
87/*
88 * For 32-bit operations, we need to extend to 64-bit
89 */
90#ifdef INTSIZE
91#define ufunction func(lu)
92#define sfunction func(l)
93#define LONGIFY(x) zapnot x,15,x
94#define SLONGIFY(x) addl x,0,x
95#else
96#define ufunction func(qu)
97#define sfunction func(q)
98#define LONGIFY(x)
99#define SLONGIFY(x)
100#endif
101
102.set noat
103.align	4
104.globl	ufunction
105.ent	ufunction
106ufunction:
107	subq	$30,STACK,$30		# E :
108	.frame	$30,STACK,$23
109	.prologue 0
110
1117:	stq	$1, 0($30)		# L :
112	bis	$25,$25,divisor		# E :
113	stq	$2, 8($30)		# L : L U L U
114
115	bis	$24,$24,modulus		# E :
116	stq	$0,16($30)		# L :
117	bis	$31,$31,quotient	# E :
118	LONGIFY(divisor)		# E : U L L U
119
120	stq	tmp1,24($30)		# L :
121	LONGIFY(modulus)		# E :
122	bis	$31,1,mask		# E :
123	DIV_ONLY(stq tmp2,32($30))	# L : L U U L
124
125	beq	divisor, 9f			/* div by zero */
126	/*
127	 * In spite of the DIV_ONLY being either a non-instruction
128	 * or an actual stq, the addition of the .align directive
129	 * below ensures that label 1 is going to be nicely aligned
130	 */
131
132	.align	4
133#ifdef INTSIZE
134	/*
135	 * shift divisor left, using 3-bit shifts for
136	 * 32-bit divides as we can't overflow. Three-bit
137	 * shifts will result in looping three times less
138	 * here, but can result in two loops more later.
139	 * Thus using a large shift isn't worth it (and
140	 * s8add pairs better than a sll..)
141	 */
1421:	cmpult	divisor,modulus,compare	# E :
143	s8addq	divisor,$31,divisor	# E :
144	s8addq	mask,$31,mask		# E :
145	bne	compare,1b		# U : U L U L
146#else
1471:	cmpult	divisor,modulus,compare	# E :
148	nop				# E :
149	nop				# E :
150	blt     divisor, 2f		# U : U L U L
151
152	addq	divisor,divisor,divisor	# E :
153	addq	mask,mask,mask		# E :
154	unop				# E :
155	bne	compare,1b		# U : U L U L
156#endif
157
158	/* ok, start to go right again.. */
1592:
160	/*
161	 * Keep things nicely bundled... use a nop instead of not
162	 * having an instruction for DIV_ONLY
163	 */
164#ifdef DIV
165	DIV_ONLY(addq quotient,mask,tmp2) # E :
166#else
167	nop				# E :
168#endif
169	srl	mask,1,mask		# U :
170	cmpule	divisor,modulus,compare	# E :
171	subq	modulus,divisor,tmp1	# E :
172
173#ifdef DIV
174	DIV_ONLY(cmovne compare,tmp2,quotient)	# E : Latency 2, extra map slot
175	nop				# E : as part of the cmovne
176	srl	divisor,1,divisor	# U :
177	nop				# E : L U L U
178
179	nop				# E :
180	cmovne	compare,tmp1,modulus	# E : Latency 2, extra map slot
181	nop				# E : as part of the cmovne
182	bne	mask,2b			# U : U L U L
183#else
184	srl	divisor,1,divisor	# U :
185	cmovne	compare,tmp1,modulus	# E : Latency 2, extra map slot
186	nop				# E : as part of the cmovne
187	bne	mask,2b			# U : U L L U
188#endif
189
1909:	ldq	$1, 0($30)		# L :
191	ldq	$2, 8($30)		# L :
192	nop				# E :
193	nop				# E : U U L L
194
195	ldq	$0,16($30)		# L :
196	ldq	tmp1,24($30)		# L :
197	nop				# E :
198	nop				# E :
199
200#ifdef DIV
201	DIV_ONLY(ldq tmp2,32($30))	# L :
202#else
203	nop				# E :
204#endif
205	addq	$30,STACK,$30		# E :
206	ret	$31,($23),1		# L0 : L U U L
207	.end	ufunction
208
209/*
210 * Uhh.. Ugly signed division. I'd rather not have it at all, but
211 * it's needed in some circumstances. There are different ways to
212 * handle this, really. This does:
213 * 	-a / b = a / -b = -(a / b)
214 *	-a % b = -(a % b)
215 *	a % -b = a % b
216 * which is probably not the best solution, but at least should
217 * have the property that (x/y)*y + (x%y) = x.
218 */
219.align 4
220.globl	sfunction
221.ent	sfunction
222sfunction:
223	subq	$30,STACK,$30		# E :
224	.frame	$30,STACK,$23
225	.prologue 0
226	bis	$24,$25,$28		# E :
227	SLONGIFY($28)			# E :
228	bge	$28,7b			# U :
229
230	stq	$24,0($30)		# L :
231	subq	$31,$24,$28		# E :
232	stq	$25,8($30)		# L :
233	nop				# E : U L U L
234
235	cmovlt	$24,$28,$24	/* abs($24) */ # E : Latency 2, extra map slot
236	nop				# E : as part of the cmov
237	stq	$23,16($30)		# L :
238	subq	$31,$25,$28		# E : U L U L
239
240	stq	tmp1,24($30)		# L :
241	cmovlt	$25,$28,$25	/* abs($25) */ # E : Latency 2, extra map slot
242	nop				# E :
243	bsr	$23,ufunction		# L0: L U L U
244
245	ldq	$24,0($30)		# L :
246	ldq	$25,8($30)		# L :
247	GETSIGN($28)			# E :
248	subq	$31,$27,tmp1		# E : U U L L
249
250	SLONGIFY($28)			# E :
251	ldq	$23,16($30)		# L :
252	cmovlt	$28,tmp1,$27		# E : Latency 2, extra map slot
253	nop				# E : U L L U : as part of the cmov
254
255	ldq	tmp1,24($30)		# L :
256	nop				# E : as part of the cmov
257	addq	$30,STACK,$30		# E :
258	ret	$31,($23),1		# L0 : L U U L
259	.end	sfunction
260