Constructing call multigraphs using dependence graphs
Constructing call multigraphs using dependence graphs
复制标题
使用依赖图构建调用多重图
DOI：
10.1145/158511.158647
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Arun Lakhotia
中科院分区：
文献类型：
--
作者：
Arun Lakhotia
程序的调用多图是一个有向多图，它编码了过程之间可能的调用关系。这些图用于程序间程序优化[2,3,9,15]和软件系统的逆向工程[7,8]。对于不包含过程值变量（下文称为过程变量）的程序，可以通过对程序进行一次遍历，收集在每个调用点调用的过程来构造此图。当过程v，ari。允许使用这些变量的值进行Ables和间接调用，构造这样的图并不是那么简单。在最坏的情况下，调用站点上的过程变量v的值可能是对程序中任何过程的引用。对于程序间优化和理解程序，人们希望有更精确的解决方案。Shivers[18]雄辩地阐述了在Scheme和ML等高阶语言环境中精确构建调用图模拟（称为o}l阶控制流分析或OCFA）的重要性。精确的调用图可以实现数据流优化*在本文中，调用multigmph也被称为调用图。这项工作是由资助LEQSF (1991-92) eh -98从路易斯安那州的董事碗。
A call m.ultigraph’of a program is a directed Multigraph encoding the possible calling relations between procedures. These graphs are used in interprocedurd program optimization [2, 3, 9, 15] and for reverse engineering of softw~are systems [7, 8]. For programs that do not contain proCedul”e valued variables (referred to hencefollh as procedure variables) this graph can be constructed by a single pass over the program collecting the procedures called at each call site. When procedure v,ari.ables and indirect calls using values of such variables are allowed constructing such a graph is not so simple. In the worst case, the value of a procedure v,ariable at a call site may be a reference to any procedure in the program. For interprocedural optimizations and for understanding programs one would like to have more precise solutions. The importance of precisely constructing an analogue of call graph (referred to as the Ot}l order control flow analysis or OCFA) in the context of higher order languages such as Scheme and ML has been eloquently elaborated by Shivers [18]. A precise call graph enables data flow optimizations * In ths paper call multigmph is also refereed to as the call graph. Ths work was supported by the grant LEQSF (1991-92) ENH-98 from the Louisiana Bowl of Regents.