Branch Optimizations | AMD x86 specs

22007E/0 — November 1999

AMD Athlon™ Processor x86 Code Optimization

6

Branch Optimizations

Wh i l e t h e A M D A t h l o n ™ p ro c e s s o r c o n t a i n s a ve ry sophisticated branch unit, certain optimizations increase the effectiveness of the branch prediction unit. This chapter discusses rules that improve branch prediction and minimize branch penalties. Guidelines are listed in order of importance.

Avoid Branches Dependent on Random Data

✩are difficult to predict. For example, a piece of code receives a

TOPrandom stream of characters “A” through “Z” and branches ifAvoid conditional branches depending on random data, as thesethe character is before “M” in the collating sequence.Data-dependent branches acting upon basically random data

causes the branch prediction logic to mispredict the branch about 50% of the time.

If possible, design branch-free alternative code sequences, which results in shorter average execution time. This technique is especially important if the branch body is small. Examples 1 and 2 illustrate this concept using the CMOV instruction. Note that the AMD-K6®processor does not support the CMOV instruction. Therefore, blended AMD-K6 and AMD Athlon processor code should use examples 3 and 4.

Avoid Branches Dependent on Random Data

57

Image 73

AMD x86 manual Branch Optimizations, Avoid Branches Dependent on Random Data

Contents

AMD AthlonTM Processor Trademarks Contents Instruction Decoding Optimizations Cache and Memory Optimizations Scheduling Optimizations Floating-Point Optimizations General x86 Optimization Guidelines 127 Appendix B Pipeline and Execution Unit Resources Overview Appendix E Programming the Mtrr and PAT List of Figures Xii List of Tables Xiv Revision History Xvi About this Document Introduction Source Level Optimizations. Describes optimizations that AMD Athlon Processor Family AMD Athlon Processor Microarchitecture Summary AMD Athlon Processor Microarchitecture Summary AMD Athlon Processor x86 Code Optimization Top Optimizations Optimization Star Memory Size and Alignment IssuesGroup I Optimizations Essential Optimizations Use the 3DNow! Prefetch and Prefetchw Instructions Select DirectPath Over VectorPath Instructions Group II Optimizations-Secondary OptimizationsLoad-Execute Instruction Usage Use Load-Execute Instructions Use 3DNow! Instructions Take Advantage of Write CombiningAvoid Branches Dependent on Random Data Avoid Placing Code and Data in the Same 64-Byte Cache Line 22007E/0 November Use 32-Bit Data Types for Integer Code Source Level Optimizations Example 1 Avoid Consider the Sign of Integer OperandsExample Preferred Example Avoid Use Array Style Instead of Pointer Style CodeUse unsigned types for Use signed types for Vertex Example 2 Preferred Avoid Unnecessary Store-to-Load Dependencies Completely Unroll Small Loops Avoid Unnecessary Store-to-Load Dependencies Consider Expression Order in Compound Branch Conditions Optimize Switch Statements Switch Statement UsageUse Prototypes for All Functions Generic Loop Hoisting Use Const Type QualifierExample Generalization for Multiple Constant Control Code Declare Local Functions as Static Introduce Explicit Parallelism into Code Dynamic Memory Allocation Consideration Explicitly Extract Common Subexpressions Example Language Structure Component ConsiderationsAvoid Preferred Original ordering Avoid Sort Local Variables According to Base Type SizeNew ordering, with padding Preferred Improved ordering Preferred Accelerating Floating-Point Divides and Square Roots Accelerating Floating-Point Divides and Square Roots Avoid Unnecessary Integer Division AMD Athlon Processor x86 Code Optimization Overview Instruction Decoding Optimizations Load-Execute Instruction Usage Select DirectPath Over VectorPath InstructionsUse Load-Execute Integer Instructions TOP Use Short Instruction Lengths Align Branch Targets in Program Hot Spots Example 2 Avoid Avoid Partial Register Reads and Writes Replace Certain Shld Instructions with Alternative Code Use 8-Bit Sign-Extended Immediates Code Padding Using Neutral Code Fillers Use 8-Bit Sign-Extended Displacements Recommendations for the AMD Athlon Processor Code Padding Using Neutral Code Fillers AMD Athlon Processor x86 Code Optimization NOP6EDI AMD Athlon Processor x86 Code Optimization Cache and Memory Optimizations Memory Size and Alignment IssuesAvoid Memory Size Mismatches Use the 3DNow! Prefetch and Prefetchw Instructions Align Data Where Possible Code Example Multiple Prefetches MOV ECX, -LARGENUM Prefetch Distance = 200 DS/C bytes Determining Prefetch Distance Avoid Placing Code and Data in the Same 64-Byte Cache Line Take Advantage of Write Combining Store-to-Load Forwarding Pitfalls -True Dependencies Store-to-Load Forwarding Restrictions Example 4 Avoid Example 3 Avoid Example 6 Avoid Example 5 PreferredExample 7 Avoid Summary of Store-to-Load Forwarding Pitfalls to Avoid Stack Alignment Considerations Align Tbyte Variables on Quadword Aligned Addresses Sort Variables According to Base Type Size Avoid Branches Dependent on Random Data Branch Optimizations Blended AMD-K6and AMD Athlon Processor Code AMD Athlon Processor Specific Code Example 6 Increment Ring Buffer Offset Always Pair Call and ReturnExample 7 Integer Signum Function Muxing Constructs Replace Branches with Computation in 3DNow! Code Code Sample Code Translated into 3DNow! Code3DNow! code MM5 Pfsub Psrad Avoid Far Control Transfer Instructions Avoid the Loop Instruction Avoid Recursive Functions Schedule Instructions According to their Latency Scheduling OptimizationsUnrolling Loops Complete Loop Unrolling Partial Loop Unrolling With Partial Loop Unrolling Without Loop Unrolling Control For Partially Deriving LoopUnrolled Loops Example 1 rolled loop Overview Use Function Inlining Always Inline Functions if Called from One Site Avoid Address Generation Interlocks Minimize Pointer Arithmetic in Loops Use Movzx and Movsx MOV ECX, Maxsize Example 3 Preferred Push Memory Data Carefully Push Memory Data Carefully Replace Divides with Multiplies Integer OptimizationsMultiplication by Reciprocal Division Utility Unsigned Division by Multiplication of Constant Simpler Code for Signed Division by Multiplication of ConstantRestricted Dividend Signed Division By 2n Signed Division ByRemainder of Signed Integer 2 or Integer 2n or -2n Use Alternative Code When Multiplying by a Constant ADD REG1, REG1 REG1, REG2 SHL Use MMX Instructions for Integer-Only Work Latency of Repeated String Instructions Repeated String Instruction UsageGuidelines for Repeated String Instructions Ensure DF=0 UP Using MovqAlign Source Destination with Efficient 64-Bit Integer Arithmetic Use XOR Instruction to Clear Integer Registers Example 5 Right shift Example 4 Left shiftExample 6 Multiplication EBX, ESP+12 Dividendlo Example 7 Division Example 8 Remainder SHR EDX Step Efficient Implementation of Population Count Function Bit field. Thus the following computation is performed MOV EDX, EDX SHR Derivation of Multiplier Used for Integer Division by Utility sdiv.exe was compiled using the following code MOV ECX EDX Imul ADD SHR SAR Ensure All FPU Data is Aligned Floating-Point OptimizationsUse Multiplies Rather than Divides Use Ffreep Macro to Pop One Register from the FPU Stack Floating-Point Compare Instructions Use the Fxch Instruction Rather than FST/FLD Pairs Avoid Using Extended-Precision Data Example 1 Fast Minimize Floating-Point-to-Integer Conversions Example 2 Potentially faster Example 4 Fastest Example 3 Potentially faster Floating-Point Subexpression Elimination 104 Take Advantage of the Fsincos Instruction 106 Use 3DNow! Instructions 3DNow! and MMX OptimizationsUse Femms Instruction Optimized 14-Bit Precision Divide Use 3DNow! Instructions for Fast DivisionOptimized Full 24-Bit Precision Divide Newton-Raphson Reciprocal Pipelined Pair of 24-Bit Precision Divides Optimized 24-Bit Precision Square Root Optimized 15-Bit Precision Square Root Newton-Raphson Reciprocal Square Root AMD Athlon 3DNow! and MMX Intra-Operand SwappingSpecific Code Blended Code Use MMX Pxor to Negate 3DNow! Data Fast Conversion of Signed Words to Floating-Point Both Numbers Use MMX Pcmp Instead of 3DNow! PfcmpPositive One Negative, One Positive AMD-K6and AMD Athlon Processor Blended Code Use MMX Instructions for Block Copies and Block Fills 116 Processor Specific Use MMX Pxor to Clear All Bits in an MMX Register Use MMX Pcmpeqd to Set All Bits in an MMX Register Optimized Matrix Multiplication MOV EBX, RES Optimized Matrix Multiplication 121 Data Use 3DNow! Pavgusb for MPEG-2 Motion Compensation MM0=QWORD1 Stream of Packed Unsigned Bytes Complex Number Arithmetic Short Forms General x86 Optimization Guidelines Register Operands DependenciesStack Allocation Introduction AMD Athlon Processor Microarchitecture Superscalar Processor AMD Athlon Processor Microarchitecture AMD Athlon Processor Microarchitecture 131 Branch Prediction Predecode Early Decoding Data Cache Instruction Control Unit Integer Execution Unit Integer Scheduler Floating-Point Scheduler 12 to Floating-Point Execution Unit Load/Store Unit Load-Store Unit LSU Write Combining L2 Cache ControllerAMD Athlon System Bus 140 AMD Athlon Processor Microarchitecture Fetch and Decode Pipeline Stages Pipeline and Execution Unit Resources Overview C T L R O M Cycle 2-SCAN Cycle 1-FETCHCycle 3 DirectPath Cycle 3 VectorPath Integer Pipeline Stages Integer Pipeline Stages Cycle 8-EXEC Cycle 7-SCHEDCycle 9-ADDGEN Cycle 10 -DCACC Floating-Point Pipeline Stages Floating-Point Pipeline Stages Cycle 8-REGREN Cycle 7-STKRENCycle 9-SCHEDW Cycle 10 -SCHED Terminology Execution Unit ResourcesOperands Results Integer Pipeline Operation Types Integer Pipeline OperationsInteger Decode Types Floating-Point Pipeline Operation Types Floating-Point Pipeline OperationsFloating-Point Decode Types Load/Store Unit Stages Load/Store Pipeline OperationsStage 1 Cycle Stage 2 Cycle Stage 3 Cycle Code Sample Analysis ADD EDI, EBX SHL Imul EAX, ECX INC ESI MOVINC EBX ADD ESI, EDX DEC EDX MOV EDI, ECX SUB Sample 2 Integer Register and Memory Load OperationsSAR Implementation Write Combining Appendix C Write-Combining Definitions and Abbreviations What is Write Combining?Programming Details Write-Combining Operations INIT, Halt Write Combining Completion Events Sending Write-Buffer Data to the System AMD Athlon System Bus Commands Generation Rules 160 Write-Combining Operations Performance Counter Usage Performance-Monitoring Counters PerfEvtSel30 Registers PerfEvtSel30 MSRs MSR Addresses C0010000h-C0010003h Performance Counter Usage 163 Performance-Monitoring Counters 73h 65hSnoop hits 74h Waited to use the L2 Event Source Event DescriptionInstruction cache fetches Instruction cache misses PerfCtr30 MSRs MSR Addresses C0010004h-C0010007h Starting and Stopping the Performance-Monitoring Counters Event and Time-Stamp Monitoring Software Monitoring Counter Overflow 170 Monitoring Counter Overflow Memory Type Range Register Mtrr Mechanism Programming the Mtrr 172 Memory Type Range Register Mtrr Mechanism FFFFFFFFh Fixed Ranges100000h Kbytes each Fixed Ranges C0000h 80000h Memory Type Encodings Memory TypesMtrr Capability Register Format Memory Type Range Register Mtrr Mechanism 175 Standard Mtrr Types and Properties Attribute Table MSR 277h Attribute Table PAT PATi 3-Bit Encodings PAT Entry Reset ValueMTRRs and PAT PATi PAT Memory Type Mtrr Memory Type Effective Memory Type Based on PAT and MTRRs Input Memory Type Final Output Memory Types Attribute Table PAT 181 9FFFF 9BFFF 97FFF 93FFF 8FFFF 8BFFF 87FFF 83FFF 7FFFF 6FFFF 5FFFF 4FFFF 3FFFF 2FFFF 1FFFF 0FFFFBffff Bbfff B7FFF B3FFF Affff Abfff A7FFF A3FFF C7FFF C6FFF C5FFF C4FFF C3FFF C2FFF C1FFF C0FFF Attribute Table PAT 183 MTRRphysMaskn Register Format MTRR-Related Model-Specific Register MSR Map 186 Instruction Dispatch Execution Resources Appendix F AAA Integer InstructionsAAD AAM ADC mreg8, reg8 ModR/M Decode ByteADC mem8, reg8 ADC mreg16/32, reg16/32 Bswap EAX BoundBswap ECX Bswap EDX CLC CBW/CWDECLD CLI CMOVE/CMOVZ reg16/32, mem16/32 0Fh CMOVE/CMOVZ reg16/32, reg16/32 0FhCMOVG/CMOVNLE reg16/32, reg16/32 0Fh CMOVG/CMOVNLE reg16/32, mem16/32 0Fh CWD/CDQ CpuidDAA DAS AL, DX EnterAX, DX EAX, DX Invlpg Invd Leave Lahf LOOPNE/LOOPNZ disp8 E0h LOOPE/LOOPZ disp8 E1hLSL reg16/32, mreg16/32 0Fh 03h LSL reg16/32, mem16/32 0Fh 03h NOP Xchg EAX, EAX OUT DX, AX OUT DX, ALOUT DX, EAX POP ES POP ESP POP EBXPOP EBP POP ESI Rdpmc RdmsrRdtsc Sahf SBB mem16/32, reg16/32 SBB mreg16/32, reg16/32SBB reg8, mreg8 SBB reg8, mem8 Sets mem8 Sets mreg8Setns mreg8 Setns mem8 STD STCSTI Sysenter SyscallSysexit Sysret Xchg EAX, ECX Xchg EAX, EAXXchg EAX, EDX Xchg EAX, EBX Emms MMX Instructions DFh Pandn mmreg1, mmreg2Pandn mmreg, mem64 Pcmpeqb mmreg1, mmreg2 FADD/FMUL FPU MMX Extensions Floating-Point Instructions Fcos FcomppFdecstp Finit FincstpFLD1 FLDL2T FLDL2EFLDLG2 FLDLN2 Ftst Fstsw AXFucom Fucomp Femms DNow! Instructions DNow! Extensions DirectPath Instructions DirectPath versus VectorPath Instructions BT mreg16/32, reg16/32 BT mreg16/32, imm8 BT mem16/32, imm8 DirectPath Integer InstructionsCBW/CWDE CLC CMC INC mreg8 INC mem8 INC mreg16/32 INC mem16/32 JO short disp8 DEC mreg8 DEC mem8 DEC mreg16/32 DEC mem16/32 222 DirectPath Instructions DirectPath Instructions 223 224 DirectPath Instructions Wait Xchg EAX, EAX 226 DirectPath Instructions DirectPath MMX Instructions DirectPath MMX Extensions Fcompp Fdecstp DirectPath Floating-Point InstructionsFist mem16int FLD1 FLDL2E FLDL2T FLDLG2 FLDLN2 Fldpi Fldz Ftst Fucom Fucomp Fucompp Fwait Fxch VectorPath Integer Instructions VectorPath InstructionsAAA AAD AAM AAS CLD CLI Clts AL, DX AX, DX EAX, DX Invd Invlpg Instruction Mnemonic DIV EAX, mem16/32 Push mreg16/32 Push mem16/32 POP mreg 16/32 POP mem 16/32PUSHA/PUSHAD PUSHF/PUSHFD Rdmsr Rdpmc Rdtsc VectorPath MMX Extensions VectorPath MMX InstructionsSyscall Sysenter Sysexit Sysret Wbinvd Wrmsr Fptan Fpatan Frndint VectorPath Floating-Point InstructionsFscale Fsin Fsincos Fxam Fxtract FYL2X FYL2XP1 236 Index 238 Index Index 239 240 Index