GCC : Control Flow Graph

趁著記憶新鮮的時候先來紀錄一下

每個 Compiler 裡面的重要基礎設施之一就是 Control Flow Graph, 也就是 Basic Block 及其 Edge, 而這邊大概介紹一下 GCC 內部的資料結構及走訪方式, 主要參考來源是 GCC Source Code 及 GCC Internal.
GCC 的 Basic Block 在實作上要比較注意的一點是 GIMPLE 及 RTL 都會使用同樣得資料結構來表示, 但 RTL 的部份照慣例一樣是 expand 完後才會有, 而且同一個時間點只會是 GIMPLE 或 RTL

詳細的程式碼則可到 gcc/basic-block.h 裡面撈

1. Basic Block

在整個 CFG 中有兩個特別的 Block 一個是 ENTRY_BLOCK, 一個是 EXIT_BLOCK 他們分別可由 ENTRY_BLOCK_PTR EXIT_BLOCK_PTR 取得

在 basic_block 這個 struct 中有 next_bb 及 prev_bb 兩個欄位, 但沒事請直接別碰這兩個傢伙, 要走訪所有的 Basic Block 或要找兒子/父親的話下面有一些範例程式碼

走訪所有 Basic Block

basic_block bb;

FOR_EACH_BB (bb) {
  /* do something */
}

要注意的一點是有個東西叫 FOR_ALL_BB, 差別在於他會走到 ENTRY_BLOCK 跟 EXIT_BLOCK 而 FOR_EACH_BB 不會

basic_block bb;

FOR_ALL_BB (bb) {
  /* do something */
}

找父親

basic_block bb;
edge e;
edge_iterator ei;
FOR_EACH_EDGE(e, ei, bb->preds){
  /*
   * get src by `e->src`
   * get dest by `e->dest`
   */
}

找兒子

basic_block bb;
edge e;
edge_iterator ei;
FOR_EACH_EDGE(e, ei, bb->succs){
  /*
   * get src by `e->src`
   * get dest by `e->dest`
   */
}

走訪該 BB 的所有 RTL INSN

rtx insn;
basic_block bb;
FOR_BB_INSNS(bb, insn) {
  /* do something with insn */
}

走訪該 BB 的所有 GIMPLE stmt 及 PHI node

basic_block bb;
gimple_stmt_iterator si;

for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) {
  gimple phi = gsi_stmt (si);
  print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
}
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) {
  gimple stmt = gsi_stmt (si);
  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}

2. Edges

Edge flag 如下
以下是從 basic-block.h 那邊抽出來的, 跟 GCC Internal 描述的是不太一樣的東西

1. EDGE_FALLTHRU : 這個 edge 不會產生額外的 jump, 代表 src/dest 之後一定會放在一起
2. EDGE_ABNORMAL : Indirect jump 或著是 Exception Handling 的 Edge
3. EDGE_ABNORMAL_CALL : 呼叫一個可能會發生 Exception 的函數或著是 No return 的函數(例如呼叫 exit 或 abort)
4. EDGE_EH : 處理 Exception Handling 的 Edge
5. EDGE_FAKE : 他是一個不是 edge 的 edge! 拿來給 profiling 時用的
6. EDGE_DFS_BACK : 是一個 back edge
7. EDGE_CAN_FALLTHRU : 可以弄成 EDGE_FALLTHRU
8. EDGE_IRREDUCIBLE_LOOP : irreducible loop 裡面的 edge
9. EDGE_SIBCALL : 摳到 sibcall
10. EDGE_LOOP_EXIT : 迴圈的終點
11. EDGE_TRUE_VALUE : 當 Conditional Branch 的 Condition 為 True 時的目的地
12. EDGE_FALSE_VALUE : 當 Conditional Branch 的 Condition 為 False 時的目的地
13. EDGE_EXECUTABLE : 作 SSA-CCP 最佳化的時候用的, 其他時候請不要亂用
14. EDGE_CROSSING : Cold code 與 Hot code 交界點
15. EDGE_PRESERVE : 這個 Edge 不准砍!!!
16. EDGE_ALL_FLAGS : 代表所有 flag
17. EDGE_COMPLEX : EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE, 很複雜就對了!