计算机系统-从应用程序到底层实现 课件 第10讲-程序的机器级表示：控制

《计算机系统》程序的控制《计算机系统》课程教学组2025年春季学期控制的重要性控制现代汉语词典释义：掌握、操纵、占有。语出《魏书·太祖道武帝纪》：“昔朕远祖，总御幽都，控制遐国。”《新唐书》亦云：“劲兵重地，控制万里。”程序的控制：依据算法设定的逻辑，决定程序执行过程中数据的流向和指令执行的顺序。理论和实践证明，无论多复杂的算法均可通过顺序、选择、循环3种基本控制结构构造出来。程序控制直接决定了程序的正确运行和运算结果的正确获得。程序控制与体系机器底层的程序控制方式与计算机体系密切相关Win-tel架构和生态统治了全球大部分市场。ARM架构作为开源架构被很多国产系统借鉴和使用。iOS自成体系，且非常封闭。Android系统号称开源，但华为同样遭到Google打压封锁。飞天（阿里）、麒麟（Ubuntu）、鸿蒙（华为）等国产体系正迎头赶上。程序控制的意义程序控制结构组成了程序的主体：顺序结构、选择结构、循环结构确保程序的运行按照算法逻辑的设定进行提供了程序调试的关键节点，便于观察重要数据的流向思考：大学生活就是基于人生规划执行的一段程序，大学生应当编写好自己的“程序控制”代码，确保大学学业的顺利完成。控制：条件码条件分支循环内容提要01020304switch语句处理器状态当前运行程序的相关信息临时数据

(%eax,…)运行栈帧的地址

(%ebp,%esp

)即将要执行的指令地址

(%eip,…)标志位

(CF,ZF,SF,OF)%eip通用寄存器当前栈指针当前栈帧指令指针CFZFSFOF%eax%ecx%edx%ebx%esi%edi%esp%ebp条件码每个条件码占一个bitCF最高位产生了进位，无符号操作数的溢出SF

符号标志，操作结果为负数ZF

零标志OF

溢出标志(有符号数signed)例如:addl/addqSrc,Dest↔t=a+bCFset

，如果t溢出ZFset

，如果

t==0SFset

，如果

t<0(assigned)OFset，如果有符号数溢出lea/mov

指令不设置条件码条件码寄存器CMPcmplSrc,Dest;Dest–Src,影响标志位cmplb,a

等价于计算

a-b，但不改变a与b的值。CFset 无符号数运算时有进位ZFset

如果

a==bSFset

如果

有符号数(a-b)<0OFset

如果有符号数运算溢出条件码设置TESTtestl/testqSrc,Dest；Dest&Src，影响标志位testlb,a等价于计算a&b（但不改变a或b的值）ZF

set

如果a&b==0SF

set

如果a&b<0条件码设置条件码设置以四个bit的数为例,有符号数能表示-8~7（1000~0111），无符号数能表示0~15（0000~1111）6>36-3=3, SF＝0, OF＝0，

SF⊕OF＝04>-24-(-2)=6, SF=0, OF=0-4<-2-2-(-4)=2, SF=0, OF=06<76-7=-1, SF=1, OF=0, SF⊕OF＝1-4>-6-4-(-6)=2, SF=0, OF=0-4<7-4-7=-11=10101=0101(正), SF=0, OF=1, SF⊕OF＝17>-57-(-5)=12=01100=1100(负), SF=1, OF=1, SF⊕OF＝0当出现：正+正=负、负+负=正、正-负=负、负-正=正

的情况，就是产生了溢出，OF=1条件码设置SetX指令：根据条件码的组合将一个字节设置为0或1SetXConditionDescriptionsete/setzZFEqual/Zerosetne/setnz~ZFNotEqual/NotZerosetsSFNegativesetns~SFNonnegativesetg~(SF^OF)&~ZFGreater(Signed)setge~(SF^OF)GreaterorEqual(Signed)setl(SF^OF)Less(Signed)setle(SF^OF)|ZFLessorEqual(Signed)seta~CF&~ZFAbove(unsigned)setbCFBelow(unsigned)有符号数无符号数设置条件码movl12(%ebp),%eax #eax=ycmpl%eax,8(%ebp) #Comparex:ysetg%al #al=x>ymovzbl%al,%eax #Zerorestof%eaxintgt(intx,inty){returnx>y;}Body%eax%ah%al课堂习题leal $8(%edx,%eax,2),%eaxleal (,%edx,4),%edxcmpl %edx,%eaxsetg %cl%eax0x08%ecx0x00%edx0x06%eax=0x1d,%edx=0x16,%cl=0x00%eax=0x1e,%edx=0x18,%cl=0x00%eax=0x30,%edx=0x24,%cl=0x01%eax=0x1e,%edx=0x18,%cl=0x01控制：条件码条件分支循环内容提要01020304switch语句跳转指令jX指令：根据不同的条件跳转到某条指令处执行jXConditionDescriptionjmp1无条件跳转je/jzZFEqual/ZeroJne/jnz~ZFNotEqual/NotZerojsSFNegativejns~SFNonnegativejg~(SF^OF)&~ZFGreater(Signed)jge~(SF^OF)GreaterorEqual(Signed)jl(SF^OF)Less(Signed)jle(SF^OF)|ZFLessorEqual(Signed)ja~CF&~ZFAbove(unsigned)jbCFBelow(unsigned)有符号数无符号数条件跳转intabsdiff(intx,inty){intresult;if(x>y){result=x-y;}else{result=y-x;}returnresult;}absdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L6subl%eax,%edxmovl%edx,%eaxjmp.L7.L6:subl%edx,%eax.L7:popl%ebpretBody1SetupFinishBody2bBody2a%edx=x%eax=y条件跳转条件跳转absdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L6subl%eax,%edxmovl%edx,%eaxjmp

.L7.L6:subl%edx,%eax.L7:popl%ebpretBody1SetupFinishBody2bBody2aintgoto_ad(intx,inty){intresult;if(x<=y)gotoElse;result=x-y;gotoExit;Else:result=y-x;Exit:returnresult;}C中可以采用goto语句进行跳转，与机器级的语言风格类似但通常被认为是一种比较“low”的编程风格%edx=x%eax=y分支跳转CCodeval=Test?Then_Expr:Else_Expr;GotoVersionnt=!Test; if(nt)gotoElse;val=Then_Expr;

gotoDone;Else:val=Else_Expr;Done: ...Test是一个返回整数值的表达式=0逻辑假≠0逻辑真为每一个分支都产生一段代码根据条件执行合适的代码段val=x>y?x-y:y-x;等价条件传送条件传送指令——满足条件才传送Instructionsupports:if(Test)DestSrc先计算一个条件操作的两种结果，然后根据条件选择某一个优势：能够更好的匹配现代处理器的特性流水线分支预测CCodetval=Then_Expr;result=Else_Expr;t=Test;if(t)result=tval;returnresult;条件传送intcomvdiff(intx,inty){inttval=y-x;intrval=x-y;inttest=x<y;if(test)rval=tval;resultrval;}comvdiff:movl8(%ebp),%ecxmovl12(%ebp),%edxmovl%edx,%ebxsubl%ecx,%ebxmovl%ecx,%eaxsubl%edx,%eaxcmpl%edx,%ecxcmovle%ebx,%eaxabsdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L6subl%eax,%edxmovl%edx,%eaxjmp.L7.L6:subl%edx,%eax.L7:popl%ebpretCCode条件传送条件跳转避免了跳转指令CPU无需做分支预测，避免预测错误的代价流水线效率更高条件传送C代码非优化编译：gcc-Stest.c：汇编代码出现了jle这样的跳转指令。对于使用了流水线的CPU，这样的跳转是存在隐患的（P140），分支预测失败就会刷新掉所有流水线中取到而未执行的指令，影响运行性能。优化：gcc-S-O1test.c经过优化后的代码没有了跳转指令，取而代之的是一个条件传送指令——cmovle。使得控制流不依赖于数据，流水线也更容易保持满状态。计算代价非法操作副作用两个计算过程都需要运行一般来说，只有两个计算过程都比较简单的时候，才能够发挥优势在p为0的时候，仍然会去引用*p，从而产生非法操作两个表达式都进行了计算产生了意料之外的赋值过程条件传送val=Test(x)?Hard1(x):Hard2(x);val=p?*p:0;val=x>0?x*=7:x+=3;课堂思考使用条件传送时要如何避免出现错误？如何提高效率？控制：条件码条件分支循环内容提要01020304switch语句do-while循环CCodeintpcount_do(unsignedx){intresult=0;

do{result+=x&0x1;x>>=1;}while(x);returnresult;}计算x中有多少个1(“popcount”)

使用条件跳转指令来进行条件判断movl

$0,%ecx #result=0.L2: #loop:movl %edx,%eaxandl $1,%eax #t=x&1addl %eax,%ecx #result+=tshrl %edx #x>>=1jne .L2 #If!0,gotoloop寄存器%edxx%ecxresultwhile循环CCodeforwhileloopCcodefordoloopWhile和do-while二者的代码是否完全一致?都是条件测试失败退出循环do-while循环至少执行一次循环体intpcount_while(unsignedx){intresult=0;

while(x){result+=x&0x1;x>>=1;}returnresult;}intpcount_do(unsignedx){intresult=0;do{result+=x&0x1;x>>=1;}

while(x)returnresult;}for循环CCode#defineWSIZE8*sizeof(int)intpcount_for(unsignedx){inti;intresult=0;

for(i=0;i<WSIZE;i++){unsignedmask=1<<i;result+=(x&mask)!=0;}returnresult;}各循环对比for(Init;Test;Update)BodyForVersionInit;while(Test){BodyUpdate;}WhileVersionInit;if(!Test)gotodone;doBodyUpdatewhile(Test);done:Init;if(!Test)gotodone;loop:BodyUpdateif(Test)gotoloop;done:HunanUniversityDo-whileVersionGotoVersion控制：条件码条件分支循环内容提要01020304switch语句switch语句多重分支使用跳转表x＝2时无breaklongswitch_eg(longx,longy,longz){longw=1;switch(x){case1:w=y*z;break;case2:w=y/z;/*FallThrough*/case3:w+=z;break;case5:case6:w-=z;break;default:w=2;}returnw;}跳转表CodeBlock0Targ_0:CodeBlock1Targ_1:CodeBlock2Targ_2:CodeBlockn–1Targ_n-1:•••target=JTab[x];goto*target;switch(x){caseval_0:Block0caseval_1:Block1•

•

•caseval_n-1:Blockn–1}SwitchFormApproximateTranslationTarg_0Targ_1Targ_2Targ_n-1•••jtab:JumpTableJumpTargetsswitch语句setup:longswitch_eg(longx,longy,longz){longw=1;switch(x){...}returnw;}switch_eg:pushl %ebp #Setupmovl %esp,%ebp #Setupmovl 8(%ebp),%eax #%eax=xcmpl $6,%eax #Comparex:6ja .L8 #Ifunsigned‘>’gotodefaultjmp *.L4(,%eax,4) #Goto*JTab[x]注意：此处W没有进行初始化Targ0Targ1Targ2Targn-1•••jtab:JumpTableJumptable.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6跳转表结构每个跳转地址需要4字节基址在

.L4跳转Direct：jmp.L2直接跳转，地址为.L2Indirect：jmp*.L4(,%eax,4)跳转表基地址：.L44是因为每个地址占4个字节取到有效地址.L4+eax*40≤x≤6JumpTable.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6跳转表JumpTable.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6switch(x){case1://.L3w=y*z;break;case2://.L5w=y/z;/*FallThrough*/case3://.L9w+=z;break;case5:case6://.L7w-=z;break;default://.L8w=2;}代码块1.L3:#x==1movl 12(%ebp),%eax#yimull 16(%ebp),%eax#w=y*zjmp .L2 #Gotodoneswitch(x){case1: //.L3w=y*z;break;...}FallThroughlongw=1;...switch(x){... case2:w=y/z;/*FallThrough*/case3:w+=z;break;...}case2:w=y/z;gotomerge;case3:w=1;merge:w+=z;代码块2&3.L5: #x==2movl 12(%ebp),%eax

#ycltdidivl16(%ebp) #y/zjmp.L6.L9:

#x==3movl $1,%eax

#w=1.L6:

#merge:addl 16(%ebp),%eax #+=zjmp .L2 #Gotodonelongw=1;...switch(x){...case2: //.L5w=y/z;/*FallThrough*/case3://.L9w+=z;break;...}代码块5&6&default.L7: #x==5,6movl $1,%eax#w=1subl 16(%ebp),%eax#w=1-zjmp.L2#gotodone.L8: #defaultmovl$2,%eax#w=2.L2: #doneswitch(x){...case5://.L7case6://.L7w-=z;break;default://.L8w=2;}代码块：结束returnw;.L2: #done:popl

%ebpret使用跳转表是一种非常有效的实现多重分支的方法目标代码准备阶段Label.L8becomesaddress0x80484b8Label.L4becomesaddress0x804868008048480<switch_eg>:...8048489: 772d ja80484b8<switch_eg+0x38>804848b: ff248580860408 jmp*0x8048680(,%eax,4)switch_eg:...ja.L8 #Ifunsigned>gotodefaultjmp*.L4(,%eax,4) #Goto*JTab[x]AssemblyCodeDisassembledObjectCode目标代码：跳转表跳转表在反汇编代码中无法直接看到，可以通过GDB来观察gdbswitch(gdb)x/7xw0x8048680Examine7hexadecimalformat“words”(4-byteseach)—x/7xw0x8048680: 0x080484b8 0x08048492 0x0804849b 0x080484a40x8048690: 0x080484b8 0x080484ae 0x080484ae跳转表解释.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=60x8048680: 0x080484b8 0x08048492 0x0804849b 0x080484a40x8048690: 0x080484b8 0x080484ae 0x080484aeAddressValuex0x80486800x80484b800x80486840x804849210x80486880x804849b20x804868c0x80484a430x80486900x80484b840x80486940x80484ae50x80486980x80484ae6反汇编x=1x=2x=3x=5,6default8048492:8b450c mov0xc(%ebp),%eax8048495:0faf4510 imul0x10(%ebp),%eax8048499:eb22 jmp80484bd<switch_eg+0x3d>804849b:8b450c mov0xc(%ebp),%eax804849e:99 cltd804849f:f77d10 idivl0x10(%ebp)80484a2:eb05

jmp80484a9<switch_eg+0x29>

80484a4:b801000000 mov$0x1,%e