Week4: 程序的机器级表示2

[OhBonsai]

数组分配与访问

C语言的素组是一个将标量数据聚集成更大数据类型的方式,C语言实现数组的方式非常简单.因此
很容易翻译为机器代码,C语言的一个不同寻常的特点是可以产生指向数组中元素的指针,并对
这些指针进行运算,在机器代码中,这些指针会被翻译成地址来计算.优化编译器非常善于简化
数组索引所使用的地址计算,不过这是C代码和它到机器代码的翻译之间的对应关系有些难以理解
C语言指针不表达长度....首元素的地址就是数组.

基本原则

对于数据类型T和整形常熟N,声明如下:
T A[N];

指针运算

------------------------------------------------------------------------------------------
| 表达式        | 类型    |  值        |                     汇编代码                    |
------------------------------------------------------------------------------------------
| E             | int*    |  xe        |           movq %rdx , %rax                      |
------------------------------------------------------------------------------------------
| E[0]          | int     | M[xe]      |           movq (%rdx) , %rax                    |
------------------------------------------------------------------------------------------
| E[i]          | int     | M[xe+4i]   |           movq (%rdx,%rcx,4), %rax              |
------------------------------------------------------------------------------------------
| &E[2]         | int*    |  xe+8      |           leaq 8(%rdx) , %rax                   |
------------------------------------------------------------------------------------------
| E+i-1         | int*    |  xe+4i-4   |           leaq-4(%rdx, %rcx, 4) , %rax          |
------------------------------------------------------------------------------------------
| *(E+i-3)      | int     |M[xe+4i-12] |           movl-12(%rdx, %rcx, 4), %eax          |
------------------------------------------------------------------------------------------
| &E[i]-E       | long    | i          |           mov %rcx,  %rax                       |
------------------------------------------------------------------------------------------

嵌套的数组

定长数组

C语言编译器能够定长多维数组上的操作代码，这里我们展示优化等级设置为-01时GCC采用的一些优化。假设
我们用如下方式将数据类型fix_matrix声明位16*16的整型数组：

#define N 16
typedef int fix_matrix[N][N]

int fix_prod_ele(fix_matrix A, fix_matrix B, long i, long k) {

		long j;
		int result = 0;
		for (j = 0; j< N; j++) {
				result += A[i][j] * B[j][k];
		}
		return result;
}


int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k ) {
		int *Aptr = &A[i][0];
		int *Bptr = &B[0][k];
		int *Bend = &B[N][k];
		int result = 0;

		do {
				result +=  *Aptr * *Bptr;
				Aptr ++;
				Bptr += N;
		} while (Bptr != Bend);
		return result;
}ypedef int fix_matrix[N][N]

变长数组

历史上如果要申请边长数组，必须使用malloc或者calloc这样的函数为这些数组分配存储空间。而且不得不显示的编码。不过现在可以在分配时候
才计算出数组长度，比如

int var_ele(long n, int A[n][n], long i, long j) {
		return A[i][j];
}


var_ele:
	imulq %rdx , %rdi
	leaq (%rsi, %rdi, 4), %rax
	movl (%rax, %rcx, 4), %eax
	ret

异质的数据结构

C语言提供了两种不同类型的对象组合到一起创建数据类型的机制：

• 结构
• 联合

结构

C语言的struct声明创建了一个数据类型，将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。类似于数组的实现。结构的所有组成部分都存放在内存的一段连续的区域。而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息。指示每个字段的字节编译。它以这些偏移作为内存引用指令的位移。从而才生对结构元素的引用

联合

联合提供了一种方式，能够规避C语言的类型系统，允许多种类型来用一个对象。联合声明的语法和结构的语法是一样的，只不过语义相差比较大，它们用不同的字段来引用相同的内存块

struct S3 {
		char c;
		int i[2];
		double v;
}


union U3 {
		char c;
		int i[2];
		double v;
}

联合用于表示互斥的结构，联合内存的大小是联合内最大的大小。用来表示一些
明显互斥的机构。

集合控制与数据

指针

指针是C语言的一个核心特色，它们以一种同意方式，对不同数据结构中的元素产生了引用。指针有一些
基本概念其实非常简单。再次，我们重点介绍一些指针和它们映射到机器代码的关键原则

• 每个指针都对应于给类型，这个类型表明该指针只想的哪一类的对象，一下面的指针申明为例：

int *ip;
char **cpp;

变量IP[是一个指向int类型的指针，而CPP指针是指向指针指向的对象本身就是一个指向char类型的指针。通常，
如果对象类型为T，那么指针的类型为T*, 特殊的void *类型表示通用指针，比如说malloc函数返回一个通用指针，
然后通过强制类型转换或者赋值操作那样隐式强制类型转换。指针类型不是机器代码中的一部分，它们是一个C怨言
提供的一种抽象，帮助程序是避免寻址错误

• 每个指针都有一个值，这个值是某个指定类型的对象的地址，特殊的NULL(0)表示该指针没有指向任何地方。
• 指针用'&'运算符来创建。这个于是暖夫可以用到任何lvalue类的C表达式上，lvalue意指可以出现在赋值语句左边
  的表达式，这样的例子包括变量一级结构，联合和数组的元素。我们已经看到因为leaq指令是设计用来计算内存引用
  的地址，&运算符的机器代码实现常用的这条指令计算表达式的值
• *操作用于间接引用指针，其结果是要给值。他的类型与该指针的类型一致，间接引用使用内存引用来实现的。要么
  是存储到一个指定的地址，要么是从指定的地址读取。
• 数组和指针精密联系： 一个素组的名字可以向一个指针比那辆一样引用。数组引用与指针运算符和间接引用有一个效果
  数组引用和指针运算都需要用对象大小对偏移量进行伸缩。当我们写表达式p + i.这里的指针P的值是p.得到的地址计算为P + l * I
• 将指针从要给类型强制转换成另外一种类型，只改变的类型，而不改变它的值。强制类型转化的也给效果是改变指针运算的伸缩。
  例如，如果P是要给char *类型的指针。它的值为P。
• 指针可以指向函数，它提供了要给很强的存储与代码传递引用的功能，这些引用可以被程序其他部分调用。例如如果我们有一个函数
  用下面的原型定义

int fun(int x, int *p);

然后我们可以声明要给指针fp, 将它赋值为这个函数，代码如下

int (*fp)(int, int *);
fp = fun;

然后用这个指针来调用这函数；

int y = 1;
int result = fp(3, &y)