ArchLab是CSAPP的第四个实验，主要考察对于架构的理解，根据虚拟的Y86-64指令架构，从而理解CPU与指令。
ArchLab同时涉及第4章架构和第5章优化，决定分两次完成，本博客也决定分两次完成。
从进度上来说：第4章相关的A/B部分只要一个晚上就可以完成了，没有遇到太多困难。

Lab

A Part

A Part感觉上是主要考察对于Y86-64的“汇编”编写能力，同时还回顾了“过程”这一机制，对于递归能有更深的理解。

sum.ys

sum.ys迭代地对链表的元素求和，与下述的examples.c里的sum_list理应一致。

typedef struct ELE {long val;struct ELE *next;
} *list_ptr;long sum_list(list_ptr ls)
{long val = 0;while (ls) {val += ls->val;ls = ls->next;}return val;
}

根据终止条件进行变成，注意CC的设置。同时还回顾了一下while的先jmp的视线，具体结果如下，也有较详细的注释：

# Execution begins at address 0 .pos 0irmovq stack, %rsp  	# Set up stack pointercall main		# Execute main programhalt			# Terminate program # Sample linked list
.align 8
ele1:.quad 0x00a.quad ele2
ele2:.quad 0x0b0.quad ele3
ele3:.quad 0xc00.quad 0main:   irmovq ele1,%rdicall sum_list        #sum(ele1)ret# long sum_list(list_ptr ls)
# ls in %rdisum_list:   xorq %rax,%rax  # val = 0andq    %rdi,%rdi       # Set CCjmp     test            # Goto test
loop:   mrmovq  (%rdi),%r10 # Get valaddq    %r10,%rax       # Add to summrmovq  0x8(%rdi),%rdi  # ptr = ptr->nextandq    %rdi,%rdi       # Set CC
test:       jne loop        # Stop when 0ret# Stacks.pos 0x200
stack:

运行：

usr@ub2004:~/csapplab/archlab/archlab-handout/sim/misc$ ./yis sum.yo

结果：

Stopped in 26 steps at PC = 0x13.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000cba
%rsp:   0x0000000000000000      0x0000000000000200
%r10:   0x0000000000000000      0x0000000000000c00Changes to memory:
0x01f0: 0x0000000000000000      0x000000000000005b
0x01f8: 0x0000000000000000      0x0000000000000013

其中%rax结果为cba，满足条件。

rsum.ys

rsum.ys递归地对链表的元素求和，与下述的examples.c里的rsum_list理应一致。

long rsum_list(list_ptr ls)
{if (!ls)return 0;else {long val = ls->val;long rest = rsum_list(ls->next);return val + rest;}
}

这里考察了“过程”这一机制，利用栈保存原有的结果，并在返回时利用：

# Execution begins at address 0 .pos 0irmovq stack, %rsp  	# Set up stack pointercall main		# Execute main programhalt			# Terminate program # Sample linked list
.align 8
ele1:.quad 0x00a.quad ele2
ele2:.quad 0x0b0.quad ele3
ele3:.quad 0xc00.quad 0main:   irmovq ele1,%rdicall rsum_list        #sum(ele1)ret# long rsum_list(list_ptr ls)
# ls in %rdirsum_list:  pushq %rbx  # save ls->valmrmovq  (%rdi),%rbx # val = ls->valirmovq  0,%rax      # sum = 0andq    %rdi,%rdi   # Set CCje      resultmrmovq  0x8(%rdi),%rdi  # ls = ls->nextcall    rsum_listaddq    %rbx,%rax   # %rax = val + rest
result:popq    %rbxret# Stacks.pos 0x200
stack:

运行：

usr@ub2004:~/csapplab/archlab/archlab-handout/sim/misc$ ./yis rsum.yo

结果：

Stopped in 43 steps at PC = 0x13.  Status 'HLT', CC Z=0 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000cba
%rsp:   0x0000000000000000      0x0000000000000200Changes to memory:
0x01b8: 0x0000000000000000      0x0000000000000c00
0x01c0: 0x0000000000000000      0x0000000000000090
0x01c8: 0x0000000000000000      0x00000000000000b0
0x01d0: 0x0000000000000000      0x0000000000000090
0x01d8: 0x0000000000000000      0x000000000000000a
0x01e0: 0x0000000000000000      0x0000000000000090
0x01f0: 0x0000000000000000      0x000000000000005b
0x01f8: 0x0000000000000000      0x0000000000000013

其中%rax结果为cba，满足条件。

copy.ys

copy.ys对数组进行复制，与下述的examples.c里的copy_block理应一致。

/* copy_block - 将src拷贝到dest并返回xor校验和 */
long copy_block(long *src, long *dest, long len)
{long result = 0;while (len > 0) {long val = *src++;*dest++ = val;result ^= val;len--;}return result;
}

这里发现没有IADDQ，却是用起来有点麻烦，只能用寄存器保存const + OPQ来进行：

# Execution begins at address 0 .pos 0irmovq stack, %rsp  	# Set up stack pointercall main		# Execute main programhalt			# Terminate program # Source block
.align 8
src:.quad   0x00a.quad   0x0b0.quad   0xc00
# Destination block
dest:.quad   0x111.quad   0x222.quad   0x333main:   irmovq  src,%rdiirmovq  dest,%rsiirmovq  $3,%rdxcall copy_blockret# long copy_block(long *src, long *dest, long len)
# src in %rdi, dest in %rsi, len in %rdxcopy_block: xorq %rax,%rax      # result=0irmovq $8,%r8       # const 8irmovq $1,%r9        # const 1andq %rdx,%rdx      # Set CCjmp  test
loop:       mrmovq (%rdi),%r10  # val=*srcaddq %r8,%rdi       # src++rmmovq %r10,(%rsi)  # *dest=valaddq %r8,%rsi       # dest++xorq %r10,%rax      # result^=valsubq %r9,%rdx       # len-- & Set CC
test:       jne loop            # Stop when 0# Stacks.pos 0x200
stack:

运行：

usr@ub2004:~/csapplab/archlab/archlab-handout/sim/misc$ ./yis copy.yo

结果：

Stopped in 34 steps at PC = 0xb6.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000cba
%rsp:   0x0000000000000000      0x00000000000001f0
%rsi:   0x0000000000000000      0x0000000000000048
%rdi:   0x0000000000000000      0x0000000000000030
%r8:    0x0000000000000000      0x0000000000000008
%r9:    0x0000000000000000      0x0000000000000001
%r10:   0x0000000000000000      0x0000000000000c00Changes to memory:
0x0030: 0x0000000000000111      0x000000000000000a
0x0038: 0x0000000000000222      0x00000000000000b0
0x0040: 0x0000000000000333      0x0000000000000c00
0x01f0: 0x0000000000000000      0x000000000000006f
0x01f8: 0x0000000000000000      0x0000000000000013

其中%rax结果为cba，且内存0x0030-0x0040都成功复制为对应的元素。

B Part

CSAPP的IADDQ对应格式如下：

            0    1     2                     10
iaddq V,rB  [C 0][F rB][          V          ]

这样我们就很清楚，我们需要在哪些阶段上添加HCL代码。最终所需修改的地方共有取指、译码、执行三个阶段，具体如下：

• 取指阶段

bool instr_valid = icode in { INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ, IIADDQ };		# note: add IIADDQ# Does fetched instruction require a regid byte?
bool need_regids =icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };					# note: add IIADDQ# Does fetched instruction require a constant word?
bool need_valC =icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };	# note: add IIADDQ

• 译码阶段

## What register should be used as the B source?
word srcB = [icode in { IOPQ, IRMMOVQ, IMRMOVQ, IIADDQ  } : rB;		# note: add IIADDQicode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;1 : RNONE;  # Don't need register
];## What register should be used as the E destination?
word dstE = [icode in { IRRMOVQ } && Cnd : rB;icode in { IIRMOVQ, IOPQ, IIADDQ} : rB;					# note: add IIADDQicode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;1 : RNONE;  # Don't write any register
];

• 执行阶段

## Select input A to ALU
word aluA = [icode in { IRRMOVQ, IOPQ } : valA;icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ } : valC;			# note: add IIADDQicode in { ICALL, IPUSHQ } : -8;icode in { IRET, IPOPQ } : 8;# Other instructions don't need ALU
];## Select input B to ALU
word aluB = [icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL, IPUSHQ, IRET, IPOPQ, IIADDQ } : valB;					# note: add IIADDQicode in { IRRMOVQ, IIRMOVQ } : 0;# Other instructions don't need ALU
];## Should the condition codes be updated?
bool set_cc = icode in { IOPQ, IIADDQ };							# note: add IIADDQ

回归测试运行：

1、测试除了iaddq和leave之外所有内容：

usr@ub2004:~/csapplab/archlab/archlab-handout/sim/seq$ (cd ../ptest; make SIM=../seq/ssim)

./optest.pl -s ../seq/ssim 
Simulating with ../seq/ssimAll 49 ISA Checks Succeed
./jtest.pl -s ../seq/ssim 
Simulating with ../seq/ssimAll 64 ISA Checks Succeed
./ctest.pl -s ../seq/ssim 
Simulating with ../seq/ssimAll 22 ISA Checks Succeed
./htest.pl -s ../seq/ssim 
Simulating with ../seq/ssimAll 600 ISA Checks Succeed

2、测试iaddq

usr@ub2004:~/csapplab/archlab/archlab-handout/sim/seq$ (cd ../ptest; make SIM=../seq/ssim)

./optest.pl -s ../seq/ssim -i
Simulating with ../seq/ssimAll 58 ISA Checks Succeed
./jtest.pl -s ../seq/ssim -i
Simulating with ../seq/ssimAll 96 ISA Checks Succeed
./ctest.pl -s ../seq/ssim -i
Simulating with ../seq/ssimAll 22 ISA Checks Succeed
./htest.pl -s ../seq/ssim -i
Simulating with ../seq/ssimAll 756 ISA Checks Succeed

C Part

在这一部分中，将在目录sim/pipe中工作。我们需要修改ncopy函数，使其并行度增加，并且提高运行的效率。ncopy函数将len元素整数数组src复制到一个不重叠的dst，重新计算src中包含的正整数数。

CPE 15.18

下列分别是ncopy的c代码和主要部分原始ys代码（CPE=15.18）。

int ncopy(int *src, int *dst, int len)
{int count = 0;int val;while (len > 0) {val = *src++;*dst++ = val;if (val > 0)count++;len--;}return count;
}

# % rdi = src, %rsi =dst, %rdx = len
ncopy:xorq %rax,%rax		# count = 0;andq %rdx,%rdx		# len <= 0?jle Done		# if so, goto Done:Loop:	mrmovq (%rdi), %r10	# read val from src...rmmovq %r10, (%rsi)	# ...and store it to dstandq %r10, %r10		# val <= 0?jle Npos		# if so, goto Npos:irmovq $1, %r10addq %r10, %rax		# count++
Npos:	irmovq $1, %r10subq %r10, %rdx		# len--irmovq $8, %r10addq %r10, %rdo		# src++addq %r10, %rsi		# dst++andq %rdx,%rdx		# len > 0?jg Loop			# if so, goto Loop:

CPE=11.70 使用iaddq

显然记数+1与迭代地址变化，没有iaddq就必须使用irmovq+opq共2个指令+额外1个寄存器实现，显然实现iaddq有助于我们提高运算效率。
仿照B部分，对pipe_full.hcl进行修改，修改部分如下：

bool instr_valid = f_icode in { INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ, IIADDQ };			#notebool need_regids =f_icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };				#notebool need_valC =f_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };	#noteword d_srcB = [D_icode in { IOPQ, IRMMOVQ, IMRMOVQ, IIADDQ  } : D_rB;		#noteD_icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;1 : RNONE;  # Don't need register
];word d_dstE = [D_icode in { IRRMOVQ, IIRMOVQ, IOPQ, IIADDQ} : D_rB;		#noteD_icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;1 : RNONE;  # Don't write any register
];word aluA = [E_icode in { IRRMOVQ, IOPQ } : E_valA;E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ } : E_valC;		#noteE_icode in { ICALL, IPUSHQ } : -8;E_icode in { IRET, IPOPQ } : 8;# Other instructions don't need ALU
];word aluB = [E_icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL, IPUSHQ, IRET, IPOPQ, IIADDQ } : E_valB;				#noteE_icode in { IRRMOVQ, IIRMOVQ } : 0;# Other instructions don't need ALU
];bool set_cc = E_icode in {IOPQ, IIADDQ} &&						#note: E_icode == IOPQ -> E_icode in {IOPQ, IIADDQ}# State changes only during normal operation!m_stat in { SADR, SINS, SHLT } && !W_stat in { SADR, SINS, SHLT };

将所有irmovq C,%r10 + opq %r10,%rB全部更替为iaddq C,%rA，修改后得到的CPE=11.70，结果如下：

	xorq %rax,%rax		# count = 0;andq %rdx,%rdx		# len <= 0?jle Done		# if so, goto Done:Loop:	mrmovq (%rdi), %r10	# read val from src...rmmovq %r10, (%rsi)	# ...and store it to dstandq %r10, %r10		# val <= 0?jle Npos		# if so, goto Npos:iaddq $1,%rax	# count++
Npos:   iaddq $8, %rdi		# src++iaddq $8, %rsi		# dst++iaddq $-1,%rdx		# len--jg Loop				# if so, goto Loop:

CPE=12.33 条件传送【放弃】

可以看到修改后的代码，使用jle和jg这种控制转移，一旦预测失败就会面临分支惩罚，所以很自然地一个想法就是用条件传送来优化，代码如下：

	xorq %rax,%rax		# count = 0;andq %rdx,%rdx		# len <= 0?irmovq $1,%r11		# %r11 = const 1jle Done		    # if so, goto Done:Loop:	mrmovq (%rdi), %r10	# read val from src...rmmovq %r10, (%rsi)	# ...and store it to dstxorq %r12,%r12		# set take=0andq %r10, %r10		# val <= 0?cmovg %r11,%r12		# if val>0,take=1; else take=0addq %r12,%rax	    # count++iaddq $8, %rdi		# src++iaddq $8, %rsi		# dst++iaddq $-1,%rdx		# len--jg Loop			# if so, goto Loop:

出乎意料地，最终结果CPE=12.33，效果反而变差了，这说明由于在Y86-64下使用条件传送所需的指令更多，这部分的开销超过了预测惩罚，所以我们确定了一个基调：不使用条件传送。

CPE=9.93 4 x 4循环展开

修改了一些细枝末节后，我们直接进入重头戏：对于循环内指令并行度的提升，直接使用循环展开，这里采用4 x 4的循环展开。

4. 4x4循环展开 CPE=9.93xorq %rax,%rax		# count = 0;xorq %rcx,%rcx		# count2 = 0;xorq %rbx,%rbx		# count3 = 0;xorq %r8,%r8		# count4 = 0;rrmovq %rdx,%r9		# limit=len;iaddq $-3,%r9			# limit=len-3;jle After		# if so, goto After:Loop:	mrmovq (%rdi), %r10	rmmovq %r10, (%rsi)	mrmovq $8(%rdi),%r11rmmovq %r11,$8(%rsi)mrmovq $16(%rdi),%r12rmmovq %r12,$16(%rsi)mrmovq $24(%rdi),%r13rmmovq %r13,$24(%rsi)  # 4 x 4 loop expandandq %r10, %r10		# val <= 0?jle b1		# if so, goto Npos:iaddq $1,%rax	# count++
b1: andq %r11,%r11jle b2iaddq $1,%rcx
b2: andq %r12,%r12jle b3iaddq $1,%rbx
b3: andq %r13,%r13jle Npos:iaddq $1,%r8
Npos:   iaddq $32, %rdi		iaddq $32, %rsi		# i=i+4iaddq $-4,%rdx		# len-=4iaddq $-4,%r9		# limit-=4jg Loop				# if so, goto Loop:andq %rdx,%rdx		# len = 0je a1
After:mrmovq (%rdi), %r10	rmmovq %r10, (%rsi)	andq %r10, %r10		# val <= 0?jle Npos2		# if so, goto Npos:iaddq $1,%rax	# count++
Npos2:   iaddq $8, %rdi		# src++iaddq $8, %rsi		# dst++iaddq $-1,%rdx		# len--jg After				# if so, goto After:
a1:addq %rcx,%raxaddq %rbx,%r8addq %r8,%rax

最终测得CPE=9.93，这里我犯了两个错误：

• mrmovq和rmmovq连续使用，这触发了数据读写相关的加载使用冒险，使得两条指令之间插入了气泡bubble，大大拖累了效率。
• 没有意识到这里由于分支语句，%rax的增加并不是关键路径，完全不必使用n x n的循环展开，使用n x 1的循环展开，并且使用了n x n的循环展开后，在最后答案的合并上也耗费了更多的指令。

CPE=7.82 10 x 1循环展开 + 多余指令删除 + 3 x 1剩余处理

	iaddq $-10,%rdx		# limit=len-K;jl loop9			loop10:mrmovq (%rdi),%rcxmrmovq $8(%rdi),%rbxmrmovq $16(%rdi),%rbpmrmovq $24(%rdi),%r8mrmovq $32(%rdi),%r9mrmovq $40(%rdi),%r10mrmovq $48(%rdi),%r11mrmovq $56(%rdi),%r12mrmovq $64(%rdi),%r13mrmovq $72(%rdi),%r14	# 10 x 1 loop expandiaddq $80,%rdirmmovq %rcx,(%rsi)rmmovq %rbx,$8(%rsi)rmmovq %rbp,$16(%rsi)rmmovq %r8,$24(%rsi)rmmovq %r9,$32(%rsi)rmmovq %r10,$40(%rsi)rmmovq %r11,$48(%rsi)rmmovq %r12,$56(%rsi)rmmovq %r13,$64(%rsi)rmmovq %r14,$72(%rsi)	# 10 x 1 loop expandiaddq $80,%rsione:andq %rcx,%rcxjle twoiaddq $1,%rax
two:andq %rbx,%rbxjle threeiaddq $1,%rax
three:andq %rbp,%rbpjle fouriaddq $1,%rax
four:andq %r8,%r8jle fiveiaddq $1,%rax
five:andq %r9,%r9jle sixiaddq $1,%rax
six:andq %r10,%r10jle seveniaddq $1,%rax
seven:andq %r11,%r11jle eightiaddq $1,%rax
eight:andq %r12,%r12jle nineiaddq $1,%rax
nine:andq %r13,%r13jle teniaddq $1,%rax
ten:andq %r14,%r14jle iter10iaddq $1,%raxiter10:iaddq $-10,%rdx		# len-=10jg loop10			# if so, goto Loop:loop9:iaddq $8,%rdx		# len=len+10-2		jle Nloop2			# if len <= 2 ,len = 0 or len = 1 or len = 2 =》 len = -2 or len =-1 or len=0# remain >=3 means using 3 x 1 loop expand
loop3:mrmovq (%rdi),%rcxmrmovq $8(%rdi),%rbxmrmovq $16(%rdi),%rbp 	# 3 x 1 loop expandiaddq $24,%rdirmmovq %rcx,(%rsi)rmmovq %rbx,$8(%rsi)rmmovq %rbp,$16(%rsi) 	# 3 x 1 loop expandiaddq $24,%rsiloop3one:andq %rcx,%rcxjle loop3twoiaddq $1,%rax
loop3two:andq %rbx,%rbxjle loop3threeiaddq $1,%rax
loop3three:andq %rbp,%rbpjle loop3iteriaddq $1,%raxloop3iter:iaddq $-3,%rdx		# len-=10jg loop3			# if so, goto Loop:Nloop2:iaddq $1,%rdx      # if len == 2 not jmpjle Nloop1		   # remain = 0 or remain = 1mrmovq (%rdi),%rcx		# remain = 2mrmovq 8(%rdi),%rbxrmmovq %rcx,(%rsi)rmmovq %rbx,(%rsi)Nloop2one:andq %rcx,%rcxjle Nloop2twoiaddq $1,%rax
Nloop2two:andq %rbx,%rbxjle Doneiaddq $1,%raxNloop1:iaddq $1,%rdxjle Donemrmovq (%rdi),%rcxiaddq $8,%rdirmmovq %rcx,(%rsi)iaddq $8,%rsiNloop1one:andq %rcx,%rcxjle Doneiaddq $1,%rax

最终这一版的CPE=7.82，已经很接近满分7.5了。
这里主要的细节如下：

• 相同寄存器的mrmovq和rmmovq进行隔开，避免加载使用冒险，从而流水线上的执行、译码同时进行，从而塞满流水线。
• %rax的默认值为0，可以省略开头xorq指令
• 采用10 x 1循环展开的原因在于，除了%rax、%rdi、%rbx、%rsi以及不宜使用的%rsp（若要使用必须采用push+pop），Y86-64只剩下10个寄存器。虽然可以采用指令隔开的方法，从而进行更多的循环展开，但对于程序的性能已经没有提升了，在benchmark.pl的结果中可以看到主要的CPE集中于剩余部分
• 由于目前程序受限于剩余部分，即在循环之外的部分，我们需要思考对于个数不超过9个剩余元素的处理，这里采用了3x1的循环展开，采用新的预测分支，一支使用3x1循环展开处理大于3个的情况，另一支采用了分类讨论的方法对0、1、2三种情况的处理。由于第一支经过3x1循环展开后，剩余部分必然<3，自然那地向下走入另一支分支，从而处理了所有的剩余元素情况。

CPE=7.49 分10种情况讨论剩余元素

很自然地，延续上一条的处理流程，在benchmark.pl的测试结果，大头CPE集中于<10的情况，这意味着循环已经优化足够了，必须更加有效地处理剩余元素部分。

	iaddq $-10,%rdx		# limit=len-K;jl remain			loop10:mrmovq (%rdi),%rcxmrmovq $8(%rdi),%rbxmrmovq $16(%rdi),%rbpmrmovq $24(%rdi),%r8mrmovq $32(%rdi),%r9mrmovq $40(%rdi),%r10mrmovq $48(%rdi),%r11mrmovq $56(%rdi),%r12mrmovq $64(%rdi),%r13mrmovq $72(%rdi),%r14	# 10 x 1 loop expandrmmovq %rcx,(%rsi)rmmovq %rbx,$8(%rsi)rmmovq %rbp,$16(%rsi)rmmovq %r8,$24(%rsi)rmmovq %r9,$32(%rsi)rmmovq %r10,$40(%rsi)rmmovq %r11,$48(%rsi)rmmovq %r12,$56(%rsi)rmmovq %r13,$64(%rsi)rmmovq %r14,$72(%rsi)	# 10 x 1 loop expandone:andq %rcx,%rcxjle twoiaddq $1,%rax
two:andq %rbx,%rbxjle threeiaddq $1,%rax
three:andq %rbp,%rbpjle fouriaddq $1,%rax
four:andq %r8,%r8jle fiveiaddq $1,%rax
five:andq %r9,%r9jle sixiaddq $1,%rax
six:andq %r10,%r10jle seveniaddq $1,%rax
seven:andq %r11,%r11jle eightiaddq $1,%rax
eight:andq %r12,%r12jle nineiaddq $1,%rax
nine:andq %r13,%r13jle teniaddq $1,%rax
ten:andq %r14,%r14jle iter10iaddq $1,%raxiter10:iaddq $80,%rdiiaddq $80,%rsiiaddq $-10,%rdx		# len-=10jg loop10			# if so, goto Loop:remain:iaddq $7,%rdx		# recover len <- len+10 and compare len with 3jl leftjg rightjmp remain3left:iaddq $2,%rdxje remain1iaddq $-1,%rdx	je remain2retright:iaddq $-3,%rdx		# compare with 6jg remain789		# remain >=7je remain6			# remain ==6iaddq $1,%rdx		# remain == 4 / 5je remain5jmp remain4remain789:iaddq $-2,%rdxjl remain7je remain8      	# jg remain9 is defaultremain9:mrmovq 64(%rdi),%r8andq %r8,%r8rmmovq %r8,64(%rsi)	remain8:mrmovq 56(%rdi),%r8jle remain82iaddq $1,%raxremain82:rmmovq %r8,56(%rsi)andq %r8,%r8
remain7:mrmovq 48(%rdi),%r8jle remain72iaddq $1,%rax
remain72:rmmovq %r8,48(%rsi)andq %r8,%r8
remain6:mrmovq 40(%rdi),%r8jle remain62iaddq $1,%rax
remain62:rmmovq %r8,40(%rsi)andq %r8,%r8
remain5:mrmovq 32(%rdi),%r8jle remain52iaddq $1,%rax
remain52:rmmovq %r8,32(%rsi)andq %r8,%r8
remain4:mrmovq 24(%rdi),%r8jle remain42iaddq $1,%rax
remain42:rmmovq %r8,24(%rsi)andq %r8,%r8
remain3:mrmovq 16(%rdi),%r8jle remain32iaddq $1,%rax
remain32:rmmovq %r8,16(%rsi)andq %r8,%r8
remain2:mrmovq 8(%rdi),%r8jle remain22iaddq $1,%rax
remain22:rmmovq %r8,8(%rsi)andq %r8,%r8
remain1:mrmovq (%rdi),%r8jle remain12iaddq $1,%rax
remain12:rmmovq %r8,(%rsi)andq %r8,%r8jle Doneiaddq $1,%rax

最终测得CPE=7.49，这里有意思的地方如下：

• 首先直接采用树状结构的分支跳转，会增加指令数，应该尽可能地利用顺序执行这一特性，上述代码中就将remain 4和5的情况自然地放在6和7的处理之后，从而省略一个jmp指令。
• 因为示例代码对于1/2/3/4的测试往往较高，最终发现以3为底最终的效果要优于以4/5的传统二分为底。

总结

到Lab4的C Part，终于遇到了无论如何都无法进一步优化的情况，不得不参考了他人的博客。

• 一方面在于，第5章我看的比较快，虽然在终于熬过了痛苦的前4章后，第5章的内容又流畅又愉快，所以不到3天就看完了，但确实基础可能还没那么牢固。
• 另一方面，尽信书则不如无书，CSAPP中n x 1展开不改变关键路径，效率提升不如n x n循环展开让我绕进了死胡同，中途揪着寄存器与内存IO、条件传送、局部变量死凹，无论如何都无法将CPE降到9以下，却完全忽略了nx1循环展开的可能性。

但还是很愉快地看到在痛苦的2/3/4章后，终于有一章让我有如鱼得水的快乐了，接下来的第6章Cache我早有耳闻，准备在考试之后，认认真真地慢慢精读，以结束第一部分！
——2023.4.17