函数调用图

函数调用图（call graph，也称为call multigraph）^[1][2]，属于控制流图^[3]，可以展示计算机程序中函数之间的关系。每一个节点是一个函数，每一个边(f, g)表示函数f调用函数g。若其中有出现互相调用的环，表示程序中可能有递归调用。

用Python程序产生的函数调用图

基本概念

函数调用图可以由动态程序分析产生（动态函数调用图），也可以由静态程序分析产生（静态函数调用图）^[4]。动态函数调用图是程序执行过程的记录，可能是性能分析工具所输出的。动态函数调用图可以准确的描述这次程序执行时,各函数之间的关系。但会遗漏这次没有执行到的代码。静态函数调用图则是设法表示所有可能执行情形下，所有函数之间的关系。准确的静态函数调用图是不可判定问题，因此静态函数调用图是多半只是近似情形。函数调用图上有所有函数之间的调用关系，但有可能其中有一些调用是永远不会执行到的。

函数调用图可以定义来呈现不同程度的准确度。更准确的函数调用图会更近似真正程序的行为，不过要计算的时间会比较长，要存储的资料也会比较多。最准确的函数调用图是完全“上下文相关”（context-sensitive），针对每一个函数，图中会对不同情形，不同调用堆栈下的调用，有不同的节点。全上下文相关的函数调用图称为调用上下文树（英语：calling context tree）。利用动态程序分析可以轻易的产生，不过会花许多的存储器。调用上下文树一般不会用静态程序分析产生，因为对大型程序会花许多时间。最不准确的函数调用图称为“上下文无关”（context-insensitive），针对每一个函数只会有一个节点。

若编程语言中有动态分派的特性（例如Java或C++）,要产生准确的静态程序分析会需要假名分析（英语：alias analysis）的结果^[5]。相对的，要得到准确的假名分析也需要函数调用图。许多静态分析系统可以同步产生这二份资料，解决这个看似无限循环的问题。

用途

函数调用图有几种不同的用途。其中一个简单的应用是找出没有被其他程序调用的子函数。函数调用图可以当做文件，有助于程序员的程序理解^[6]。函数调用图也是进一步分析的基础，例如追踪某一变量数值在各子函数中的变化，或是进行变更影响分析^[7]。函数调用图可以用来侦测异常的程序执行，或是侦测代码注入攻击^[8]。

示例的图

以下是用gprof（英语：gprof）自我分析得到的函数调用图

index    called     name                              |index    called     name
      72384/72384       sym_id_parse [54]             |       1508/1508        cg_dfn [15]
[3]   72384             match [3]                     |[13]   1508             pre_visit [13]
----------------------                                |----------------------
          4/9052        cg_tally [32]                 |       1508/1508        cg_assemble [38]
       3016/9052        hist_print [49]               |[14]   1508             propagate_time [14]
       6032/9052        propagate_flags [52]          |----------------------
[4]    9052             sym_lookup [4]                |          2             cg_dfn [15]
----------------------                                |       1507/1507        cg_assemble [38]
       5766/5766        core_create_function_syms [41]|[15]   1507+2           cg_dfn [15]
[5]    5766             core_sym_class [5]            |       1509/1509        is_numbered [9]
----------------------                                |       1508/1508        is_busy [11]
         24/1537        parse_spec [19]               |       1508/1508        pre_visit [13]
       1513/1537        core_create_function_syms [41]|       1508/1508        post_visit [12]
[6]    1537             sym_init [6]                  |          2             cg_dfn [15]
----------------------                                |----------------------
       1511/1511        core_create_function_syms [41]|       1505/1505        hist_print [49]
[7]    1511             get_src_info [7]              |[16]   1505             print_line [16]
----------------------                                |          2/9           print_name_only [25]
          2/1510        arc_add [31]                  |----------------------
       1508/1510        cg_assemble [38]              |       1430/1430        core_create_function_syms [41]
[8]    1510             arc_lookup [8]                |[17]   1430             source_file_lookup_path [17]
----------------------                                |----------------------
       1509/1509        cg_dfn [15]                   |         24/24          sym_id_parse [54]
[9]    1509             is_numbered [9]               |[18]     24             parse_id [18]
----------------------                                |         24/24          parse_spec [19]
       1508/1508        propagate_flags [52]          |----------------------
[10]   1508             inherit_flags [10]            |         24/24          parse_id [18]
----------------------                                |[19]     24             parse_spec [19]
       1508/1508        cg_dfn [15]                   |         24/1537        sym_init [6]
[11]   1508             is_busy [11]                  |----------------------
----------------------                                |         24/24          main [1210]
       1508/1508        cg_dfn [15]                   |[20]     24             sym_id_add [20]
[12]   1508             post_visit [12]               |

相关条目

• 相依性图（英语：Dependency graph）
• 功能树