你的位置:首页 > 操作系统

[操作系统]汇编器构造


 汇编器构造

 

一、             汇编器简介

前面介绍了编译器构造和静态链接器构造的具体方法,而且我们实现了一个将高级语言转化为汇编语言的编译器,同时又实现了一个将多个目标文件链接为一个可执行文件的链接器。现在需要一个连接这两个模块的功能模块——汇编器,它能将一个单独的汇编文件转换为一个可重定位目标文件,如图1-1反映出汇编器在整个编译系统中的地位和功能。

 

图 1-1  静态编译步骤

从本质上讲,汇编器也是编译器,只是它和我们熟知的编译器的有略微的差别。汇编器处理的“高级语言”是汇编语言,输出的是机器语言二进制形式。因此,对于汇编器的构造,实质上和编译器大同小异,也都需要进行词法分析、语法分析、语义处理、符号表管理和代码生成(机器代码)等阶段。

对于编译器来说,代码生成阶段只需要将解析的语法树映射到汇编语言子模块即可(当然还要考虑指令优化问题),而对于汇编器,将解析出的指令简洁的映射到正确机器代码相对比较复杂。另外,由于本汇编器处理的输入文件为编译器生成的汇编文件,经测试,编译生成的汇编文件是正确的汇编文件,因此汇编器不需要考虑源文件会产生错误,因此它的语法分析的目的是识别出输入语言的语法结构并进行解析引导机器代码生成。

另外,汇编器和编译器最大的不同是:汇编语言允许符号后置定义,因此通过一遍扫描无法保证获得某个符号的准确定义信息,所以对于汇编器必须采用两边扫描的方式进行设计,汇编器的设计结构如图1-2所示。

 

图1-2 汇编器结构

从图中可以看出汇编器的设计中,在语法分析模块之前和前述编译器的结构完全相同,只是语法分析时要进行两遍的扫描过程,通过第一遍扫描获取文件定义的所有的段的信息以及全部的符号信息,第二遍扫描根据最新的段表和符号表,将所有的重定位信息收集到重定位表中,然后通过指令生成模块生成了代码段数据。最后,从符号表中抽取有效数据定义形成数据段,符号导出到文件符号表段,再把所有的段按照elf文件的格式组装起来,形成最终的可重定位目标文件*.o。下面就按照上述路程具体说明汇编器设计的内容。

二、             文法定义

和编译器设计过程相同,首先必须明确处理汇编语言的文法定义,按照符合LL(1)文法的规则定义的待处理汇编语言的文法如表2-1所示: 

 

表2-1 汇编文法

上述汇编文法可以识别之前编译器生成的所有代码,从文法定义中,可以看出汇编语言的功能主要如下:

(1)支持段声明,全局符号声明,数据定义db|dw|dd,times关键字和equ宏命令。

(2)支持数据为整数和字符串格式,允许定义中引用符号,数据使用逗号分隔。

(3)支持的指令数:双操作数指令5条,单操作数指令17条,无操作数指令1条。

(4)支持寻址模式:寄存器寻址,立即寻址,寄存器间址,间接寻址,基址+偏移寻址,基址+变址寻址。

明确汇编语言的文法后就可以构造分析程序识别语言的语法结构。

三、             词法分析

汇编器的词法分析过程和编译器相同,也需要扫描器和解析器,区别在于字母表和词法记号的差别。汇编语言的词法记号如表3-1所示。

表 3-1  词法记号

从词法记号表中可以看出汇编语言词法记号的变化:

(1)标识符可以用符号‘@’开头。

(2)增加一部分界符‘[’,‘]’,‘:’。

(3)删除了一部分界符‘*’,‘/’,‘=’,‘>’,‘<’,‘!’,‘;’,‘(’,‘)’,‘{’,‘}’。

(4)注释由分号引导的单行注释。

(5)关键字表有重大变化,所有的汇编助记符、寄存器、汇编器操作符都是关键字。

很明显,随着汇编语法结构的相对简化,词法记号的识别的复杂度也有所降低。另外由于由编译器生成的汇编语言文件是经过测试正确的,因此不需要进行异常处理。

四、             语法分析

语法分析是汇编器设计的核心,从图1-2就可以看出语法分析模块的重要地位。汇编器的语法分析模块不需要进行错误处理和修复的操作,但是必须正确识别并处理每一个关键的语法模块。汇编语言有两大类型的语法模块:数据和指令。数据语法模块要能识别所有类型的符号并存储到符号表,供指令模块和重定位表使用。指令语法模块要填充临时数据结构,供指令生成模块生成正确的操作码和操作数二进制信息。

简单的说,语法分析的目的是填充系统需要的三张表:段表、符号表、重定位表。通过第一遍扫描将输入文件的所有的段信息收集到段表中,所有的符号信息收集到符号表中,然后第二面扫描在产生重定位的地方生成重定位项,填充重定位表。这三张表是输出文件信息的核心,下边就按照这三张表的构造流程逐个说明。

4.1  段表

汇编语言使用section关键字声明段开始,直到下一个段声明或者文件结束位置结束,整个中间部分都属于section声明的段的内容。具体的说,由于编译器生成的汇编文件共有三个段:.text,.data,.bss。又因为我们使用两边扫描源文件的方式,因此,在第二遍扫描之前(第一遍.bss段结束后)汇编器就可以获得所有的段信息。参考链接器设计中elf文件Elf32_Shdr的数据结构可以看出段表项信息的最关键的信息是:段名、偏移、大小。段名在每次section声明时候记录下来即可,偏移计算之前必须知道上一个段的大小,因此段的大小计算是关键中的关键。为此汇编器使用一个全局变量curAddr记录了相对于当前段的起始偏移,每次汇编语言定义一个需要地址空间存储的语法模块,这个curAddr就会累加当前语法模块的大小,直到段声明结束时记录了整个段的大小。至于每个语法模块的大小如何计算,在后边符号表中再具体介绍。另外,由于.bss的特殊性,它的物理大小为0,但是虚拟大小需要计算。比如编译器只使用.bss存储了辅助栈供64k字节,因此虚拟大小为64k,但是占用磁盘空间大小为0。

另外还需要注意的是段的偏移并不是简单的累加段的大小计算,因为还涉及另一个概念——段对齐。这里和链接器类似,段的开始位置必须是一个数的整数倍(一般重定位目标文件是按照4字节对齐),因此在每次累加段偏移的时候需要考虑段对齐的影响。图4-1给出了一个构造段表项一个例子:

 

图4-1 段表构造实例

下面给出了段表项的相关代码: 

void Table::switchSeg()
{
    if(scanLop==1)
    {
        dataLen+=(4-dataLen%4)%4;
        obj.addShdr(curSeg,lb_record::curAddr);//新建一个段
        if(curSeg!=".bss")
            dataLen+=lb_record::curAddr;
    }
    curSeg="";curSeg+=id;//切换下一个段名
    lb_record::curAddr=0;//清0段偏移
}
void Elf_file::addShdr(string sh_name,int size)
{
    int off=52+dataLen;
    if(sh_name==".text")
    {
        addShdr(sh_name,SHT_PROGBITS,SHF_ALLOC|SHF_EXECINSTR,0,off,size,0,0,4,0);
    }
    else if(sh_name==".data")
    {
        addShdr(sh_name,SHT_PROGBITS,SHF_ALLOC|SHF_WRITE,0,off,size,0,0,4,0);
    }
    else if(sh_name==".bss")
    {
        addShdr(sh_name,SHT_NOBITS,SHF_ALLOC|SHF_WRITE,0,off,size,0,0,4,0);
    }
}

 

函数switchSeg在每次段声明的位置被调用,但是只是在第一次扫描时候生成段表项,每次调用后都会记录当前段名到curSeg,并清零curAddr。dataLen记录了当前的段偏移,添加段表项之前都会将之按照4字节对齐后在加上52(elf文件头大小)作为真正的段偏移添加到段表。另外,.bss段声明结束后是不累加段偏移的,这就反映了.bss无物理空间的含义。最后,addShdr按照段名分别生成具体的段表项,记录到段表。

4.2  符号表

符号表是所有表中最重要的,段表使用它计算自身大小,重定位需要它识别重定位符号,最终的数据段和符号表段还需要符号表进行导出。符号表相关的有三个最重要的数据结构:lb_record,Inst和Table。顾名思义,lb_record记录了当前分析出来的符号,Inst记录了当前分析出来的指令,Table是对所有符号的记录,即传统意义上的符号表,不过这里把Inst也作为符号表数据结构的一部分看待。下面首先给出这三种数据结构的定义:

首先说明符号数据结构:

struct lb_record//符号声明记录
{
  static int curAddr;//一个段内符号的偏移累加量
  string segName;//隶属于的段名,三种:.text .data .bss
  string lbName;//符号名
  bool isEqu;//是否是L equ 1
  bool externed;//是否是外部符号,内容是1的时候表示为外部的,此时curAddr不累加
  int addr;//符号段偏移
  int times;//定义重复次数
  int len;//符号类型长度:db-1 dw-2 dd-4
  int *cont;//符号内容数组
  int cont_len;//符号内容长度
  lb_record(string n,bool ex);//L:或者创建外部符号(ex=true:L dd @e_esp)
  lb_record(string n,int a);//L equ 1
  lb_record(string n,int t,int l,int c[],int c_l);//L times 5 dw 1,"abc",L2 或者 L dd 23
  void write();//输出符号内容
};

(1)       curAddr:当前段偏移的静态变量。

(2)       segName:符号隶属于的段名。

(3)       lnName:符号名。

(4)       isEqu:符号是否是equ定义的常量。

(5)       externed:符号是否是外部符号。

(6)       addr:符号的段偏移,若isEqu为true则表示符号的值。

(7)       times:符号定义重复次数,不带times关键字默认为1,equ和外部符号为0。

(8)       len:符号类型长度,db,dw,dd分别为1,2,4字节,无类型为0。

(9)       cont:符号定义的内容,无内容为NULL。

(10)   cont_len:符号定义内容长度,无内容为0。

(11)   lb_record(string n,bool ex):形如L:或者符号引用L dd @e_esp。

(12)   lb_record(string n,int a):形如L equ 1。

(13)   lb_record(string n,int t,int l,int c[],int c_l):形如L times 5 dw 1或者 L dd 2。

(14)   write():输出符号的二进制形式。

可以看出,构造符号记录有五种可能;

(1)形如L:这种标号形式,符号记录为本地局部符号,它代表一个32位地址,不占用任何存储空间。

(2)形如L equ 1这种标号形式,符号记录为本地局部符号,它代表一个32位立即数,不占用任何存储空间。

(3)形如L db 0这种标号形式,符号记录为全局符号,它对应了一串具体的数据,是数据段的组成部分,数据占用的空间大小为times*len*cont_len字节。

(4)形如L db 1这种标号形式,符号记录为全局符号的引用,是extern变量生成的代码,不占用存储空间。

(5)形如call fun这种标号形式,fun如果不存在本地,那么fun就是一个外部符号,它也不占用存储空间。

这些所有的符号都会记录在Table的中,含有实际数据的符号记录在defLbs列表中。

指令数据结构如下,Intel x86指令格式在指令生成时会具体介绍。

struct ModRM//modrm字段
{
  int mod;//0-1
  int reg;//2-4
  int rm;//5-7
};
struct SIB//sib字段
{
  int scale;//0-1
  int index;//2-4
  int base;//5-7
};
struct Inst//指令的其他部分
{
  unsigned char opcode;
  int disp;
  int imm32;
  int dispLen;//偏移的长度
};

(1)       ModRM:指令的modrm字段,若mod=-1说明不存在modrm字段。

(2)       SIB:指令的sib字段,若scale=-1说明不存在SIB字段。

(3)       Inst:指令中其余需要的字段集合。

(4)       opcode:本意为了记录指令的操作码,但由于操作码的不具有统一性,因此此字段不再使用,输出操作码在指令生成的时候确定。

(5)       disp:指令中偏移的大小,用于间接寻址和基址+偏移寻址。

(6)       imm32:32位立即数,用于立即数寻址。

(7)       dispLen:标识disp是8位还是32位。

指令长度的计算在后边指令生成部分会具体说明。

符号表数据结构定义如下:

class Table//符号表
{
public:
  hash_map<string, lb_record*, string_hash> lb_map;//符号声明列表
  vector<lb_record*>defLbs;//记录数据定义符号顺序
  int hasName(string name);
  void addlb(lb_record*p_lb);//添加符号
  lb_record * getlb(string name);//获取已经定义的符号
  void switchSeg();//切换下一个段,由于一般只有.text和.data,因此可以此时创建段表项目
void exportSyms();//导出所有的符号到elf
  void write();
};

(1)       lb_map:

符号数据结构和符号名的哈希表。

(2)       defLbs:记录数据段中所有的符号定义。

(3)       hasName():查看某个符号名是否存在。

(4)       addLb():添加一个符号记录。

(5)       getLb():获取指定名字的符号记录,若不存在添加一个外部符号。

(6)       switchSeg():添加段表项。

(7)       exportSyms():导出所有的非equ定义符号到elf文件中。

(8)       write():输出数据段,即defLbs记录的符号对应的所有数据。

符号表除了记录符号的信息之外,还要保证使用符号表的模块能正确访问对应符号的信息。这里主要处理在addLb和getLb函数中。首先看看addLb的功能:

void Table::addlb(lb_record*p_lb)//添加符号

  if(hasName(p_lb->lbName)&&scanLop==1)//需要决定是否替换,第二次不必更新,没意义
  {
      if(p_lb->externed==false)//局部符号替换外部符号
      {
          delete lb_map[p_lb->lbName];
          lb_map[p_lb->lbName]=p_lb;
      }
  }
  else
  {
    lb_map[p_lb->lbName]=p_lb;
  }
  //按照有效符号定义记录顺序,方便生成数据段,忽略.bss
  if(p_lb->times&&!p_lb->externed&&scanLop==2&&p_lb->segName==".data")
  {
      defLbs.push_back(p_lb);
  }
}

可以看出每次添加符号的时候都会检查符号是否存在,若不存在则说明是第一次遇到这个符号,添加这个符号到符号表,否则说明符号出现过(可能是定义,也可能是引用)则决定是否替换,如果替换符号是本地定义的符号那么就更新符号,否则就不更新。这里只在第一次扫描时决定,第二次扫描直接忽略这个动作。

另外这个函数还记录了含有实体数据的符号,函数在第二次扫描中检查数据段中times不为0的本地变量,这些变量必然是有实际数据的,把它们记录在defLbs列表中,而且它们是按照定义的顺序有序的,这就保证了地址的正确性,这就为生成数据段做了准备。

或许有人会有疑问如何符号的引用生成符号记录的,这里需要了解getLb函数:

lb_record * Table::getlb(string name)
{
  lb_record*ret;
  if(hasName(name))
    ret=lb_map[name];
  else
  {
      //未知符号,添加到符号表(仅仅添加了一次,第一次扫描添加的)
      lb_record*p_lb=lb_map[name]=new lb_record(name,true); 
      ret=p_lb;
  }
  return ret;
}

 

 

getLb函数返回制定符号名称对应的符号结构,当符号不存在的时候,就生成一个外部符号引用结构,一旦出现本地这个符号定义就被替换为更完整的符号结构信息。这样经过一遍的扫描,本地符号引用被替换为真实的符号定义,未被替换的外部符号记录就是真正的外部符号引用。结合上述的addLb的功能可以完整的获得所有符号的结构。

到此为止,汇编程序已经能获得所有的符号信息。但是这些符号并不是最终导入到目标文件的符号,在此之前还必须对一些符号进行过滤和处理,规则如下:

(1)equ定义的符号仅仅是立即时,并不需要导入到目标文件。

(2)按照编译器的约定,以@cal_,@lab_,@while_,@if_以及符号@s_stack都是不会用到或者是局部跳转不会产生重定位信息的符号,这些符号占有很大的比重,可以被优化删除。

(3)按照编译器约定,全局符号的名称格式为:.text段中@str2long,@procBuf,和非@开头的符号(函数名)都是全局符号;.data段中@str_开头的紧跟非数字的符号或者其他符号都是全局的;所有的外部符号都是全局的。

按照这种约定构造的符号记录添加到Elf32_Sym类型的符号表中构成elf文件的符号表,对符号的导出操作在exportSyms函数中。

4.3  重定位表

重定位是支持链接的编译器的核心操作,因为在编译汇编过程中,程序无法确定代码的其实位置的虚拟地址,这个过程被推迟到链接的时候进行计算。由于无法确定数据起始位置的虚拟地址,那么所有数据定义的符号地址都是“假”的地址,但是指令或者数据定义中一旦引用该符号,就有可能需要这个符号的“真实”的地址,这就需要重定位来修正这种偏差,因此,可以简单的说:重定位来源于对符号的引用。无论这种引用是在数据段还是在代码段,当然.bss不会出现重定位,因为.bss内的数据都是0,没法重定位。另外,对符号的绝对、引用绝对是需要重定位的,因为符号定义的段的地址是无法确定的,而引用符号的地方需要的是符号的真实虚拟地址,因此必须重定位。对外部符号的相对引用是绝对需要重定位的,因为外部富符号的地址是未知的,因此必须到链接时重定位。对相同段内符号的相对引用绝对不需要重定位,因为内部符号与当前引用位置的相对位置不会发生变化,因为重定位就没有必要了。

基于此,我们在语法分析时就需要留意对符号引用的语句,一旦出现这种引用就需要查看是否需要为此产生重定位项。在本汇编器文法中共用三种出现重定位项的可能:

(1)数据段中使用了符号引用:如:@s_esp dd @s_base,这个语句是本汇编器唯一一处对数据段冲定位的地方。实际上@s_base是.bss的段的符号,但是不管@s_base出现在何处,因为它是绝对地址,因此必须重定位。

(2)代码段使用符号引用作为立即数,如mov eax,@buffer,由于@buffer真实地址不确定,因此需要对@buffer引用位置重定位。

(3)代码段使用符号引用作为内存地址,如mov [@buffer_len],al,这里@buffer_len地址也不确定,也需要重定位。

(4)代码段使用符号引用作为跳转地址,和之前的指令不同,类似call,jmp,jcc的指令不是把符号地址作为操作数,而是把被引用的符号的地址相对与当前指令的下一条指令的起始地址的偏移作为操作数。因为这种指令是否形成重定位项需要查看被引用的符号是否是外部符号。

这样和链接器联系起来,我们知道elf重定位类型有两种:R_386_32和R_386_PC32,即绝对地址重定位和相对地址重定位,其含义如上所述。那么汇编程序如何处理以上情况呢,这里分别讨论:

对于(1),它是数据段中惟一出现重定位的情况,但是很具有代表性。文法中允许符号定义dd后跟着一系列由都好连接的合法的数据,如L dd 1,2,L2等,这里就需要确定L2出现的地址。在文法中每解析一个逗号数据项都会将数据按照单位放在一个临时整形数组中,放入整数或者标识符数组长度加1,对于标识符记录值为0(反正都需要重定位,记录什么值没有区别),对于串就需要将串按照字节拆分,分别放入数组,数组长度增加量为串长。这样重定位位置就很好确定了,即标号地址+数组长度*类型长度,重定位相关符号位当前引用符号,类型为绝对地址重定位R_386_32。 

对于(2)、(3)(4),由于是在指令中重定位,而指令由于形式的不同,指令的操作码和相关字节都会发生变化,因此无法在语法分析阶段确定重定位的位置。现在我们假设已经知道了重定位的位置,对于一般的指令能确定重定位类型为R_386_32,对于call,jmp,jcc指令重定位类型为R_386_PC32,但是是否这得需要重定位还得继续分析:

bool processRel(int type)//处理可能的重定位信息
{
    if(scanLop==1||relLb==NULL)
    {
        relLb=NULL;
        return false;
    }
    bool flag=false;
    if(type==R_386_32)//绝对重定位
    {
        if(!relLb->isEqu)//只要是地址符号就必须重定位,宏除外
        {
            obj.addRel(curSeg,lb_record::curAddr,relLb->lbName,type);
            flag=true;
        }
    }
    else if(type==R_386_PC32)//相对重定位
    {
        if(relLb->externed)//对于跳转,内部的不需要重定位,外部的需要重定位
        {
            obj.addRel(curSeg,lb_record::curAddr,relLb->lbName,type);
            flag=true;
        }
    }
    relLb=NULL;
    return flag;
}

 

relLb记录了重定位引用符号的结构,根据传递来的重定位类型分别处理:对于绝对地址重定位必须保证被重定位的符号是非equ的符号,这里不再解释。对于相对重定位的符号必须保证是外部符号,因为内部符号不需要相对重定位。这里没有判断引用符号是否是本段的符号,因为跳转指令肯定在代码段中,而跳转指令不可能也不允许跳转到其他段中,因此不需要再做比较。每次调用obj.addRel都会给当前目标文件添加一个重定位项目。

最后一步最“神秘”的部分来介绍指令里边都有什么,如何确定指令的长度,怎么计算指令重定位的位置?

五、             指令生成

作为汇编器最后一个模块,也是最贴近底层的一个模块,指令生成严重依赖于x86的指令的格式。

作者统计了编译器生成的汇编代码的所有指令,一共是23条:双操作数指令5条,mov,cmp,add,sub,lea;但操作数指令17条,call,int,imul,idiv,neg,inc,dec,jmp,je,jg,jl,jge,jle,jne,jna;无操作数指令一条,ret。

那么这些指令信息是如何保存的,以及最后如何输出的,在深入讨论之前,我们必须清楚了解x86的通用指令格式结构。

5.1  x86指令格式

图5-1给出了x86指令的通用结构:

图5-1 x86指令格式

为了直入正题,我们这里只关心我们需要的结构:Opcode,ModRM,SIB,Disp,Imm字段。

对于操作码,大多数通用指令的Opcode是单字节,最多是 2 字节的。Opcode是指令的核心部分,代表指令的功能,是不可缺少的。

ModRM 字节,意为:mod-reg-r/m 按2-3-3比例划分字节。最主要作用是对指令的 operands 提供寻址,另外是对 Opcode 进行补充。ModRM.mod提供寻址模式, ModRM.reg用来提供寄存器 ID,ModRM.r/m 提供register的 ID或直接memory或者引导SIB字节。

有两种情况下是无需用 ModRM 提供寻址的:

(1)一部分操作数是寄存器的,它直接嵌入 Opcode 中。

(2)一部分操作数是立即数的,它直接嵌入指令编码中。

ModRM字节结构如下:

表 5-1  ModRM字节

ModRM.mod 提供r/m寻址的模式,这个模式以 disp长度或者值作区别。当 ModRM.mod = 11 时,它提供 register 寻址。如表5-2所示:

表 5-2  ModRM.mod寻址模式

ModRM.reg 提供寄存器寻址,reg 表示寄存器ID值,或者对 Group属性的Opcode进行补充。如表5-3所示:

表 5-3  ModRM.reg值

 ModRm.r/m提供 register寻址或memory 寻址。寻址模式由ModRM.mod决定。不过需要注意的是当ModRM.mod!=11,且ModRM.r/m==100时,表示引导SIB字段,disp信息仍有效。另外,当ModRm.mod==00时,ModRM.r/m==101,表示32位直接寻址模式,即[disp32]。

对于ModRM字段的具体含义可以参考图5-2:

 

图5-2 ModRM字段含义

SIB 意即:Sacle-Index-Base 也是按 2-3-3比例划分字节。这两个字节用来为 memory 操作数提供 base, index 以及 scale,SIB 是对 ModRM 寻址的一个补充,ModRM 提供的是 registers 寻址、[register] 寻址(寄存器间接寻址)以及 [register + displacement](寄存器基址寻址),SIB 提供的是 [base + index * scale] 这种形式的寻址。即:基址 + 变址寻址。同样,SIB 是可选的,前面已经说明SIB 字节由 ModRM.r/m = 100 引导出来,指令中命名用了 [base + index] 这种地址形式时,必须使用 SIB 进行编码,SIB字节结构如表5-4所示:

表 5-4  SIB字节

(1)SIB.scale 提供 index 寄存器乘数因子,正如表5-4所示,因子值=2^SIB.scale。

(2)SIB.index 提供 index 寄存器寻址,index寄存器的ID见表5-3。另外,当SIB.index==100时,说明没有变址寄存器,只有基址寻址。

(3)SIB.base 提供 base 寄存器寻址,base寄存器的ID见表5-3。另外,当ModRM.mod==00,且SIB.base==101时,说明没有基址寄存器,只有变址寻址。

对于SIB字段的具体含义可以参考图5-3:

 

图5-3 SIB字段含义

Disp字段记录需要的偏移,有两处需要记录disp:一个是形如mov eax,[@buffer]直接内存寻址,这里@buffer就是disp,毫无疑问它是32位的。另一个形如inc [ebp+1]的寄存器基址+偏移寻址,这里disp等于1,按照数据的大小,它是8位的。如果这个值超过127或者小于-128,那么就是32位的。

Imm字段记录立即数寻址的指令,形如mov eax,1,这里imm等于1,imm的长度去决定于另一个寄存器操作数长度。上述指令imm为32位,对于mov al,1,imm表示为8位。

至此对x86指令的格式简单介绍完毕,下边就是在语法模块中分析指令的格式,填充指令的信息到之前的ModRM,SIB,Inst数据结构中去,为生成模块服务。

5.2  指令信息记录

指令信息的记录是随着指令的识别逐渐填充到对应的字段中的,下面按照操作数的类型进行填充指令数据结构。

(1)       首先识别出操作符关键字,记录下来,作为后边处理的依据。

(2)       按照操作数个数分类指令,识别每个操作数类型。

(3)       操作数为整数:mov eax,1,记录里imm=1,操作数类型为立即数。

(4)       操作数为符号:mov eax,@buffer,记录imm为符号地址(重定位),操作数类型为立即数。

(5)       操作数为寄存器:mov eax,ebx,记录寄存器编码到modrm.reg,记录寄存器长度。若第二个操作数也是寄存器,modrm.mod=3,交换rm和reg字节(因此双操作数指令操作选用指令将rm作为目的操作数)。

(6)       操作数包含[],继续识别内存寻址模式,操作数类型为内存。

(7)       直接寻址(一般是符号):modrm.mod=0,modrm.rm=5使用[disp32]寻址方式,disp记录4字节的符号地址(重定位)。

(8)       寄存器间址:对于[esp]:modrm=0x00xxx100引导SIB,SIB=0x00100100。对于[ebp]:实际上是[ebp+0],modrm=0x01xxx101,disp=0,8位。对于一般的寄存器modrm.mod=0,modrm.rm为寄存器编号(reg记录另一个操作数)。

(9)       基址+偏移:对于一般基址寄存器,将modrm.rm设置为基址寄存器编号,disp记录偏移,根据[-128,127]区分disp位数,8位设置mod=1,32位设置modrm.mod=2。若基址寄存器是esp,modrm.rm=4,sib=0x00100100。

(10)   基址+变址:modrm=0x00xxx100引导sib,sib.scale=0,sib.index=变址寄存器编号,sib.base=基址寄存器编号。

这样,23种指令的信息就可以全部记录下来了,生成指令二进制信息时只需要访问对应的三个数据结构即可。

5.3  指令输出

模块定义了一个输出字节的函数:

void writeBytes(int value,int len)
{
  lb_record::curAddr+=len;//计算地址
  if(scanLop==2)
  {
      fwrite(&value,len,1,fout);
      inLen+=len;
  }
}

 

 

 

它按照指定的长度按照little endian(小字节序)的方式输出,而且只在第二次扫描时真正输出数据,一般情况下仅仅累加输出的数据量,即数据偏移,这既是为什么重定位位置能确定以及代码段的长度在第一遍扫描就能计算出看来的原因。

另外对于ModRM和SIB字节输出代码如下:

void writeModRM()
{
    if(modrm.mod!=-1)//有效
    {
        unsigned char mrm=(unsigned char)(((modrm.mod&0x00000003)<<6)
                         +((modrm.reg&0x0000007)<<3)+(modrm.rm&0x00000007));
        writeBytes(mrm,1); 
    }
}
void writeSIB()
{
    if(sib.scale!=-1)
    {
        unsigned char _sib=(unsigned char)(((sib.scale&0x00000003)<<6)
                          +((sib.index&0x00000007)<<3)+(sib.base&0x00000007));
        writeBytes(_sib,1);
    }
}

 

 

首先看双操作数指令的输出方法,这里引入一个操作码表5-5:

表 5-5  双操作数操作码表

每种指令按照先8位操作数后32位操作数分组,每组按照r,r、r,rm、rm,r、r,im的形式记录对应的操作码。按照上述解析出的操作数的类型,不难索引查找到对应的操作码。具体形式分以下情况考虑:

(1)mod=-1时表示立即数指令,这里参考Intel的指令文档。Mov指令需要opcode+modrm.reg后输出1字节操作码。而cmp,add,sub是输出操作码后,在输出一个固定字节+mod.reg字节。对应固定字节为0xf8,0xc0,0xe8。在接下来输出立即数之前还需要在此时处理可能存在的重定位项,因为此时的数据偏移就是重定位的位置。最后根据寄存器操作数的长度输出立即数。

(2)mod=0时表示寄存器寻址,此时输出操作码、ModRM字段,若modrm.rm=5,说明是[disp32]寻址,需要处理重定位项后输出32位disp。若modrm.rm=4需要输出sib字节。

(3)mod=1、2时表示8、32位偏移基址寻址:输出操作码、ModRM和可能的SIB字段后输出disp8/32。

(4)mod=3时表示双寄存器操作数,输出 操作码和ModRM即可。

接着看单操作数指令的处理方法,和双操作数类似,但操作数指令也有一个操作码表,不过却没有双操作数指令操作码那么有规律:

static unsigned short int i_1opcode[]=
{
  0xe8,0xcd,0xf7,0xf7,0xf7,0x40,0x48,0xe9,//call,int,imul,idiv,neg,inc,dec,jmp<rel32>
  0x0f84,0x0f8f,0x0f8c,0x0f8d,0x0f8e,0x0f85,0x0f86,//je,jg,jl,jge,jle,jne,jna<rel32>
  0x50,//push
  0x58//pop
};

 

 

 

这个表中仅仅记录了某类指令的一部分操作码,特殊情况的操作码还需要具体补充。

(1)首先分析跳转指令:call,jmp,jcc共9条指令,call和jmp都是单字节的,jcc都是双字节的,因此分别输出。注意这里jcc操作码不能使用writeBytes(opcode,2)进行输出,因为双字节操作数并不是小字节序的,因此应该拆分输出:writeBytes(opcode>>8,1); writeBytes(opcode,1);接着就需要处理可能存在的相对重定位项,如果重定位项不存在那么输出4字节的偏移=imm-(curAddr+4),否则输出-4,即当前位置相对于下一条指令的偏移。

(2)int指令:输出操作码和8位立即数。

(3)push指令:操作数为立即数时输出0x68操作码和32位立即数,操作数为32位寄存器时输出opcode+modrm.reg字节。

(4)inc指令:操作数为8位寄存器时输出操作码0xfe和0xc0+modrm.reg,操作数是32位寄存器时输出opcode+modrm.reg。

(5)dec指令:操作数为8位寄存器时输出操作码0xfe和0xc8+modrm.reg,操作数是32位寄存器时输出opcode+modrm.reg。

(6)neg指令:若操作数是8位寄存器操作码为0xf6,然后输出0xd8+modrm.reg。

(7)pop指令:输出操作码+modrm.reg。

(8)imul指令:输出操作码和0xe8+modrm.reg。

(9)idiv指令:输出操作码和0xf8+modrm.reg。

无操作数指令只有一条ret,输出字节0xc3。

至此,所有的指令二进制输出完成。

六、             目标文件组装

和之前介绍的链接器文件拼装类似,这里目标文件就是将段表、符号表、重定位表、数据段、代码段组合到elf文件中去,子模块的顺序为elf文件头,.text,.data,.shstrtab,段表,.syntab,.strtab,.rel.text,.rel.data,输出主要流程如下,由于和链接器输出方式类似,这里不做具体代码说明:

(1)输出elf文件头,段表加上空项共8个条目,e_shstrndx=3。

(2)输出代码段数据,填充代码段和数据段的间隙,由于代码段是在第二次扫描时输出的,所以代码段事先输出到一个临时文件中,这里做了一次文件合并,最后删除临时文件。

(3)输出数据段数据,即输出defLbs的符号数据,填充数据段和.bss段的间隙,这里调用了符号记录的write方法。

void lb_record::write()
{
  for(int i=0;i<times;i++)
  {
    for(int j=0;j<cont_len;j++)
    {
        writeBytes(cont[j],len);
    }
  }
}

(4)输出所有段名抽取的字符串形成的.shstrtab。

(5)输出段表,拼装时e_shoff为当前偏移。

(6)输出符号表。

(7)输出所有符号名抽取的字符串形成的.strtab。

(8)输出代码段重定位表和数据段重定位表。

七、             汇编实例

用前述的编译器生成的汇编文件common.s和main.s作为输入,输出文件common.o和main.o,使用readelf命令查看结果如下:

 

 

图7-1 common.o段表

 

 

图7-2 common.o符号表

 

 

图7-3 common.o重定位表

 

 

图7-4 main.o段表

 

 

图7-5 main.o符号表

 

 

图7-6 main.o部分重定位表

将这两个目标文件作为链接器的输入,生成的可执行文件的执行效果在编译器构造中已经演示了,结果说明整个流程下来程序的执行是正常的。

八、             总结

通过对编译器、汇编器、链接器构造的叙述,我们构造了一套完整的编译系统程序,经过代码测试,验证了整个编译系统的正确性。当然,该编译系统仅仅是为了学习gcc相关知识而构造的,不具有主流编译器的工业化性能。但是作为一款亲手构造的的编译系统来说,对于学习和理解编译系统的内容部流程还是有一定的学习价值的。