回路搜索算法

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

[资源] 中科院开源协会的GCC等GNU软件镜像站点上线

中科院开源协会最近上线了一个开源软件镜像站点, 提供包括GCC在内的众多GNU软件源代码的镜像. 服务器部署在中国科技网上, 国内访问的速度还可以, 可以尝试下.

镜像地址: http://mirrors.opencas.cn/gnu/gcc/

中科院开源协会地址: http://www.opencas.org/

看了一下, 还有一个有吸引力的地方是提供了Android相关SDK的下载. 这点对于希望接触Android开发的爱好者帮助很大 :-)

像使用gdb一样,使用perl debugger进行调试

调试perl脚本,通过-d选项来启动perl debugger,例如:

$ perl -d ./test.pl

这里我们先花点时间,把perl的调试环境配置的好使些。

1、增加对Readline的支持

缺省的perl调试器不支持Readline功能,所以,如果你想按up键往前翻历史命令的话,会出现如下乱码:

^[[A^[[A^[[A^[[A

需要安装模块: Term::ReadKey,Term::ReadLine,Term::ReadLine::Perl(其中后两个我没搞清楚是否重复,反正全装上了)
安装模块的方法,参见 http://www.cpan.org/modules/INSTALL.html

2、使用.perldb文件

这个类似于gdb的.gdbinit,可以用来在调试器启动的时候,做些配置工作,预先执行一些命令。需要注意的是,需要将该文件的权限设定为只有创建者可写,即:

-rw-r--r--

否则,perl debugger出于安全的考虑,不会去加载这个文件:

perldb: Must not source insecure rcfile /home/xmj/.perldb.
        You or the superuser must be the owner, and it must not
        be writable by anyone but its owner.

3、打印数组,哈希变量

可以使用Data::Dumper模块,来打印数组,哈希变量的内容,在.perldb中加入如下配置:

$DB::alias{'dump'}  = 's/^dump (.*)/p Dumper($1)/';
sub afterinit {
  push @DB::typeahead, "use Data::Dumper qw(Dumper)";
}

这样,就可以在perldb中,直接使用dump命令来打印:

  DB<10> dump %Options
$VAR1 = 'EnableCheckers';
$VAR2 = [];
$VAR3 = 'DisableCheckers';
$VAR4 = [];

4、保存历史命令

在.perldb中加入如下配置:

&parse_options("HistFile=$ENV{HOME}/.perldb_hist");

下次进入perl debugger的时候,还可以向上翻出早前的历史命令。

———————-
参考链接:
Debugging Perl scripts, http://perlmaven.com/debugging-perl-scripts
Perl Debugger Tutorial: 10 Easy Steps to Debug Perl Program,http://www.thegeekstuff.com/2010/05/perl-debugger/
How can I print the contents of a hash in Perl? http://stackoverflow.com/questions/1162245/how-can-i-print-the-contents-of-a-hash-in-perl
Can the Perl debugger save the ReadLine history to a file? http://stackoverflow.com/questions/6433241/can-the-perl-debugger-save-the-readline-history-to-a-file
How to install CPAN modules,http://www.cpan.org/modules/INSTALL.html
perldebug在线文档:执行命令perldoc perldebug进行查看

Linux下那么多Tracer如何选择

如果你想要在linux下调调kernel, 抓抓程序的性能, 那么首先想到的可能是 OProfile 和 Linux Perf. 但是显然, 开源有一个非常显著地你无法回避的特点, 就是你会有太多的选择: perf, oprofile, systemtap, dtrace4linux, lttng, kgtp, ktap, sysdig, ftrace, eBPF. 是不是已经眼花了? 那么你不能错过这篇文章:

http://www.brendangregg.com/blog/2015-07-08/choosing-a-linux-tracer.html

介绍了目前常用的各类工具:

  1. ftrace
  2. perf_events
  3. eBPF
  4. SystemTap
  5. LTTng
  6. ktap
  7. dtrace4linux
  8. OL DTrace
  9. sysdig

作者非常细心的列出了大量的工具原理及使用教程, 保证会花掉你大把的晚上才能看完.

其实我日常使用的只有 perf, 只能算是 ‘most people’ :)

‘#include_next’ 的用途

最近在阅读开源项目代码的时候看到一个很少见的预处理命令:

#include_next

查询了一下, 并不是标准中的一部分, 属于 GNU 扩展, 使用的场合也比较少, 在某些新旧代码共存时或许会比较常见.

https://gcc.gnu.org/onlinedocs/cpp/Wrapper-Headers.html

2.7 Wrapper Headers

Sometimes it is necessary to adjust the contents of a system-provided header file without editing it directly. GCC’s fixincludes operation does this, for example. One way to do that would be to create a new header file with the same name and insert it in the search path before the original header. That works fine as long as you’re willing to replace the old header entirely. But what if you want to refer to the old header from the new one?

You cannot simply include the old header with ‘#include’. That will start from the beginning, and find your new header again. If your header is not protected from multiple inclusion (see Once-Only Headers), it will recurse infinitely and cause a fatal error.

You could include the old header with an absolute pathname:

#include “/usr/include/old-header.h”

This works, but is not clean; should the system headers ever move, you would have to edit the new headers to match.

There is no way to solve this problem within the C standard, but you can use the GNU extension ‘#include_next’. It means, “Include the next file with this name”. This directive works like ‘#include’ except in searching for the specified file: it starts searching the list of header file directories after the directory in which the current file was found.