Annotation of OpenXM_contrib/gmp/mpn/x86/README.family, Revision 1.1
1.1 ! maekawa 1:
! 2: X86 CPU FAMILY MPN SUBROUTINES
! 3:
! 4:
! 5: This file has some notes on things common to all the x86 family code.
! 6:
! 7:
! 8:
! 9: ASM FILES
! 10:
! 11: The x86 .asm files are BSD style x86 assembler code, first put through m4
! 12: for macro processing. The generic mpn/asm-defs.m4 is used, together with
! 13: mpn/x86/x86-defs.m4. Detailed notes are in those files.
! 14:
! 15: The code is meant for use with GNU "gas" or a system "as". There's no
! 16: support for assemblers that demand Intel style, and with gas freely
! 17: available and easy to use that shouldn't be a problem.
! 18:
! 19:
! 20:
! 21: STACK FRAME
! 22:
! 23: m4 macros are used to define the parameters passed on the stack, and these
! 24: act like comments on what the stack frame looks like too. For example,
! 25: mpn_mul_1() has the following.
! 26:
! 27: defframe(PARAM_MULTIPLIER, 16)
! 28: defframe(PARAM_SIZE, 12)
! 29: defframe(PARAM_SRC, 8)
! 30: defframe(PARAM_DST, 4)
! 31:
! 32: Here PARAM_MULTIPLIER gets defined as `FRAME+16(%esp)', and the others
! 33: similarly. The return address is at offset 0, but there's not normally any
! 34: need to access that.
! 35:
! 36: FRAME is redefined as necessary through the code so it's the number of bytes
! 37: pushed on the stack, and hence the offsets in the parameter macros stay
! 38: correct. At the start of a routine FRAME should be zero.
! 39:
! 40: deflit(`FRAME',0)
! 41: ...
! 42: deflit(`FRAME',4)
! 43: ...
! 44: deflit(`FRAME',8)
! 45: ...
! 46:
! 47: Helper macros FRAME_pushl(), FRAME_popl(), FRAME_addl_esp() and
! 48: FRAME_subl_esp() exist to adjust FRAME for the effect of those instructions,
! 49: and can be used instead of explicit definitions if preferred.
! 50: defframe_pushl() is a combination FRAME_pushl() and defframe().
! 51:
! 52: There's generally some slackness in redefining FRAME. If new values aren't
! 53: going to get used, then the redefinitions are omitted to keep from
! 54: cluttering up the code. This happens for instance at the end of a routine,
! 55: where there might be just four register pops and then a ret, so FRAME isn't
! 56: getting used.
! 57:
! 58: Local variables and saved registers can be similarly defined, with negative
! 59: offsets representing stack space below the initial stack pointer. For
! 60: example,
! 61:
! 62: defframe(SAVE_ESI, -4)
! 63: defframe(SAVE_EDI, -8)
! 64: defframe(VAR_COUNTER,-12)
! 65:
! 66: deflit(STACK_SPACE, 12)
! 67:
! 68: Here STACK_SPACE gets used in a "subl $STACK_SPACE, %esp" to allocate the
! 69: space, and that instruction must be followed by a redefinition of FRAME
! 70: (setting it equal to STACK_SPACE) to reflect the change in %esp.
! 71:
! 72: Definitions for pushed registers are only put in when they're going to be
! 73: used. If registers are just saved and restored with pushes and pops then
! 74: definitions aren't made.
! 75:
! 76:
! 77:
! 78: ASSEMBLER EXPRESSIONS
! 79:
! 80: Only addition and subtraction seem to be universally available, certainly
! 81: that's all the Solaris 8 "as" seems to accept. If expressions are wanted
! 82: then m4 eval() should be used.
! 83:
! 84: In particular note that a "/" anywhere in a line starts a comment in Solaris
! 85: "as", and in some configurations of gas too.
! 86:
! 87: addl $32/2, %eax <-- wrong
! 88:
! 89: addl $eval(32/2), %eax <-- right
! 90:
! 91: Binutils gas/config/tc-i386.c has a choice between "/" being a comment
! 92: anywhere in a line, or only at the start. FreeBSD patches 2.9.1 to select
! 93: the latter, and as of 2.9.5 it's the default for GNU/Linux too.
! 94:
! 95:
! 96:
! 97: ASSEMBLER COMMENTS
! 98:
! 99: Solaris "as" doesn't support "#" commenting, using /* */ instead,
! 100: unfortunately. For that reason "C" commenting is used (see asm-defs.m4) and
! 101: the intermediate ".s" files have no comments.
! 102:
! 103:
! 104:
! 105: ZERO DISPLACEMENTS
! 106:
! 107: In a couple of places addressing modes like 0(%ebx) with a byte-sized zero
! 108: displacement are wanted, rather than (%ebx) with no displacement. These are
! 109: either for computed jumps or to get desirable code alignment. Explicit
! 110: .byte sequences are used to ensure the assembler doesn't turn 0(%ebx) into
! 111: (%ebx). The Zdisp() macro in x86-defs.m4 is used for this.
! 112:
! 113: Current gas 2.9.5 or recent 2.9.1 leave 0(%ebx) as written, but old gas
! 114: 1.92.3 changes it. In general changing would be the sort of "optimization"
! 115: an assembler might perform, hence explicit ".byte"s are used where
! 116: necessary.
! 117:
! 118:
! 119:
! 120: SHLD/SHRD INSTRUCTIONS
! 121:
! 122: The %cl count forms of double shift instructions like "shldl %cl,%eax,%ebx"
! 123: must be written "shldl %eax,%ebx" for some assemblers. gas takes either,
! 124: Solaris "as" doesn't allow %cl, gcc generates %cl for gas and NeXT (which is
! 125: gas), and omits %cl elsewhere.
! 126:
! 127: For GMP an autoconf test is used to determine whether %cl should be used and
! 128: the macros shldl, shrdl, shldw and shrdw in mpn/x86/x86-defs.m4 then pass
! 129: through or omit %cl as necessary. See comments with those macros for usage.
! 130:
! 131:
! 132:
! 133: DIRECTION FLAG
! 134:
! 135: The x86 calling conventions say that the direction flag should be clear at
! 136: function entry and exit. (See iBCS2 and SVR4 ABI books, references below.)
! 137:
! 138: Although this has been so since the year dot, it's not absolutely clear
! 139: whether it's universally respected. Since it's better to be safe than
! 140: sorry, gmp follows glibc and does a "cld" if it depends on the direction
! 141: flag being clear. This happens only in a few places.
! 142:
! 143:
! 144:
! 145: POSITION INDEPENDENT CODE
! 146:
! 147: Defining the symbol PIC in m4 processing selects position independent code.
! 148: This mainly affects computed jumps, and these are implemented in a
! 149: self-contained fashion (without using the global offset table). The few
! 150: calls from assembly code to global functions use the normal procedure
! 151: linkage table.
! 152:
! 153: PIC is necessary for ELF shared libraries because they can be mapped into
! 154: different processes at different virtual addresses. Text relocations in
! 155: shared libraries are allowed, but that presumably means a page with such a
! 156: relocation isn't shared. The use of the PLT for PIC adds a fixed cost to
! 157: every function call, which is small but might be noticeable when working with
! 158: small operands.
! 159:
! 160: Calls from one library function to another don't need to go through the PLT,
! 161: since of course the call instruction uses a displacement, not an absolute
! 162: address, and the relative locations of object files are known when libgmp.so
! 163: is created. "ld -Bsymbolic" (or "gcc -Wl,-Bsymbolic") will resolve calls
! 164: this way, so that there's no jump through the PLT, but of course leaving
! 165: setups of the GOT address in %ebx that may be unnecessary.
! 166:
! 167: The %ebx setup could be avoided in assembly if a separate option controlled
! 168: PIC for calls as opposed to computed jumps etc. But there's only ever
! 169: likely to be a handful of calls out of assembler, and getting the same
! 170: optimization for C intra-library calls would be more important. There seems
! 171: no easy way to tell gcc that certain functions can be called non-PIC, and
! 172: unfortunately many gmp functions use the global memory allocation variables,
! 173: so they need the GOT anyway. Object files with no global data references
! 174: and only intra-library calls could go into the library as non-PIC under
! 175: -Bsymbolic. Integrating this into libtool and automake is left as an
! 176: exercise for the reader.
! 177:
! 178:
! 179:
! 180: SIMPLE LOOPS
! 181:
! 182: The overheads in setting up for an unrolled loop can mean that at small
! 183: sizes a simple loop is faster. Making small sizes go fast is important,
! 184: even if it adds a cycle or two to bigger sizes. To this end various
! 185: routines choose between a simple loop and an unrolled loop according to
! 186: operand size. The path to the simple loop, or to special case code for
! 187: small sizes, is always as fast as possible.
! 188:
! 189: Adding a simple loop requires a conditional jump to choose between the
! 190: simple and unrolled code. The size of a branch misprediction penalty
! 191: affects whether a simple loop is worthwhile.
! 192:
! 193: The convention is for an m4 definition UNROLL_THRESHOLD to set the crossover
! 194: point, with sizes < UNROLL_THRESHOLD using the simple loop, sizes >=
! 195: UNROLL_THRESHOLD using the unrolled loop. If position independent code adds
! 196: a couple of cycles to an unrolled loop setup, the threshold will vary with
! 197: PIC or non-PIC. Something like the following is typical.
! 198:
! 199: ifdef(`PIC',`
! 200: deflit(UNROLL_THRESHOLD, 10)
! 201: ',`
! 202: deflit(UNROLL_THRESHOLD, 8)
! 203: ')
! 204:
! 205: There's no automated way to determine the threshold. Setting it to a small
! 206: value and then to a big value makes it possible to measure the simple and
! 207: unrolled loops each over a range of sizes, from which the crossover point
! 208: can be determined. Alternately, just adjust the threshold up or down until
! 209: there's no more speedups.
! 210:
! 211:
! 212:
! 213: UNROLLED LOOP CODING
! 214:
! 215: The x86 addressing modes allow a byte displacement of -128 to +127, making
! 216: it possible to access 256 bytes, which is 64 limbs, without adjusting
! 217: pointer registers within the loop. Dword sized displacements can be used
! 218: too, but they increase code size, and unrolling to 64 ought to be enough.
! 219:
! 220: When unrolling to the full 64 limbs/loop, the limb at the top of the loop
! 221: will have a displacement of -128, so pointers have to have a corresponding
! 222: +128 added before entering the loop. When unrolling to 32 limbs/loop
! 223: displacements 0 to 127 can be used with 0 at the top of the loop and no
! 224: adjustment needed to the pointers.
! 225:
! 226: Where 64 limbs/loop is supported, the +128 adjustment is done only when 64
! 227: limbs/loop is selected. Usually the gain in speed using 64 instead of 32 or
! 228: 16 is small, so support for 64 limbs/loop is generally only for comparison.
! 229:
! 230:
! 231:
! 232: COMPUTED JUMPS
! 233:
! 234: When working from least significant limb to most significant limb (most
! 235: routines) the computed jump and pointer calculations in preparation for an
! 236: unrolled loop are as follows.
! 237:
! 238: S = operand size in limbs
! 239: N = number of limbs per loop (UNROLL_COUNT)
! 240: L = log2 of unrolling (UNROLL_LOG2)
! 241: M = mask for unrolling (UNROLL_MASK)
! 242: C = code bytes per limb in the loop
! 243: B = bytes per limb (4 for x86)
! 244:
! 245: computed jump (-S & M) * C + entrypoint
! 246: subtract from pointers (-S & M) * B
! 247: initial loop counter (S-1) >> L
! 248: displacements 0 to B*(N-1)
! 249:
! 250: The loop counter is decremented at the end of each loop, and the looping
! 251: stops when the decrement takes the counter to -1. The displacements are for
! 252: the addressing accessing each limb, eg. a load with "movl disp(%ebx), %eax".
! 253:
! 254: Usually the multiply by "C" can be handled without an imul, using instead an
! 255: leal, or a shift and subtract.
! 256:
! 257: When working from most significant to least significant limb (eg. mpn_lshift
! 258: and mpn_copyd), the calculations change as follows.
! 259:
! 260: add to pointers (-S & M) * B
! 261: displacements 0 to -B*(N-1)
! 262:
! 263:
! 264:
! 265: OLD GAS 1.92.3
! 266:
! 267: This version comes with FreeBSD 2.2.8 and has a couple of gremlins that
! 268: affect gmp code.
! 269:
! 270: Firstly, an expression involving two forward references to labels comes out
! 271: as zero. For example,
! 272:
! 273: addl $bar-foo, %eax
! 274: foo:
! 275: nop
! 276: bar:
! 277:
! 278: This should lead to "addl $1, %eax", but it comes out as "addl $0, %eax".
! 279: When only one forward reference is involved, it works correctly, as for
! 280: example,
! 281:
! 282: foo:
! 283: addl $bar-foo, %eax
! 284: nop
! 285: bar:
! 286:
! 287: Secondly, an expression involving two labels can't be used as the
! 288: displacement for an leal. For example,
! 289:
! 290: foo:
! 291: nop
! 292: bar:
! 293: leal bar-foo(%eax,%ebx,8), %ecx
! 294:
! 295: A slightly cryptic error is given, "Unimplemented segment type 0 in
! 296: parse_operand". When only one label is used it's ok, and the label can be a
! 297: forward reference too, as for example,
! 298:
! 299: leal foo(%eax,%ebx,8), %ecx
! 300: nop
! 301: foo:
! 302:
! 303: These problems only affect PIC computed jump calculations. The workarounds
! 304: are just to do an leal without a displacement and then an addl, and to make
! 305: sure the code is placed so that there's at most one forward reference in the
! 306: addl.
! 307:
! 308:
! 309:
! 310: REFERENCES
! 311:
! 312: "Intel Architecture Software Developer's Manual", volumes 1 to 3, 1999,
! 313: order numbers 243190, 243191 and 243192. Available on-line,
! 314:
! 315: ftp://download.intel.com/design/PentiumII/manuals/243190.htm
! 316: ftp://download.intel.com/design/PentiumII/manuals/243191.htm
! 317: ftp://download.intel.com/design/PentiumII/manuals/243192.htm
! 318:
! 319: "Intel386 Family Binary Compatibility Specification 2", Intel Corporation,
! 320: published by McGraw-Hill, 1991, ISBN 0-07-031219-2.
! 321:
! 322: "System V Application Binary Interface", Unix System Laboratories Inc, 1992,
! 323: published by Prentice Hall, ISBN 0-13-880410-9. And the "Intel386 Processor
! 324: Supplement", AT&T, 1991, ISBN 0-13-877689-X. (These have details of ELF
! 325: shared library PIC coding.)
! 326:
! 327:
! 328:
! 329: ----------------
! 330: Local variables:
! 331: mode: text
! 332: fill-column: 76
! 333: End:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to README.family CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / mpn / x86