函式呼叫圖（call graph，也稱為call multigraph）[1][2]，屬於控制流圖[3]，可以展示電腦程式中函式之間的關係。每一個節點是一個函式，每一個邊(f, g)表示函式f呼叫函式g。若其中有出現互相呼叫的環，表示程式中可能有遞迴呼叫。
 | 此條目可參照英語維基百科相應條目來擴充。 |
基本概念
函式呼叫圖可以由動態程式分析產生（動態函式呼叫圖），也可以由靜態程式分析產生（靜態函式呼叫圖）[4]。動態函式呼叫圖是程式執行過程的記錄，可能是效能分析工具所輸出的。動態函式呼叫圖可以準確的描述這次程式執行時,各函式之間的關係。但會遺漏這次沒有執行到的程式碼。靜態函式呼叫圖則是設法表示所有可能執行情形下，所有函式之間的關係。準確的靜態函式呼叫圖是不可判定問題，因此靜態函式呼叫圖是多半只是近似情形。函式呼叫圖上有所有函式之間的呼叫關係，但有可能其中有一些呼叫是永遠不會執行到的。
函式呼叫圖可以定義來呈現不同程度的準確度。更準確的函式呼叫圖會更近似真正程式的行為，不過要計算的時間會比較長，要儲存的資料也會比較多。最準確的函式呼叫圖是完全「上下文相關」（context-sensitive），針對每一個函式，圖中會對不同情形，不同呼叫堆疊下的呼叫，有不同的節點。全上下文相關的函式呼叫圖稱為呼叫上下文樹。利用動態程式分析可以輕易的產生，不過會花許多的記憶體。呼叫上下文樹一般不會用靜態程式分析產生，因為對大型程式會花許多時間。最不準確的函式呼叫圖稱為「上下文無關」（context-insensitive），針對每一個函式只會有一個節點。
若程式語言中有動態分派的特性（例如Java或C++）,要產生準確的靜態程式分析會需要假名分析的結果[5]。相對的，要得到準確的假名分析也需要函式呼叫圖。許多靜態分析系統可以同步產生這二份資料，解決這個看似無限迴圈的問題。
用途
函式呼叫圖有幾種不同的用途。其中一個簡單的應用是找出沒有被其他程式呼叫的子函式。函式呼叫圖可以當做檔案，有助於程式設計師的程式理解[6]。函式呼叫圖也是進一步分析的基礎，例如追蹤某一變數數值在各子函式中的變化，或是進行變更影響分析[7]。函式呼叫圖可以用來偵測異常的程式執行，或是偵測代碼注入攻擊[8]。
範例的圖
以下是用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] |
相關條目
- 相依性圖
- 功能樹
參考資料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
