定義
所謂基本塊,是指程式—順序執行的語句序列,其中只有一個人口和一個出口,入口就是其中的第—個語句,出口就是其中的最後一個語句。對一個基本塊來說,執行時只從其入口進入,從其出口退出。具體而言:
1. 只有一個入口,表示程式中不會有其它任何地方能通過jump跳轉類指令進入到此基本塊中。
2. 只有一個出口,表示程式只有最後一條指令能導致進入到其它基本塊去執行。
所以,基本塊的一個典型特點是:只要基本塊中第一條指令被執行了,那么基本塊內所有執行都會按照順序僅執行一次。
基本塊可以用原始碼、彙編、指令等表示。
基本塊的劃分
尋找入口語句1、程式的第一條語句
2、轉移語句的目標語句
3、緊跟在條件轉移語句後面的語句
·劃分基本塊的算法:
1、求出所有入口語句
2、一個入口語句對應一個基本塊,口語句對應的基本塊方法是:該基本塊由該入口語句到下一入口語句(不含下一入口語句),或到一轉移語句(包括該轉移語句),或到一停語句(包括該停語句)之間的代碼序列組成
3、凡未被納入某一基本塊的語句,都是程式中控制流程無法到達的語句,可以刪除
GCC中基本塊的表示
在GCC中,基本塊使用basic_block數據類型來表示。結構體basic_block的兩個指針成員是指針next_bb和prev_bb,用來構造和內在的指令流順序相同的基本塊雙向鍊表。基本塊的連結由操作CFG的API來更新。宏FOR_EACH_BB可以用來按照lexicographical順序來訪問所有基本塊。也可以使用walk_dominator_tree,來進行dominator遍歷。給出兩個基本塊A和B,塊A支配(dominate)塊B,如果A總是在B之前被執行。
數組BASIC_BLOCK按照未指定的順序包含了所有的基本塊。每一個basic_block結構體都有一個域,包含了一個唯一的整數標識符index,其為該塊在BASIC_BLOCK數組中的索引。函式中基本塊的總數為n_basic_blocks。由於過程可以重排,創建,複製和銷毀基本塊,所以基本塊的索引和總數在編譯過程中都可能改變。任何塊的索引都不應該比last_basic_block的大。
一些特定的基本塊用來表示一個函式的可能的入口和出口。這些塊被稱作ENTRY_BLOCK_PRT和EXIT_BLOCK_PTR。這些塊不包含任何代碼,並且不是BASIC_BLOCK數組的成員。因此它們被賦予了唯一的負數索引。
每個basic_block還包含了指向基本塊中的第一個指令(head)和最後一條指令(tail),或者指令流的結尾。實際上,由於basic_block數據類型在GCC的兩個主要中間表示(tree和RTL)中都被用來表示塊,因此具有針對這兩種表示的指向基本塊的頭和尾的指針。
對於RTL,這些指針是rtx頭和尾。在RTL函式表示中,頭指針總是指向NOTE_INSN_BASIC_BLOCK或者CODE_LABEL。在RTL函式表示中,指令流不僅包含“真正”的指令,而且還有註解。任何移動或者複製基本塊的函式都需要注意更新這些註解。許多這些註解都期望指令流由線性區域組成,這使得難以更新。NOTE_INSN_BASIC_BLOCK註解是唯一類型的,可以出現在基本塊內包含的指令流中。一個基本塊的指令流總是跟隨一個NOTE_INSN_BASIC_BLOCK,但是塊註解之前可以有0個或多個CODE_LABEL節點。基本塊結束於控制流指令,或者最後一條指令後面跟隨CODE_LABEL或者NOTE_INSN_BASIC_BLOCK。CODE_LABEL不能出現在基本塊中的指令流里。
除了註解之外,跳轉表向量還被表示為insn流中的“偽指令”。這些向量從不出現在基本塊中,並且應該總是放在跳轉指令引用它們的表後面。在移除table-jump之後,通常很難消除計算地址和引用向量的代碼,所以對這些向量的清除工作被推遲到活躍分析之後。這樣跳轉表向量可能會在insn流中出現未被引用,並且無用的情況。在任何邊成為fall-thru之前,關於現存的構架,需要調用can_fallthru函式來檢測。
對於樹的表示,基本塊的頭和尾由stmt_list域指向,但是,決不要直接引用這些特定的樹。相反的,在樹級別上,使用抽象容器和疊代器來訪問基本塊中的語句和表達式。這些疊代器被稱作塊語句疊代器(BSI)。可以在各種tree-*檔案中使用grep查找^bsi。下面的摘抄可以很好的列印使用GIMPLE表示的程式的所有語句。
basic_block bb;
FOR_EACH_BB (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);
}
}