aboutsummaryrefslogtreecommitdiff
path: root/vendor/gmp-6.3.0/mpn/x86/README
blob: 8d7ac9080ddcf6ef3ab31488493b9147ca0ed17a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
Copyright 1999-2002 Free Software Foundation, Inc.

This file is part of the GNU MP Library.

The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of either:

  * the GNU Lesser General Public License as published by the Free
    Software Foundation; either version 3 of the License, or (at your
    option) any later version.

or

  * the GNU General Public License as published by the Free Software
    Foundation; either version 2 of the License, or (at your option) any
    later version.

or both in parallel, as here.

The GNU MP Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received copies of the GNU General Public License and the
GNU Lesser General Public License along with the GNU MP Library.  If not,
see https://www.gnu.org/licenses/.





                      X86 MPN SUBROUTINES


This directory contains mpn functions for various 80x86 chips.


CODE ORGANIZATION

	x86               i386, generic
	x86/i486          i486
	x86/pentium       Intel Pentium (P5, P54)
	x86/pentium/mmx   Intel Pentium with MMX (P55)
	x86/p6            Intel Pentium Pro
	x86/p6/mmx        Intel Pentium II, III
	x86/p6/p3mmx      Intel Pentium III
	x86/k6            \ AMD K6
	x86/k6/mmx        /
	x86/k6/k62mmx     AMD K6-2
	x86/k7            \ AMD Athlon
	x86/k7/mmx        /
	x86/pentium4      \
	x86/pentium4/mmx  | Intel Pentium 4
	x86/pentium4/sse2 /


The top-level x86 directory contains blended style code, meant to be
reasonable on all x86s.



STATUS

The code is well-optimized for AMD and Intel chips, but there's nothing
specific for Cyrix chips, nor for actual 80386 and 80486 chips.



ASM FILES

The x86 .asm files are BSD style assembler code, first put through m4 for
macro processing.  The generic mpn/asm-defs.m4 is used, together with
mpn/x86/x86-defs.m4.  See comments in those files.

The code is meant for use with GNU "gas" or a system "as".  There's no
support for assemblers that demand Intel style code.



STACK FRAME

m4 macros are used to define the parameters passed on the stack, and these
act like comments on what the stack frame looks like too.  For example,
mpn_mul_1() has the following.

        defframe(PARAM_MULTIPLIER, 16)
        defframe(PARAM_SIZE,       12)
        defframe(PARAM_SRC,         8)
        defframe(PARAM_DST,         4)

PARAM_MULTIPLIER becomes `FRAME+16(%esp)', and the others similarly.  The
return address is at offset 0, but there's not normally any need to access
that.

FRAME is redefined as necessary through the code so it's the number of bytes
pushed on the stack, and hence the offsets in the parameter macros stay
correct.  At the start of a routine FRAME should be zero.

        deflit(`FRAME',0)
	...
	deflit(`FRAME',4)
	...
	deflit(`FRAME',8)
	...

Helper macros FRAME_pushl(), FRAME_popl(), FRAME_addl_esp() and
FRAME_subl_esp() exist to adjust FRAME for the effect of those instructions,
and can be used instead of explicit definitions if preferred.
defframe_pushl() is a combination FRAME_pushl() and defframe().

There's generally some slackness in redefining FRAME.  If new values aren't
going to get used then the redefinitions are omitted to keep from cluttering
up the code.  This happens for instance at the end of a routine, where there
might be just four pops and then a ret, so FRAME isn't getting used.

Local variables and saved registers can be similarly defined, with negative
offsets representing stack space below the initial stack pointer.  For
example,

	defframe(SAVE_ESI,   -4)
	defframe(SAVE_EDI,   -8)
	defframe(VAR_COUNTER,-12)

	deflit(STACK_SPACE, 12)

Here STACK_SPACE gets used in a "subl $STACK_SPACE, %esp" to allocate the
space, and that instruction must be followed by a redefinition of FRAME
(setting it equal to STACK_SPACE) to reflect the change in %esp.

Definitions for pushed registers are only put in when they're going to be
used.  If registers are just saved and restored with pushes and pops then
definitions aren't made.



ASSEMBLER EXPRESSIONS

Only addition and subtraction seem to be universally available, certainly
that's all the Solaris 8 "as" seems to accept.  If expressions are wanted
then m4 eval() should be used.

In particular note that a "/" anywhere in a line starts a comment in Solaris
"as", and in some configurations of gas too.

	addl	$32/2, %eax           <-- wrong

	addl	$eval(32/2), %eax     <-- right

Binutils gas/config/tc-i386.c has a choice between "/" being a comment
anywhere in a line, or only at the start.  FreeBSD patches 2.9.1 to select
the latter, and from 2.9.5 it's the default for GNU/Linux too.



ASSEMBLER COMMENTS

Solaris "as" doesn't support "#" commenting, using /* */ instead.  For that
reason "C" commenting is used (see asm-defs.m4) and the intermediate ".s"
files have no comments.

Any comments before include(`../config.m4') must use m4 "dnl", since it's
only after the include that "C" is available.  By convention "dnl" is also
used for comments about m4 macros.



TEMPORARY LABELS

Temporary numbered labels like "1:" used as "1f" or "1b" are available in
"gas" and Solaris "as", but not in SCO "as".  Normal L() labels should be
used instead, possibly with a counter to make them unique, see jadcl0() in
x86-defs.m4 for instance.  A separate counter for each macro makes it
possible to nest them, for instance movl_text_address() can be used within
an ASSERT().

"1:" etc must be avoided in gcc __asm__ blocks too.  "%=" for generating a
unique number looks like a good alternative, but is that actually a
documented feature?  In any case this problem doesn't currently arise.



ZERO DISPLACEMENTS

In a couple of places addressing modes like 0(%ebx) with a byte-sized zero
displacement are wanted, rather than (%ebx) with no displacement.  These are
either for computed jumps or to get desirable code alignment.  Explicit
.byte sequences are used to ensure the assembler doesn't turn 0(%ebx) into
(%ebx).  The Zdisp() macro in x86-defs.m4 is used for this.

Current gas 2.9.5 or recent 2.9.1 leave 0(%ebx) as written, but old gas
1.92.3 changes it.  In general changing would be the sort of "optimization"
an assembler might perform, hence explicit ".byte"s are used where
necessary.



SHLD/SHRD INSTRUCTIONS

The %cl count forms of double shift instructions like "shldl %cl,%eax,%ebx"
must be written "shldl %eax,%ebx" for some assemblers.  gas takes either,
Solaris "as" doesn't allow %cl, gcc generates %cl for gas and NeXT (which is
gas), and omits %cl elsewhere.

For GMP an autoconf test GMP_ASM_X86_SHLDL_CL is used to determine whether
%cl should be used, and the macros shldl, shrdl, shldw and shrdw in
mpn/x86/x86-defs.m4 pass through or omit %cl as necessary.  See the comments
with those macros for usage.



IMUL INSTRUCTION

GCC config/i386/i386.md (cvs rev 1.187, 21 Oct 00) under *mulsi3_1 notes
that the following two forms produce identical object code

	imul	$12, %eax
	imul	$12, %eax, %eax

but that the former isn't accepted by some assemblers, in particular the SCO
OSR5 COFF assembler.  GMP follows GCC and uses only the latter form.

(This applies only to immediate operands, the three operand form is only
valid with an immediate.)



DIRECTION FLAG

The x86 calling conventions say that the direction flag should be clear at
function entry and exit.  (See iBCS2 and SVR4 ABI books, references below.)
Although this has been so since the year dot, it's not absolutely clear
whether it's universally respected.  Since it's better to be safe than
sorry, GMP follows glibc and does a "cld" if it depends on the direction
flag being clear.  This happens only in a few places.



POSITION INDEPENDENT CODE

  Coding Style

    Defining the symbol PIC in m4 processing selects SVR4 / ELF style
    position independent code.  This is necessary for shared libraries
    because they can be mapped into different processes at different virtual
    addresses.  Actually, relocations are allowed but text pages with
    relocations aren't shared, defeating the purpose of a shared library.

    The GOT is used to access global data, and the PLT is used for
    functions.  The use of the PLT adds a fixed cost to every function call,
    and the GOT adds a cost to any function accessing global variables.
    These are small but might be noticeable when working with small
    operands.

  Scope

    It's intended, as a matter of policy, that references within libgmp are
    resolved within libgmp.  Certainly there's no need for an application to
    replace any internals, and we take the view that there's no value in an
    application subverting anything documented either.

    Resolving references within libgmp in theory means calls can be made with a
    plain PC-relative call instruction, which is faster and smaller than going
    through the PLT, and data references can be similarly PC-relative, saving a
    GOT entry and fetch from there.  Unfortunately the normal linker behaviour
    doesn't allow us to do this.

    By default an R_386_PC32 PC-relative reference, either for a call or for
    data, is left in libgmp.so by the linker so that it can be resolved at
    runtime to a location in the application or another shared library.  This
    means a text segment relocation which we don't want.

  -Bsymbolic

    Under the "-Bsymbolic" option, the linker resolves references to symbols
    within libgmp.so.  This gives us the desired effect for R_386_PC32,
    ie. it's resolved at link time.  It also resolves R_386_PLT32 calls
    directly to their target without creating a PLT entry (though if this is
    done to normal compiler-generated code it still leaves a setup of %ebx
    to _GLOBAL_OFFSET_TABLE_ which may then be unnecessary).

    Unfortunately -Bsymbolic does bad things to global variables defined in
    a shared library but accessed by non-PIC code from the mainline (or a
    static library).

    The problem is that the mainline needs a fixed data address to avoid
    text segment relocations, so space is allocated in its data segment and
    the value from the variable is copied from the shared library's data
    segment when the library is loaded.  Under -Bsymbolic, however,
    references in the shared library are then resolved still to the shared
    library data area.  Not surprisingly it bombs badly to have mainline
    code and library code accessing different locations for what should be
    one variable.

    Note that this -Bsymbolic effect for the shared library is not just for
    R_386_PC32 offsets which might have been cooked up in assembler, but is
    done also for the contents of GOT entries.  -Bsymbolic simply applies a
    general rule that symbols are resolved first from the local module.

  Visibility Attributes

    GCC __attribute__ ((visibility ("protected"))), which is available in
    recent versions, eg. 3.3, is probably what we'd like to use.  It makes
    gcc generate plain PC-relative calls to indicated functions, and directs
    the linker to resolve references to the given function within the link
    module.

    Unfortunately, as of debian binutils 2.13.90.0.16 at least, the
    resulting libgmp.so comes out with text segment relocations, references
    are not resolved at link time.  If the gcc description is to be believed
    this is this not how it should work.  If a symbol cannot be overridden
    by another module then surely references within that module can be
    resolved immediately (ie. at link time).

  Present

    In any case, all this means that we have no optimizations we can
    usefully make to function or variable usages, neither for assembler nor
    C code.  Perhaps in the future the visibility attribute will work as
    we'd like.




GLOBAL OFFSET TABLE

The magic _GLOBAL_OFFSET_TABLE_ used by code establishing the address of the
GOT sometimes requires an extra underscore prefix.  SVR4 systems and NetBSD
don't need a prefix, OpenBSD does need one.  Note that NetBSD and OpenBSD
are both a.out underscore systems, so the prefix for _GLOBAL_OFFSET_TABLE_
is not simply the same as the prefix for ordinary globals.

In any case in the asm code we write _GLOBAL_OFFSET_TABLE_ and let a macro
in x86-defs.m4 add an extra underscore if required (according to a configure
test).

Old gas 1.92.3 which comes with FreeBSD 2.2.8 gets a segmentation fault when
asked to assemble the following,

        L1:
            addl  $_GLOBAL_OFFSET_TABLE_+[.-L1], %ebx

It seems that using the label in the same instruction it refers to is the
problem, since a nop in between works.  But the simplest workaround is to
follow gcc and omit the +[.-L1] since it does nothing,

            addl  $_GLOBAL_OFFSET_TABLE_, %ebx

Current gas 2.10 generates incorrect object code when %eax is used in such a
construction (with or without +[.-L1]),

            addl  $_GLOBAL_OFFSET_TABLE_, %eax

The R_386_GOTPC gets a displacement of 2 rather than the 1 appropriate for
the 1 byte opcode of "addl $n,%eax".  The best workaround is just to use any
other register, since then it's a two byte opcode+mod/rm.  GCC for example
always uses %ebx (which is needed for calls through the PLT).

A similar problem occurs in an leal (again with or without a +[.-L1]),

            leal  _GLOBAL_OFFSET_TABLE_(%edi), %ebx

This time the R_386_GOTPC gets a displacement of 0 rather than the 2
appropriate for the opcode and mod/rm, making this form unusable.




SIMPLE LOOPS

The overheads in setting up for an unrolled loop can mean that at small
sizes a simple loop is faster.  Making small sizes go fast is important,
even if it adds a cycle or two to bigger sizes.  To this end various
routines choose between a simple loop and an unrolled loop according to
operand size.  The path to the simple loop, or to special case code for
small sizes, is always as fast as possible.

Adding a simple loop requires a conditional jump to choose between the
simple and unrolled code.  The size of a branch misprediction penalty
affects whether a simple loop is worthwhile.

The convention is for an m4 definition UNROLL_THRESHOLD to set the crossover
point, with sizes < UNROLL_THRESHOLD using the simple loop, sizes >=
UNROLL_THRESHOLD using the unrolled loop.  If position independent code adds
a couple of cycles to an unrolled loop setup, the threshold will vary with
PIC or non-PIC.  Something like the following is typical.

	deflit(UNROLL_THRESHOLD, ifdef(`PIC',10,8))

There's no automated way to determine the threshold.  Setting it to a small
value and then to a big value makes it possible to measure the simple and
unrolled loops each over a range of sizes, from which the crossover point
can be determined.  Alternately, just adjust the threshold up or down until
there's no more speedups.



UNROLLED LOOP CODING

The x86 addressing modes allow a byte displacement of -128 to +127, making
it possible to access 256 bytes, which is 64 limbs, without adjusting
pointer registers within the loop.  Dword sized displacements can be used
too, but they increase code size, and unrolling to 64 ought to be enough.

When unrolling to the full 64 limbs/loop, the limb at the top of the loop
will have a displacement of -128, so pointers have to have a corresponding
+128 added before entering the loop.  When unrolling to 32 limbs/loop
displacements 0 to 127 can be used with 0 at the top of the loop and no
adjustment needed to the pointers.

Where 64 limbs/loop is supported, the +128 adjustment is done only when 64
limbs/loop is selected.  Usually the gain in speed using 64 instead of 32 or
16 is small, so support for 64 limbs/loop is generally only for comparison.



COMPUTED JUMPS

When working from least significant limb to most significant limb (most
routines) the computed jump and pointer calculations in preparation for an
unrolled loop are as follows.

	S = operand size in limbs
	N = number of limbs per loop (UNROLL_COUNT)
	L = log2 of unrolling (UNROLL_LOG2)
	M = mask for unrolling (UNROLL_MASK)
	C = code bytes per limb in the loop
	B = bytes per limb (4 for x86)

	computed jump            (-S & M) * C + entrypoint
	subtract from pointers   (-S & M) * B
	initial loop counter     (S-1) >> L
	displacements            0 to B*(N-1)

The loop counter is decremented at the end of each loop, and the looping
stops when the decrement takes the counter to -1.  The displacements are for
the addressing accessing each limb, eg. a load with "movl disp(%ebx), %eax".

Usually the multiply by "C" can be handled without an imul, using instead an
leal, or a shift and subtract.

When working from most significant to least significant limb (eg. mpn_lshift
and mpn_copyd), the calculations change as follows.

	add to pointers          (-S & M) * B
	displacements            0 to -B*(N-1)



OLD GAS 1.92.3

This version comes with FreeBSD 2.2.8 and has a couple of gremlins that
affect GMP code.

Firstly, an expression involving two forward references to labels comes out
as zero.  For example,

		addl	$bar-foo, %eax
	foo:
		nop
	bar:

This should lead to "addl $1, %eax", but it comes out as "addl $0, %eax".
When only one forward reference is involved, it works correctly, as for
example,

	foo:
		addl	$bar-foo, %eax
		nop
	bar:

Secondly, an expression involving two labels can't be used as the
displacement for an leal.  For example,

	foo:
		nop
	bar:
		leal	bar-foo(%eax,%ebx,8), %ecx

A slightly cryptic error is given, "Unimplemented segment type 0 in
parse_operand".  When only one label is used it's ok, and the label can be a
forward reference too, as for example,

		leal	foo(%eax,%ebx,8), %ecx
		nop
	foo:

These problems only affect PIC computed jump calculations.  The workarounds
are just to do an leal without a displacement and then an addl, and to make
sure the code is placed so that there's at most one forward reference in the
addl.



REFERENCES

"Intel Architecture Software Developer's Manual", volumes 1, 2a, 2b, 3a, 3b,
2006, order numbers 253665 through 253669.  Available on-line,

	ftp://download.intel.com/design/Pentium4/manuals/25366518.pdf
	ftp://download.intel.com/design/Pentium4/manuals/25366618.pdf
	ftp://download.intel.com/design/Pentium4/manuals/25366718.pdf
	ftp://download.intel.com/design/Pentium4/manuals/25366818.pdf
	ftp://download.intel.com/design/Pentium4/manuals/25366918.pdf


"System V Application Binary Interface", Unix System Laboratories Inc, 1992,
published by Prentice Hall, ISBN 0-13-880410-9.  And the "Intel386 Processor
Supplement", AT&T, 1991, ISBN 0-13-877689-X.  These have details of calling
conventions and ELF shared library PIC coding.  Versions of both available
on-line,

	http://www.sco.com/developer/devspecs

"Intel386 Family Binary Compatibility Specification 2", Intel Corporation,
published by McGraw-Hill, 1991, ISBN 0-07-031219-2.  (Same as the above 386
ABI supplement.)



----------------
Local variables:
mode: text
fill-column: 76
End: