解決指令下沉阻擋商餘合併之最佳化演算法改良;An Algorithm to Prevent Division-Modulo Combine from Being Blocked by Instruction Sink

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/89724

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/89724

Title:	解決指令下沉阻擋商餘合併之最佳化演算法改良;An Algorithm to Prevent Division-Modulo Combine from Being Blocked by Instruction Sink
Authors:	林庭葦;Lin, Ting-Wei
Contributors:	資訊工程學系
Keywords:	編譯器;程式碼最佳化;相序問題;程式碼移動;LLVM;機器相依最佳化;機器不相依最佳化;compiler;code optimization;phase-ordering;code motion;LLVM;machine-dependent optimization;machine-independent optimization
Date:	2022-07-02
Issue Date:	2022-10-04 11:57:25 (UTC+8)
Publisher:	國立中央大學
Abstract:	編譯器除了將程式碼由高階語言轉換成組合語言或者是機器語言外，還會根據不同的目的對程式碼進行最佳化以提升程式碼的品質。然而，由於最佳化的演算法很多，使得最佳化的順序會影響程式碼品質，有時甚至會使程式碼品質更差，如指令下沉使得取餘數、取商數分開到不同基本程式塊，導致商餘合併無法套用，這樣的阻擋問題會使程式碼的效能變差。由於指令下沉為機器不相依的最佳化，商於合併則為機器相依的最佳化，應用於後端，因此兩者難以對調其順序以避開該衝突。我們提出一個演算法，以解決該阻擋問題。我們將該演算法介入並實作於 LLVM 最佳化器上的指令下沉內，以求解決所有會受影響的後端。最後根據可行性、相容性、針對性三個面向進行完整的評估，評估結果表示確實能夠有效的解決該阻擋問題且不會與其他最佳化演算法產生衝突而最佳化失敗，也能夠只針對有問題的指令進行處理而不會影響到正常的其他指令。;Compiler compiles high-level language like C language to assembly language even machine code to let programmers don′t need to concern about what machine actually do and how to write machine code while developing. In addition, it can optimize the code base on different purpose. However, according to compiler phase-ordering problem, the orders of optimizations will impact the quality of programs. In some cases, the sequence of optimizations will make the program worse. For example, Instruction Sink separates division and modulo to different basic blocks and this act will make Division-Modulo Combine failed to be applied. Because the former is a machine-independent optimization and the latter is a machine-dependent optimization, it′s hard to reorder them to avoid the problem. We propose an algorithm to solve this blocking issue. We implement our algorithm in Instruction Sink in LLVM Optimizer to keep this problem from all impacted backend. In the end, we evaluate the feasibility, the compatibility and the pertinence. The result shows that our proposal can solve this problem and won′t conflict with other optimizations to let program worse. It also shows that our algorithm only targets the instruction with blocking issue and won′t change the other normal instructions.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	52	View/Open

社群 sharing

Loading...