跳转到内容

死码删除

本页使用了标题或全文手工转换
维基百科,自由的百科全书

编译器原理中,死码消除(Dead code elimination)是一种编译最佳化技术,它的用途是移除对程式执行结果没有任何影响的程式码。移除这类的程式码有两种优点,不但可以减少程式的大小,还可以避免程式在执行中进行不相关的运算行为,减少它执行的时间。不会被执行到的程式码(unreachable code)以及只会影响到无关程式执行结果的变数(Dead Variables),都是死码英语dead code(Dead code)的范畴。

范例

下列的范例,以C语言写成:

 int foo(void)
 {
   int a = 24;
   int b = 25; /* 賦值給一個無用的變數*/
   int c;
   c = a << 2;
   return c;
   b = 24; /* 不會被執行到的程式碼*/
   return 0;
 }

分析上述程式对于数值的使用,将会发现b的数值在第一次被赋值之后,就不再使用,而且b是在foo函数内宣告,无法在函数外面使用,所以变数b无用的,最佳化的过程可以回收他所使用的空间,并删除他的初始化。

当第一个return被执行,则代表函数已经结束,之后变数b的赋值行为则不会被执行,所以赋值行为是可以被删除的。如果程式有更复杂的控制流程,例如在第一个return之后加上一个标签,使得程式中任和一个地方都可以用goto来执行到这个程式段,那么变数b的赋值行为将有可能被执行。

尽管一些计算行为被包装成函数,他们的数值也无法被函数外所存取,但仍然还是有些函数仅会回传一个固定的数值,这或许可以将该数值取代所有函数的呼叫。(这个简化的过程被称之为常数折叠

更进阶的编译器则会有些选项可以启动死码删除的功能,而有些则是可以选择不同等级的死码删除,比较低阶等级的死码删除仅会移除不会被执行到的指令,而较高阶的可能不会保留无用变数的空间,其他高阶等级的做法可能会判断哪些指令及函数没有任何用途,并且删除他们。

死码删除最普遍的做法,是透过预处理器来判断程式码是否需要被编译,如下列这个范例:

 int main(void) {
   int a = 5;
   int b = 6;
   int c;
   c = a * (b >> 1);
   if (0) {   /* DEBUG */
     printf("%d\n", c);
   }
   return c;
 }

由于0将永远被视为False,所以if判断式内的程式将永远不会被执行,死码删除将会把它移除,这个技术在调试上相当常见,我们可以透过一个数值来决定程式段是否该被编译,使用死码删除的最佳化过程,将会使用预处理器来进行相同的工作。

实作中,有些在最佳化过程中找到的死码,是被其他最佳化技术产生,举例来说,典型强度折减的技术,将会在程式码内插入新的运算以取代昂贵的运算行为,而被取代的程式码就成了死码[1],随后,死码删除会移除那些计算,以完成这个效果(没有复杂的强度折减演算法)。

从历史上来看,死码删除使用来自资料流分析的资讯[2],Cytron et al在原始文章中发布了一个基于静态单赋值形式的演算法[3],Shillingsburg改进了这个演算法,并开发了一个演算法来移除无用的控制流(Control-flow)[4]

动态死码删除

死码通常被视为无条件的(unconditionally),所以我们可以在编译时期透过死码删除来移除这些无用的程式码。

然而,在实作上,只有在特定的情形才会标注一个程式码区段是无用的,或是不会执行到的,这可能无法在编译时期所得知。例如在不同的执行环境有不同的结果(举例来说,目标环境可能会有不同的作业系统版本,或是不同的驱动程式及可用服务的组合),可能会在程式码内要求不同特例的集合,同时在这些案例下就变成有条件的死码。然而,软体(例如驱动程式、或是常驻服务)可能会根据使用者的设定,而配置或排除特定的功能,使得在一些特定的情境,会变成部分无用的死码。模组化软体实作方式,是在需要时才读取动态函式库,在多数的案例中,不可能仅从特定的函式库读取相关的程式,它仍然会包含一些程式片段,在特定的环境下是可被视为死码,但是这在编译时期是无法被排除的。

动态死码删除(dynamic dead code elimination)被使用在执行时动态侦测,可辨识及解析相依性,用以移除有条件的死码,在执行时期重新组合保留的程式码。

多数的电脑语言、编译器、作业系统不提供,或是仅比动态读取函式库及后连结(late linking)提供多一点点的功能,能使用动态死码删除的软体是相当稀少的。

参考文献

Partial dead code elimination using slicing transformations Found in: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation (PLDI '97) By Rastislav Bodík, Rajiv Gupta Issue Date:June 1997 pp. 682–694

  1. ^ Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
  2. ^ Ken Kennedy. A Survey of Data-flow Analysis Techniques. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
  3. ^ Ron Cytron, Jeanne Ferrante, Barry Rosen, and Ken Zadeck. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4), 1991.
  4. ^ Keith D. Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann, 2003, pages 498ff.

参考书籍

  • Grune, Dick; Bal, Henri E.; Jacobs, Ceriel J.H.; Langendoen, Koen G. Modern Compiler Design. John Wiley & Sons, Inc. 2000. ISBN 0-471-97697-0. 

外部链接