为td文件生成tags

LLVM的TableGen可以用来为td文件生成tags,方便在vim中查看。该功能的svn信息如下:

------------------------------------------------------------------------
r177682 | silvas | 2013-03-22 07:40:38 +0800 (Fri, 22 Mar 2013) | 18 lines
Changed paths:
   M /llvm/trunk/utils/TableGen/CMakeLists.txt
   A /llvm/trunk/utils/TableGen/CTagsEmitter.cpp
   M /llvm/trunk/utils/TableGen/TableGen.cpp
   M /llvm/trunk/utils/TableGen/TableGenBackends.h
   A /llvm/trunk/utils/TableGen/tdtags

Add TableGen ctags(1) emitter and helper script.

To use this in conjunction with exuberant ctags to generate a single
combined tags file, run tblgen first and then
  $ ctags --append [...]

Since some identifiers have corresponding definitions in C++ code,
it can be useful (if using vim) to also use cscope, and
  :set cscopetagorder=1
so that
  :tag X
will preferentially select the tablegen symbol, while
  :cscope find g X
will always find the C++ symbol.

Patch by Kevin Schoedel!

(a couple small formatting changes courtesy of clang-format)
------------------------------------------------------------------------

使用方法如下:

xmj@xmj-OptiPlex-9020:~/project/llvm-trunk$ bash utils/TableGen/tdtags -q -x all

生成的tags文件:

xmj@xmj-OptiPlex-9020:~/project/llvm-trunk$ find ./ -name tags
./unittests/Option/tags
./lib/IR/tags
./lib/LibDriver/tags
./lib/Target/AVR/tags
./lib/Target/XCore/tags
./lib/Target/WebAssembly/tags
./lib/Target/BPF/tags
./lib/Target/Sparc/tags
./lib/Target/Mips/tags
./lib/Target/NVPTX/tags
./lib/Target/SystemZ/tags
./lib/Target/PowerPC/tags
./lib/Target/Lanai/tags
./lib/Target/MSP430/tags
./lib/Target/X86/tags
./lib/Target/AArch64/tags
./lib/Target/Hexagon/tags
./lib/Target/ARM/tags
./lib/Target/AMDGPU/tags
./test/TableGen/tags
./include/llvm/IR/tags
./include/llvm/Option/tags
./include/llvm/Target/tags
./include/llvm/CodeGen/tags
./tools/clang/tags
./tools/clang/lib/StaticAnalyzer/Checkers/tags
./tools/clang/test/TableGen/tags
./tools/clang/include/clang/AST/tags
./tools/clang/include/clang/Driver/tags
./tools/clang/include/clang/Basic/tags
./tools/clang/include/clang/StaticAnalyzer/Checkers/tags

回路搜索算法

Gcc和LLVM中的软流水优化,都是基于Swing Modulo Scheduling算法(翻译成摆动模调度?)实现的,参见[1]。其中,需要在依赖图(dependency graph)上搜索所有的简单回路(elementary circuits)。

LLVM中的软流水代码里,提到了“Identify all the elementary circuits in the dependence graph using Johnson’s circuit algorithm.”,这个算法源自论文[2]。

为了更好的理解回路搜索算法,我也基于论文[2]做个实现,放在了github上,参见[3]。

[1] Josep Llosa, Antonio Gonzalez, Eduard Ayguade, and Mateo Valero. Swing Modulo Scheduling: A Lifetime Sensitive Approach. In Pact96 , pages 80-87, October 1996 (Boston – Massachusetts – USA).
[2] Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing, 1975.
[3] https://github.com/hellogcc/circuit-finding-algorithm

clang小技巧:加快编译速度

编译整个llvm会花费很长的时间,如果你只关心clang,则每次修改完代码之后需要make的时候,可以使用

make ONLY_TOOLS="clang"

只编译clang,从而大大减少编译时间。

进一步,还可以使用

make ONLY_TOOLS="clang" BUILD_CLANG_ONLY=YES

只编译器clang本身,不编译clang的unit test。

小技巧:追溯历史开发信息

在gcc中,如果想查看以往的代码变动信息,可以查看相应源码目录下的ChangeLog文件。ChangeLog有很好的格式要求和内容规范,并且也要经过review。这虽然对于Patch提交者来来说显得有些繁琐,但当你需要查看历史开发信息的时候,就充分感受到了它的重要性了。

在LLVM中,没有ChangeLog文件,LLVM的开发者认为查看svn log就足够了。但是,日志信息的格式和内容比较随意,而且,一般还需要手动导出到文件中进行查看。使用svn命令时,建议使用svn log -v命令,这个-v选项,可以打印出相关的文件变动信息,可以帮助你更好的追溯代码变动情况。

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也无能为力。