LCC编译器的源程序分析(41)赋值表达式的有向无环图

前面已经介绍怎么样把赋值表达式变换到树的中间表示,接着下来编译器要做的事情就是怎么样把树变换成有向无环图。也许你会问为什么要把树变换成有向无环图,而不是直接生成最终代码呢?其实,学习过数据结构就很清楚有向无环图的应用,编译器里就是利用有向无环图的特性来进行局部代码优化的,最主要的优化就是删除公共表达式。下面就来分析LCC从树到有向无环图的实现代码。
上面函数dcllocal里调用转换函数如下:
walk(root(asgn(p, e)), 0, 0);
从root函数里返回一棵赋值树,然后就把它传递给函数walk,在walk函数里就会调用一系列函数实现到DAG的转换。函数walk的代码如下:
#001 //
#002 void walk(Tree tp, int tlab, int flab)
#003 {
#004 //
#005 listnodes(tp, tlab, flab);
#006
#007 if (forest)
#008 {
#009 Node list = forest->link;
#010 forest->link = NULL;
#011 if (!IR->wants_dag && errcnt == 0)
#012 list = undag(list);
#013 code(Gen)->u.forest = list;
#014 forest = NULL;
#015 }
#016
#017 reset();
#018 deallocate(STMT);
#019 }
第5行就是调用函数listnodes来实现DAG构造。
第7行是判断是否有森林生成,如果生成就把代码块放到代码链表里。这些是在第9行到第14行里做的工作。
第17行复位所有变量。
第18行删除分配的内存。
大部份的工作都是在函数listnodes实现的,因此这个函数比较长,有420多行代码。现在先分析赋值部分相关的代码,后面当遇到时再去分析它。OK,先来回顾一下前面的例子:
int nTest1 = 1;
由上面这行代码就生成下面的树:
ASGN树:
左子树- INDIR树-ADDRL树
右子树-常量表达式树
listnodes函数再由上面的树生成DAG,因此listnodes函数先会遇到ASGN树节点,然后再遇到INDIR树、ADDRL树,最后就是常量表达式树。有了这条主线,就可以去分析函数listnodes的代码了。
#001 //
#002 Node listnodes(Tree tp, int tlab, int flab)
#003 {
#004 Node p = NULL, l, r;
#005 int op;
#006
#007 assert(tlab == 0 || flab == 0);
#008 if (tp == NULL)
#009 return NULL;
#010
#011 if (tp->node)
#012 return tp->node;
#013
#014 if (isarray(tp->type))
#015 op = tp->op + sizeop(voidptype->size);
#016 else
#017 op = tp->op + sizeop(tp->type->size);
#018
#019 switch (generic(tp->op))
#020 {
第2行里函数参数tp就是传入来的赋值树指针,tlab和flab是当存在条件选择时才出现,因此传下来是0。
第8行是当传入来的树是空树,就直接返回,这样才能实现递归调用本函数。
第11行是当树已经变换到DAG节点,就不需要再进行转换,直接返回DAG节点。
第14行是计算操作符的类型和数据类型大小。
第19行是根据树节点不同的类型进行分别处理。比如赋值、与树等等。

#021 case AND:

现在先分析到这里,下次再接着分析赋值树具体地变换到DAG的代码。

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License