?使用 C++ 風格的模式匹配和重寫來優化轉置運算
?使用 DRR 優化 reshape 運算
?
???????? 創建一種貼近輸入語言的語義表示的方言,可以在 MLIR 中分析、變換和優化,這些過程中需要用到高級語言的信息,而且通常是在語言的 AST 上執行的這些過程。
?例如,為了執行template 實例化,在clang 程序中有一個相當厚實的機制。
?
? ? ? ? 我們將編譯器變換分為兩大類:局部的和全局的。在本章中,我們聚焦怎么利用Toy Dialect 和它的高層次語義來執行局部模式匹配變換,這在 LLVM 中是比較難實現的。
?為此,我們使用了 MLIR的 Generic DAG Rewriter。
?
? ? ? ? 這里有兩個方法可以用于實現模式匹配變換:1,命令式的,C++模式匹配和重寫,2,生命式的,基于規則的模式匹配和重寫,這是使用 表格驅動的 Declarative Rewrite Rules(DRR)。
?注意,使用DRR的話,要求 operations 是使用 ODS 定義的,如第2章中所述。
?
使用 C++ 風格的模式匹配和重寫來優化轉置運算
? ? ? ? 讓我們先一起研究一個簡單的模式,并且嘗試去消除一個由兩個可以抵消的轉置組成的序列:transpose(transpose(X)) -> X。這里是對應的 Toy 示例:
?
def transpose_transpose(x) {return transpose(transpose(x));
}
? 它對應于如下的 Toy IR:
toy.func @transpose_transpose(%arg0: tensor<*xf64>) -> tensor<*xf64> {%0 = toy.transpose(%arg0 : tensor<*xf64>) to tensor<*xf64>%1 = toy.transpose(%0 : tensor<*xf64>) to tensor<*xf64>toy.return %1 : tensor<*xf64>
}
這個變換的好示例,在Toy IR 中做匹配非常容易,但是,在 LLVM IR 中解決這個問題非常困難。例如,當前的 Clang 無法優化掉臨時數組,并且單純的轉置的計算,表示為如下這樣的循環:
#define N 100
#define M 100void sink(void *);
void double_transpose(int A[N][M]) {int B[M][N];for(int i = 0; i < N; ++i) {for(int j = 0; j < M; ++j) {B[j][i] = A[i][j];}}for(int i = 0; i < N; ++i) {for(int j = 0; j < M; ++j) {A[i][j] = B[j][i];}}sink(A);
}
? ? ? ? 對于一個簡單實現重寫的 C++ 方法,涉及到在 IR 中匹配一個類樹的模式,并且用一組不同的 operations 集合來替代它,我們可以通過實現一個 RewritePattern來插入到 MLIR Canonicalizer 中。
?
?
未完待續。。。