Side effect analysis in LLVM

简单介绍下LLVM中的副作用分析。关于LLVM的别名分析基础设施,可以参考:http://llvm.org/docs/AliasAnalysis.html

何为副作用分析,简单来讲,就是分析执行一条语句(包括函数调用)是否会对内存对象有读写操作(Mod/Ref)。书上(包括龙书等)讲的大多都是fortran时代的算法,而对于c语言这样的,由于引入了指针,使得情况变得复杂了。所以,后来的论文大多集中在别名分析或指向分析领域。副作用分析可以看作是别名分析的客户程序,指针分析搞定,副作用分析就迎刃而解。

LLVM中,在2.6以及之前,是有Andersen别名分析的实现的,后来因为无人维护,有许多问题就不再支持。在单独的一个项目poolalloc中,有对DSA(data structure analysis)的实现,以及基于DSA的Steensgaard别名分析的实现,这部分正是Chris Lattner的博士论文所讲的内容。然而真正属于LLVM内核代码中的,主要也就是basicaa和globalsmodref-aa,这些都是比较简单但有效的实现。gcc也是如此,产品级的编译器,会综合考虑精度和开销的问题,并对健壮性有更高的要求。通常,我们说副作用分析是以别名分析为基础的,但是globalsmodref-aa恰恰反过来,它是先分析globals的mod/ref信息,然后推导别名信息。

LLVM中,对于普通的语句(非函数调用),其副作用可以直接通过别名分析的结果推导出来,例如:

AliasAnalysis::ModRefResult
AliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) {
// Be conservative in the face of volatile/atomic.
if (!L->isUnordered())
return ModRef;

// If the load address doesn't alias the given address, it doesn't read
// or write the specified memory.
if (!alias(getLocation(L), Loc))
return NoModRef;

// Otherwise, a load just reads.
return Ref;
}

对于函数调用的情况,需要额外处理。所以对于一个新的继承自AliasAnalysis类的别名分析实现,通常会将其作为接口单独实现。

LLVM中全局变量,函数都是指针类型的,其指向对应的内存分配。对于c语言“a = b + c;”,我们可能会说这条语句引用了b和c,修改了a。但,其翻译到LLVM中间代码的时候,已经是多条语句,包含了load,add,store。所以,对于LLVM的中间语言,add是不涉及到副作用的,只有load和store这样的对内存有操作的,才具有副作用,正如代码所示,


ModRefResult getModRefInfo(const Instruction *I,
const Location &Loc) {
switch (I->getOpcode()) {
case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc);
case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc);
case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc);
case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc);
case Instruction::AtomicCmpXchg:
return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
case Instruction::AtomicRMW:
return getModRefInfo((const AtomicRMWInst*)I, Loc);
case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc);
case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
default: return NoModRef;
}
}

副作用分析的客户程序又是哪些呢?这包括:-adce(Aggressive Dead Code Elimination),-licm(Loop Invariant Code Motion),-gvn(global value numbering)等。看起来,如果副作用分析做好的话,还是会有性能提升的。

副作用分析的效果又如何呢?实际情况中,往往会有函数调用了外部函数(比如c库),为了正确性,必须保守的认为其对所有的内存对象都有副作用。这就导致整个调用链上的函数都将保守处理,以至于分析精度严重受损,效果也会大打折扣。所以LTO很关键,但是实际情况中,对于c库之类的,我们还是用的二进制包,LTO也无能为力。

分享几篇关于gcc和gdb的文章

海法Linux俱乐部是一群在以色列海法地区生活的Linux工程师定期组织的,分享在Linux下开发程序经验的聚会。网站是http://www.haifux.org/。其中有很多topic,涉及的范围很广,感兴趣的同学可以登陆这个网站看一下。我把其中和gcc和gdb相关的文章选出来,分享在下面:
gdb – customize it the way you want
Advanced GDB
Compiling Effectively for Cell with GCC
GCC Profile Guided Optimization

Clang之libclang

写在前面的话:之前在翻译Clang官方文档(http://www.hellogcc.org/?p=33721)的时候,已经涉及到了libclang,并且对libclang有了一个简单的介绍,特别是关于在什么时候去使用libclang。在这里,侧重谈下自己对libclang的理解和使用的感受。

正文:

现在的Clang,不仅仅是一个编译器前端,同时也可以作为一个库使用。作为一个库使用的时候,可以用它去分析C/C++/ObjectC语言代码,可以 分析源码得到AST,也可以获取已经分析好的AST,也可以遍历AST,还可以获取AST中基本元素的物理源码位置。这就是libclang。

libclang提供了一系列的C语言的接口,但是这些接口并不能完全提供存储在Clang C++ AST中的所有信息,只能提供部分基本信息,但是这些基本信息已经可以满足一般情况下的使用。主要目的是为了稳定,并且可以支持开发工具的基本功能。 (clang/include/clang-c/Index.h中的注释原文如下: This C interface to Clang will never provide all of the information representation stored in Clang’s C++ AST, nor should it: the intent is to maintain an API that is relatively stable from one release to the next, providing only the basic functionality needed to support development tools.)

与此同时,libclang支持和python绑定使用,也就是说你可以是用python去调用libclang。clang在 clang/bindings/python/这个目录下面提供了绑定所需要的文件。目前这个目录下面除了README之外还有三个目 录:clang,examples,tests。其中clang目录下面的文件是绑定所需要的,examples目录下面是绑定后测试用的两个小例子。 test目录下面应该是测试需要的一些文件(该目录下面文件目前还没有认真分析)。只需要把绑定文件放到python的库文件下面(包含clang文件 夹),然后确保系统安装clang到系统目录,之后就可以运行例子了。
libclang带来的优点很明显,可以在很多不同的环境下面轻松的用上libclang,只是作为一个提供了parser功能的库,非常方便快捷 的嵌入自己的工具中,避免了大量的重复工作。同时也不用去分析clang内部的代码,不需要熟悉内部大量的AST相关的代码,就可以使用,这可以节省大量 的时间。当然,想深挖clang的代码的同学,也可以把这里当作一个突破口。

附录(一个同主题的非常好的英文博客,该内容包含了如何去具体实现python调用libclang):

http://eli.thegreenplace.net/2011/07/03/parsing-c-in-python-with-clang/

Solaris搭建64位C语言开发环境

刚来公司时,公司的C程序还是32位的。后来我阅读了一些资料,觉得64位的程序才是真正的趋势,所以就开始尝试着开发64位的程序。这篇文章介绍如何在Solaris下搭建64位C语言开发环境,希望给需要的朋友一点帮助。

(1)gcc

Solaris的/usr/sfw/bin/gcc可以用来编译64位C程序,但是需要加-m64编译选项,否则默认编译出来的是32位程序。此外也可以从gcc的官网下载gcc源代码,自行编译安装,但是要注意编译出来的gcc需要是64位的。

(2)gdb

调试64位C程序需要64位的gdb,gdb的安装步骤如下(以7.6版本为例):

1)gunzip gdb-7.6.tar.gz
2)tar xvf gdb-7.6.tar
3)export CC=”/usr/sfw/bin/gcc -m64″
4)mkdir build_gdb
5)cd build_gdb
6)../gdb-7.6/configure –prefix=“/…/…(a folder path)”
7)make
8)make install

需要注意以下两点:

a)Solaris下的tar程序不支持”-z”选项,所以只能先调用gunzip,再调用tar,不能一步搞定:tar -xzf gdb-7.6.tar.gz。

b)目前gdb的最新版本是7.7,在Solaris下编译会有错误。解决办法也很简单,可以参考这篇文章

(3)参考资料

个人认为Oracle的这本《Solaris 64-bit Developer’s Guide》,是在Solaris下开发64位C程序最好的资料。每一位C语言开发者都应该看一下,相信都能受益匪浅。