加载中…
正文 字体大小:

底层虚拟机(LLVM)中间语言(IR)基本语法简介

(2012-04-11 16:59:05)
标签:

it

分类: 专业领域

 

根据编译原理知识,编译器不是直接将源语言翻译为目标语言,而是翻译为一种“中间语言”,我们编译器从业人员称之为“IR--指令集,之后再由中间语言,利用后端程序和设备翻译为目标平台的汇编语言;

无疑,不同编译器的中间语言IR是不一样的,而IR可以说是集中体现了这款编译器的特征----他的算法,优化方式,汇编流程等等,想要完全掌握某种编译器的工作和运行原理,分析和学习这款编译器的中间语言无疑是重要手段,另外,由于中间语言相当于一款编译器前端和后端的“桥梁”,如果我们想进行基于llvm的后端移植,无疑需要开发出对应目标平台的编译器后端,想要顺利完成这一工作,透彻了解llvm的中间语言无疑是非常必要的工作。

Llvm相对于gcc的一大改进就是大大提高了中间语言的生成效率和可读性,我个人感觉llvm的中间语言是一种介于c语言和汇编语言的格式,他既有高级语言的可读性,又能比较全面地反映计算机底层数据的运算和传输的情况,精炼而又高效,相对而言,gcc的中间代码有如科幻小说一般~~~~~

******************************************************************************

 

首先用vim命令创建一个新的c程序代码文件try1.c

 

 

int main()

{

int a,b;

return a+b;

}

 

 

Clang try1.c -o try1

生成可执行文件

Clang -emit-llvm try1.c -S -o try1.ll

生成中间代码文件

Vim try1.ll

查看:

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ModuleID 'try1.c'

target datalayout "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

target triple "i386-pc-linux-gnu"

 

 

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %a alloca i32, align 4

  %b alloca i32, align 4

  store i32 0, i32* %retval 

  %0 load i32* %a, align 4

  %1 load i32* %b, align 4

  �d add nsw i32 %0, %1

  ret i32 �d

}

 

 

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

 

 

根据llvm.org上的描述,@代表全局变量,%代表局部变量,那么无疑,在llvm IR看来,int main这个函数,或者说他的函数返回值是个全局变量,其内部的b是局部变量。

 

 

在这段代码里,我们找到了我们之前定义的ab

  %a alloca i32, align 4

  %b alloca i32, align 4

那么其他字符分别代表什么操作呢?

Alloca

Alloca相当于变量声明:

 

llvm文档上对于Alloca的解释是:The 'allocainstruction allocates memory on the stack frame of the currently executing function, to be automatically released when this function returns to its caller.

“alloca指令用于分配内存堆栈给当前执行的函数,当这个函数返回其调用者(我自己对于caller的翻译)时自动释放

 

感觉跟c语言里的malloc差不多,不过当然,llvm更加“底层”。

 

i32

 

 

可以得知这其实是在设置整数位长度 document里说的很明白:i是几这个整数就会占几位(bit),i32的话就是32位,4字节;i后面的数字可以随意写,这体现的就是llvm中间语言类似汇编的特征;

 

 

 

align 

Language Reference Manual似乎没有这个关键字的注释,align 的意思是“对齐”那么这个对齐的意思究竟是什么?

 

 

 

"对齐"的意义是:若一个结构中含有一个int,一个char,一个int则他应该占用4*3=12字节,虽然char本身只占用一个字节的空间,但由于要向4“对齐”所以其占用内存空间仍为4(根据大端小端分别存储)

 

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

 

int main()

{

double a=128;

 

 

}

                                                                          

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

它生成的中间代码是这样的:

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

 

ModuleID 'try5.c'

target datalayout "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

target triple "i386-pc-linux-gnu"

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %a alloca double, align 8

  store i32 0, i32* %retval

  store double 1.280000e+02, double* %a, align 8

  %0 load i32* %retval

  ret i32 %0

}

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

 %a    alloca   double,   align    8

可以看align 后面跟的数字变成4而不是8~~~~~~

 

 

 

 

i32, align 4的意义就应该是:向4对齐,即便数据没有占用4个字节,也要为其分配4字节,这样使得llvm  IR在保证了数据格式一致性的前提条件下,定义数据型时非常灵活,不仅可以任意定义整形和浮点型的长度(iX,iXX,iXXX.........),甚至还允许使用不同的数制,比如你需要使用64进制数字(?),那就只要i48, align 6即可。

 

 

 

这是ab的情况,至于那个  %retval alloca i32, align 4

中的retval,它无疑是return value 返回值的缩写,但它很有意思,它存储的值不一定就是返回值,它在上述return a+b的时候除了得到个0值之外根本不参与任何运算和传输,而且根据试验情况,这个retval似乎只在main函数中出现,而且由于main的返回值必须是int,这个retval也总是“  %retval alloca i32, align  ”事实上,当提供高优化等级之后,retval就不会再出现,这个变量可以被认为是非必要的;

 

 

 

证明:

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Try.c:

double dou()

{

 

double a,b;

return a+b;

 

}

 

int  main()

{

 

int c,d;

return c+d;

 

}

 

.............................................................................................

Try.ll:

 

define double @dou() nounwind {

entry:

  %a alloca double, align 8

  %b alloca double, align 8

  %0 load double* %a, align 8

  %1 load double* %b, align 8

  �d fadd double %0, %1

  ret double �d

}

 

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %c alloca i32, align 4

  %d alloca i32, align 4

  store i32 0, i32* %retval

  %0 load i32* %c, align 4

  %1 load i32* %d, align 4

  �d add nsw i32 %0, %1

  ret i32 �d

}

     

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

我猜测这个retval可能是为后端留的某个接口,因为我是在x86下运行llvm所以默认数据型是int,但是这也仅仅是我的猜测,我自己并不知道retval是什么,我在文档上和网上也没找到答案;

 

 

 

研究了以上这些后,之后的程序语句:

  %0 load i32* %a, align 4

  %1 load i32* %b, align 4

就好理解了;

 

 

它与allocastore均属于“Memory Access and Addressing Operations

Load是“装载”,即读出内容,store则是写入;

 

这之后是运算命令:

 

 

 

Add是加

Sub是减

Mul是乘

Div是除

Rems是求余

前头加f的是浮点运算,加u的是返回无符号整型值(unsigned integer)加s返回的是有符号的;

 

 

 

ret i32 �d表示返回加的结果,如果是void型的函数,就ret void

 

******************************************************************************

 

 

 

4c语言基本条件语句和循环语句:

If     which for switch

 

 

 

 

If:

Try3.c:

 

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()

{

 

int a,b,c;

 

a=1;

b=2;

c=0;

if(a>b)

{c=1;}

else

{c=2;}

 

}

        

生成中间代码文件:

 

ModuleID 'try3.c'

target datalayout "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

target triple "i386-pc-linux-gnu"

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %a alloca i32, align 4

  %b alloca i32, align 4

  %c alloca i32, align 4

  store i32 0, i32* %retval

  store i32 1, i32* %a, align 4

  store i32 2, i32* %b, align 4

  store i32 0, i32* %c, align 4

  %0 load i32* %a, align 4

  %1 load i32* %b, align 4

  %cmp icmp sgt i32 %0, %1

  br i1 %cmp, label %if.then, label %if.else

 

if.then:                                          preds %entry

  store i32 1, i32* %c, align 4

  br label %if.end

 

if.else:                                          preds %entry

  store i32 2, i32* %c, align 4

  br label %if.end

 

if.end:                                           preds %if.else, %if.then

  %2 load i32* %retval

  ret i32 %2

}

 

 

 

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

if的中间语言里,主要有这么几个陌生关键字:

icmp 

br 

label 

 

逐个分析:

Icmp

 

Llvm.org  explanation

 

Syntax:

  <result> icmp <cond> <ty> <op1>, <op2>   yields {i1} or {<N i1>}:result

 

Overview:

The 'icmp' instruction returns boolean value or vector of boolean values based on comparison of its two integer, integer vector, pointer, or pointer vector operands.

Icmp可以根据两个整数值的比较(op1op2)返回一个布尔类型的值或者布尔矢量(?)

比较规则由参数cond确定;

具体比较规则如下:

 eq: yields true if the operands are equal, false otherwise. No sign interpretation is necessary or performed.

 ne: yields true if the operands are unequal, false otherwise. No sign interpretation is necessary or performed.

 ugt: interprets the operands as unsigned values and yields true if op1 is greater than op2.

 uge: interprets the operands as unsigned values and yields true if op1 is greater than or equal to op2.

 ult: interprets the operands as unsigned values and yields true if op1 is less than op2.

 ule: interprets the operands as unsigned values and yields true if op1 is less than or equal to op2.

 sgt: interprets the operands as signed values and yields true if op1 is greater than op2.

 sge: interprets the operands as signed values and yields true if op1 is greater than or equal to op2.

 slt: interprets the operands as signed values and yields true if op1 is less than op2.

 sle: interprets the operands as signed values and yields true if op1 is less than or equal to op2.

 

 

 sgt: interprets the operands as signed values and yields true if op1 is greater than op2.

也就是说:Sgt的意思就是若整数op1大于op2的话,cmp 就是true,否则就是false

无疑,icmp是用于判断的指令;

但是仅仅判断出结果来还不够,仍需要根据判断结果进行相应的选择性操作,if语句才完整;

 

Br

Llvm.org  explanation

 

Syntax:

  br i1 <cond>, label <iftrue>, label <iffalse>

  br label <dest>          Unconditional branch

 

Overview:

Llvm.org  explanation

 

The 'br' instruction is used to cause control flow to transfer to different basic block in the current function. There are two forms of this instruction, corresponding to conditional branch and an unconditional branch.

Br提供一个选择分支结构,可根据cond的情况使程序转向label <iftrue>label <iffalse>

另外br也有一种特殊形式:无条件分支(Unconditional branch):当在某种情况时;不必进行条件判断而直接跳转至某一个特定的程序入口标签(label)处(感觉类似于一个“goto”);

如:

if.then:                                          preds %entry

  store i32 1, i32* %c, align 4

  br label %if.end

If then完事后,直接跳转到if.end

 

 

label 

严格的讲它也是一种数据类型(type),但它可以标识入口,相当于代码标签;

综上我们可知:

一个if工作的流程是:

1.开始

2.得到两个操作数的值和比较条件;

3.开始比较,得到比较布尔值(true或者false

4.根据布尔比较值使程序跳转到分支入口去;

 

 

While:

例子:

Try7.c:

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()

{

int a,i;

while (i<10)

{

i=i+1;

a=a*2;

}

 

}

生成的中间代码:

ModuleID 'try7.c'

target datalayout "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

target triple "i386-pc-linux-gnu"

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %a alloca i32, align 4

  %i alloca i32, align 4

  store i32 0, i32* %retval

  br label %while.cond

 

while.cond:                                       preds %while.body, %entry

  %0 load i32* %i, align 4

  %cmp icmp slt i32 %0, 10

  br i1 %cmp, label %while.body, label %while.end

 

while.body:                                       preds %while.cond

  %1 load i32* %i, align 4

  �d add nsw i32 %1, 1

  store i32 �d, i32* %i, align 4

  %2 load i32* %a, align 4

  %mul mul nsw i32 %2, 2

  store i32 %mul, i32* %a, align 4

  br label %while.cond

 

while.end:                                        preds %while.cond

  %3 load i32* %retval

  ret i32 %3

}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////   

可以看到相对于ifwhilellvm IR中的实现几乎没有用到新的指令,可以说,所谓的循环语句while==if+分支循环;

 

While的运行流程是:首先跳到while.cond: 相关变量得到初始值后判断是否满足继续循环条件,若满足,就转到while.body: 进行循环实际操作,一次实际操作运行完后再次跳到while.cond:进行条件判断,如此循环~;若否,则直接跳到  while.end: 终止循环;

 

 

 

 

While~~~原来这么简单~~~~~~      

 

 

For

例子程序:

Try8.c:

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Imt main()

{

Int a,i;

For(i=0;i<10;i++)

{

A=a*2;

 

}

 

}

 

 

生成中间:

 

 

 

ModuleID 'try8.c'

target datalayout "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

target triple "i386-pc-linux-gnu"

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %i alloca i32, align 4

  %a alloca i32, align 4

  store i32 0, i32* %retval

  store i32 0, i32* %i, align 4

  br label %for.cond

 

for.cond:                                         preds %for.inc, %entry

  %0 load i32* %i, align 4

  %cmp icmp slt i32 %0, 10

  br i1 %cmp, label %for.body, label %for.end

 

for.body:                                         preds %for.cond

  %1 load i32* %a, align 4

  %mul mul nsw i32 %1, 2

  store i32 %mul, i32* %a, align 4

  br label %for.inc

 

for.inc:                                          preds %for.body

  %2 load i32* %i, align 4

  %inc add nsw i32 %2, 1

  store i32 %inc, i32* %i, align 4

  br label %for.cond

 

for.end:                                          preds %for.cond

  %3 load i32* %retval

  ret i32 %3

}

 

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

可以看到for循环同样也没有什么新的指令出现;它一样是条件判断+分支循环,只不过比while更高级的地方在于:它把用于判断是否继续循环的条件“集成”进了函数体,故而也比while多出了个“for.inc:”:用于处理For(i=0;i<10;i++)中“i”的运算;证明:

若把For(i=0;i<10;i++)

改为:

For(i=0;i<10;i*2)

for.inc:会变为:

 

for.inc:                                          preds %for.body

  %2 load i32* %i, align 4

  %mul1 mul nsw i32 %2, 2

  store i32 %mul1, i32* %i, align 4

  br label %for.cond

 

 

 

 

 

 

 

 

 

 

 

Switch:

例子程序:

Try9.c:

 

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

int main()

{

 

int a,b;

switch(a)

{

case 0:

{b=1;}

case 1:

{b=2;}

case 2:

{b=3;}

}

}

 

 

转换为中间代码:

ModuleID 'try9.c'

target datalayout "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

target triple "i386-pc-linux-gnu"

 

define i32 @main() nounwind {

entry:

  %retval alloca i32, align 4

  %a alloca i32, align 4

  %b alloca i32, align 4

  store i32 0, i32* %retval

  %0 load i32* %a, align 4

  switch i32 %0, label %sw.epilog [

    i32 0, label %sw.bb

    i32 1, label %sw.bb1

    i32 2, label %sw.bb2

  ]

 

sw.bb:                                            preds %entry

  store i32 1, i32* %b, align 4

  br label %sw.bb1

 

sw.bb1:                                           preds %entry, %sw.bb

  store i32 2, i32* %b, align 4

  br label %sw.bb2

 

sw.bb2:                                           preds %entry, %sw.bb1

  store i32 3, i32* %b, align 4

  br label %sw.epilog

 

sw.epilog:                                        preds %sw.bb2, %entry

  %1 load i32* %retval

  ret i32 %1

}

 

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

可以看到,switch就比较有意思了:

他的中间语言代码形式与c语言代码非常像,他并不是br的简单多次重复,而是一个独立的指令:

Llvm.org  explanation

Syntax:

  switch <intty> <value>, label <defaultdest> <intty> <val>, label <dest> ... ]

 

Overview:

The 'switch' instruction is used to transfer control flow to one of several different places. It is generalization of the 'br' instruction, allowing branch to occur to one of many possible destinations.

Arguments:

The 'switch' instruction uses three parameters: an integer comparison value 'value', default 'label' destination, and an array of pairs of comparison value constants and 'label's. The table is not allowed to contain duplicate constant entries.

Semantics:

The switch instruction specifies table of values and destinations. When the 'switch' instruction is executed, this table is searched for the given value. If the value is found, control flow is transferred to the corresponding destination; otherwise, control flow is transferred to the default destination.

 

 

这就说得很明白了:switch是个独立的命令,它是“br”的扩展版,可以产生多个(不止两个)程序分支;说白了跟c语言的switch机制差不多;

这里需要注意的是,根据IR代码switch的各个分支不是运行一个就完事了的,而是自上而下顺序运行的,如果你的条件变量的值触发了第N个程序分支,那么运行完第N个程序分支后switch会继续运行N+1N+2N+3~~~~~~~~~----它是连成一串的:

 

 

sw.bb:                                            preds %entry

  store i32 1, i32* %b, align 4

  br label %sw.bb1

 

sw.bb1:                                           preds %entry, %sw.bb

  store i32 2, i32* %b, align 4

  br label %sw.bb2

 

sw.bb2:                                           preds %entry, %sw.bb1

  store i32 3, i32* %b, align 4

  br label %sw.epilog

 

sw.epilog:                                        preds %sw.bb2, %entry

  %1 load i32* %retval

  ret i32 %1

 

 

这就是为什么正常写c代码使用switch时必须合理使用break;关键字的原因了~~一旦这个概念没搞好,程序得出的结果往往都是错的,想当年我们c语言期末考试还考过这个知识点呢,吼吼;

 

 

 

 

 

众所周知,llvm起源自美国伊利诺伊大学香槟分校发起的一个开源计划,目的是发展出一款模块化的新兴开源编译器,使llvm拥有比现有编译器更强的优化能力是该项目负责人Chris LattnerVikram Adve非常看重的一项技术指标;llvm的主要赞助人和支持者苹果公司最看重的也是这一项;因为在苹果看来,如果能在程序编译优化方面取得突破,那么相当于一不用改良软件编程语法,二不用更新硬件架构,就能使得程序运行性能和速度取得提升,从而优化用户体验,这样的话简直是太划算了;当然现在看来这种构想还只是镜中花水中月,但是所有的伟大发明,最早都来自于狂野的幻想,我们程序员也没有理由不去主动了解llvm这种致力于超越gcc的编译环境,以期提高自己的专业素养,争取在未来的竞争中立于不败之地。

0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

       

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有