【汇编语言与计算机系统结构笔记08】如何实现循环(Loops),gcc历史上经历了多种转换模式(微体系结构角度解释),Switch语句,跳转表

本次笔记内容:
09.控制流-2

文章目录

练习题:条件转移指令局限性

int cread(int *xp) {
	return (xp ? *xp : 0);
}

空指针返回0,否则返回指针所指。

是否可以用如下汇编代码段完成?

# xp in register %edx
movl $0, %eax		# Set 0 as return value
testl %edx, %edx	# Test xp
cmovne (%edx), %eax	# if !0, dereference xp to get return value

答:不可以,因为cmovne:

  • cmove先进行了地址计算;
  • 再决定最后选择谁。
  • 在这道题中,如果xp不等于0的话,就把(%edx)取出来,挪到%eax里面去,替换掉预先填在%eax中的0值;
  • 如果xp是空指针的话,虽然没有将(%edx)移动到%eax中,但是xp已经访问了一个0的地址,这是不对的。

下面是一种正确的操作:

先从c的思考方式入手:

int cread_alt(int *xp) {
	int t = 0;
	return *(xp ? xp : &t);
}

则对应的汇编代码如下:

movl $0 -4(%ebp)		# t = 0
movl 8(%ebp) %eax		# %eax = xp
leal -4(%ebp) %edx
testl %eax %eax
cmove %edx %eax
movl (%eax) %eax

如此,xp等于0时,则无需访问它。

如何实现循环(Loops)

  • 所有的循环模式(while, do-while, for)都转换为“do-while”形式,再转换为汇编形式;
  • 历史上gcc采用过多种转换模式,经历了“否定之否定”的过程:do-while -> Jump-to-middle -> do-while。

“Do-While”循环实例

int fact_do(int x) {
	int result = ;
	do {
		result *= x;
		x = x - 1;
	} while (x > 1);
	return result;
}

编译器首先将代码转换为Goto Version,方便转换成机器语言:

int fact_goto(int x) {
	int result = 1;
	loop:
		result *= x;
		x = x - 1;
		if (x > 1)
			goto loop;
	return result;
}

与汇编相对照:
Registers:
%edx x;
%eax result

fact_goto:
	pushl %ebp			# Setup
	movl %esp, %ebp		# Setup
	movl $1, %eax		# eax = 1
	movl 8(%ebp), %edx	# edx = x

L11:
	imull %edx, %eax	# result *= x
	decl %edx			# x--
	cmpl $1, %edx		# Compare X : 1
	jg L11				#if > goto loop

	movl %ebp, %esp		# Finish
	popl %ebp			# Finish
	ret					# Finish

“While”循环版本

“While”循环版本1
int fact_while(int x) {
	int result = 1;
	while (x > 1) {
		result *= x;
		x = x - 1;
	};
	return result;
}

Goto Version - 1

int fact_while_goto(int x) {
	int result = 1;
	loop:
		if (! (x > 1))
			goto done;
		result *= x;
		x = x - 1;
		goto loop;
	done:
		return result;
}
“While”循环版本2

目前gcc模式(4.0以后(不确定),以及早期gcc模式)如下:

Goto Version - 2

int fact_while_goto2(int x) {
	int result = 1;
		if (! (x > 1))
			goto done;
	loop:
		result *= x;
		x = x - 1;
		if (x > 1)
			goto loop;
	done:
		return result;
}

编译器转换成了do-while模式。

“For” -> “While” -> “Do-While”

对于for循环,也要转换为Goto Version,历程如下:

For Version -> While Version -> Do-While Version -> Goto Version

为什么gcc历史上经历了多种转换模式?

历史上gcc采用过多种转换模式,经历了“否定之否定”的过程:do-while -> Jump-to-middle -> do-while。

以“While”转换成“jump-to-middle”为例

int fact_while(int x) {
	int result = 1;
	while (x > 1) {
		result *= x;
		x = x - 1;
	};
	return result;
}

转换成Goto Version:

int fact_while_goto3(int x) {
	int result = 1;
	goto middle;
	loop:
		result *= x;
		x = x - 1;
	middle:
		if (x > 1)
			goto loop;
	return result;
}

Jump-to-Middle转换成汇编效率更高。

使用gcc 3.4.4 -O2对c代码进行编译:

# x in %edx, result in $eax
	jmp L34				# goto Middle
L35:					# Loop:
	imull %edx, %eax	# 	result *= x
	decl %edx			# 	x--
L34:					# Middle:
	cmp $1, %edx		#	x : 1
	jg L35				#	if >, goto Loop

这么做的好处:

  • 避免了双重测试;
  • 无条件跳转指令处理器运行开销非常低(可以忽略)。

但是问题是:

  • 跳转指令的执行次数是无法改变的(由程序本身决定);
  • 因此从指令次数角度并没有节省什么。

从微体系结构背景解释

调转指令往往会引起一定的性能损失,Branch Prediction技术被引入进行优化。

在硬件中做了一张表,如果发现有跳转指令,使用PC记录其调转结果,之后可以根据表、PC来预测跳转指令是否为跳转。

Branch Prediction的表项数有限,且其依据跳转与否的历史信息来做预测。因此条件跳转指令越多(一般以指令地址来识别),跳转历史信息越碎片化,就越不利于提升预测精确度。

Branch Prediction继续发展,采用了循环预测器技术(US Patent 5909573),能够对loop进行专门的预测,即对于“循环入口”的预测基本为真。

Switch语句

  • 多个case对应同一段处理语句;
  • “Fall through”;
  • case值并不连续。

在内存中设置Jump Table跳转表:

Jump Table Jump Targets
Targ0 Code Block 0
…1 …1

Swith语句示例(x86-32)

long switch_eg(long x, long y, long z) {
	long w = 1;
	switch(x) {
		case 1:
			w = y * z;
			break;
		case 2:
			w = y / z;
			/* Fall Through */
		case 3:
			w += z;
			break;
		case 5:
		case 6:
			w -= z;
			break;
		default:
			w = 2;		
	}
	return w;
}

Setup:

switch_eg:
	pushl %ebp				# Setup
	movl %esp, %ebp			# Setup
	pushl %ebx				# Setup
	movl $1, %ebx			# w = 1
	movl 8(%ebp), %edx		# edx = x
	movl 16(%ebp), %ecx		# ecx = z
	cmpl $6, %edx			# x : 6
	ja .L61					# if > goto default
	jmp *.L62(, %edx, 4)	# goto Jtab[x]

表结构:

  • 每个表项(及跳转地址)占4字节;
  • 基地址是 .L62。

无条件跳转指令:

  • jmp .L61
    • Jump target is denoted by label .L61
  • jmp *.L62(, %edx, 4)
    • Start of jump table denoted by label .L62
    • Register %edx holds x
    • Must scale by factor of 4 to get offset into table
    • Fetch target from effective Address .L61 + x * 4, Only for 0 ≤ x ≤ 6 0 \le x \le 6 0≤x≤6
    • 这表明是一个间接跳转,即目标地址存于内存地址中

本例中表项内容如下图:
【汇编语言与计算机系统结构笔记08】如何实现循环(Loops),gcc历史上经历了多种转换模式(微体系结构角度解释),Switch语句,跳转表

对于switch结构的汇编如下:

switch(x) {
	...
	case 2: // .L57
		w = y/z;
		/* Fall Through */
	case 3: // .L58
		w += z;
		break;
	default: // .L61
		w = 2;
}

其汇编为:

.L61:	// Default case
	movl $2, %ebx			# w = 2
	movl %ebx, %eax			# Return w
	popl %ebx
	leave
	ret
.L57:	// Case 2:
	movl 12(%ebp), %eax		# y
	cltd					# Div prep
	idivl %ecx				# y/z
	movl %eax, %ebx			# w = y/z
	# Fall through
.L58:	// Case 3:
	addl %ecx, %ebx			# w += z
	movl %ebx, %eax			# Return w
	popl %ebx
	leave
	ret
switch(x) {
	...
	case 1: // .L56
		w = y*z;
		break;
	...
	case 5:
	case 6: // .L60
		w -= z;
		break;
	...
}

对于汇编指令:

.L60:	// Case 5&6:
	subl %ecx, %ebx			# w -= z
	movl %ebx, %eax			# Return w
	popl %ebx
	leave
	ret
.L56:	// Case 1:
	movl 12(%ebp), %ebx			# w = y
	imull %ecx, %ebx			# w *= z
	movl %ebx, %eax				# Return w
	leave
	ret

x86-64下的Switch语句

基本与32位版本一样,地址长度64位。

Switch语句实例(case很稀疏)

使用跳转表性能差,不现实,编译器编译成二叉树形式。

上一篇:OpenEuler基础实验


下一篇:54归妹