Loading...
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