跳到主要內容

臺灣博碩士論文加值系統

(3.238.204.167) 您好!臺灣時間:2022/08/09 22:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王勳和
研究生(外文):Hsun-Her Wang
論文名稱:應用FUDChains進行迴圈中常數傳遞之分析
論文名稱(外文):Constant Propagation for Loops with Factored Use-Def Chains
指導教授:雍忠
指導教授(外文):Chung Yung
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:63
中文關鍵詞:控制流程圖常數傳遞需求導向靜態單一指定陳述格式擴大的後支配樹要素使用定義關聯
外文關鍵詞:constant propagationSSA formcontrol flow graphaugmented postdominated treefactored use-def chainsdemand-driven
相關次數:
  • 被引用被引用:0
  • 點閱點閱:210
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
常數傳遞(constant propagation)分析是一個以資料流分析法為基礎的最佳化分析,是一個提供有關一個程序如何處理它所內含資料的靜態分析法。 編譯器可以經由在程序中執行常數傳遞分析來產生更有效率的程式碼。 常數傳遞分析可視為一個簡化程式碼的技術,它可以決定針對某一特定變數的所有指定陳述其結果值是否為常數,並且將這相同的常數值提供給一些特定的程式點。

在這篇論文中,我們開發了一個常數傳遞的新方法,並且我們將常數傳遞問題專注在迴圈上。 我們的方法結合了Wegman和Zadeck所提出找尋條件常數(conditional constant)的SCC演算法及Wolfe等人所提出在迴圈中尋找線性歸納常數(linear induction variable)的方法。 我們所採用的方法是根基在要素使用-定義關聯(Factored Use-Def Chains)上,它是一個已廣為流傳的靜態單一指定陳述格式(SSA form)的另一需求導向(demand-driven)表示法。 我們的方法可以解決程式裡迴圈中的常數。 我們已經實作出這方法的演算法並以SCC演算法做實驗性的比較。
Constant propagation analysis is the optimization based on data-
ow analysis
which is a static analysis of providing global information about how a proce-
dure manipulates its data. Compiler can generate more e cient codes when
performing constant propagation within a procedure. Constant propagation
can be regarded as a code reduction technique that determines whether all as-
signments to a particular variable is a constant and provides the same constant
value to some particular points.
In this thesis, we develop a new approach of constant propagation with a
focus on the constant propagation problems within loops. We combine the idea
from Wegman and Zadeck's SCC algorithm of nding conditional constants
and the idea from the method by Wolfe et al. of nding linear induction
variables[Wol96] with loops. The method we applied is based on Factored
Use-Def (FUD) chains, which is a demand-driven representation of the popular
Static Single Assignment (SSA) form. We develop a new approach that nds
the constants of the loops in a program. We have implemented this algorithm
and we present experiments comparing our approach with the SCC method.
Dedication iii
Acknowledgements iv
List of Figures ix
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . 1
1.2 Terminology . . . . . . . . . . . . . . . . . 3
1.2.1 Loops . . . . . . . . . . . . . . . . . . . 5
1.2.2 Notation . . . . . . . . . .. . . . . . . . 6
1.3 Organization of the thesis . . . . . . . . . 8
2 Background 10
2.1 Graph Preliminaries . . . .. . . . . . . . . 10
2.1.1 Control Flow Graph . . . . . . . . . . . . 11
2.1.2 Dominate and Postdominate . . . . . . .. . 12
2.1.3 Control Dependence . . . . . . . . . . . . 16
2.2 Static Single Assignment Construction . . . 18
2.2.1 Why is SSA Good . . . . . . . . . . . . . .21
2.2.2 APT Data Structure . . . . . . . . . . . . 22
2.2.3 Construction . . . . . . . . . . . . . . . 24
2.3 Constructing SSA with Factored Use-Def Chains . .. 25
3 Constant Propagation 31
3.1 Compilation Model . . . . . . . . . . . . .. 31
3.2 Constant Propagation for Loops . . . . . . . 33
3.3 Uses of Constant Propagation . . . . . . . . 38
4 Implementation and Experiment 42
4.1 Symbol Table and Block Table . . . . . . . . 44
4.2 Implementation of -Placement . . . . . . .. 46
4.3 Experiments . . . . . . . . . . . . . . . . 50
5 Related Work 52
5.1 Interprocedural Constant Propagation . . . . 52
5.2 Wegman and Zadeck's Approach . . . . . . . . 53
5.3 Approach by Wolfe et al. . . . . . . . . . . 55
6 Conclusions 57
[ASU86] Aho, Sethi and Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley Press, 1986.
[BMO90] R. A. Ballance, A. B. Maccabe, and K. J. Ottenstein. "The Program Dependence Web: A representation supporting control - ,data-, and demand-driven interpretation of imperative languages," Proceeding
of the ACM SIGPLAN Conference on Programming Language De-
sign and Implementation, pp.257-271, 1990.
[CCK86] David Callahan, Keith D. Cooper, Ken Kennedy, and Linda Tor-czon, "Interprocedural Constant Propagation," Proceeding of the 1986 SIGPLAN Conference on Compiler Construction, pp.152-161 July 1986.
[CFR91] Ron Cytron, Jeanne Ferrante, Barry K. Rose, and Mark N. Wegman. "Efficiently Computing Static Single Assignment From and the Control Dependence Graph," ACM Transactions on Programming Languages and Systems, Vol 13, No 4, pp.451-490, 1991.
[CH95] Paul R. Carini and Michael Hind, "Flow-Sensitive Interprocedural Constant Propagation," Proceeding of the 1995 SIGPLAN Conference on Programming Language Design and Implementation, pp.23-31 Jun. 1995.
[GT93] Dan Grove and Linda Torczon, "Interprocedural Constant Propagation: A Study of Jump Function Implementations," Proceeding of the 1993 SIGPLAN Conference on Programming Language Design and Implementation, pp.90-99 Jun. 1993.
[Kil73] G. Kildall. "A Unifed Approach to Global Program Optimization," Proceedings of the First Annual ACM Symposium on Principles of Programming Languages, 1973.
[KLT92] Robert L. Kruse, Bruce P. Leung, and Clovis L. Tondo. Data Structures and Program Design in C, 1992.
[KU77] J. B. Kam, J. D. Ullman. "Monotone data
ow analysis frameworks," Acta Informatica, 7:305-317, 1977.
[LT79] Thomas Lengauer and Robert Endre Tarjan. "A fast algorithm fornding dominators in a flowgraph," Proceeding of the ACM Transactions on Programming Languages and Systems, pp.121-141, July 1979.
[MS93] Robert Metzger and Sean Stroud, "Interprocedural Constant Propagation: An Empirical Study," Proceeding of the ACM Letters on Programming Languages and Systems, pp.213-232 Mar.-Dec. 1993.
[Muc97] Steven S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann Press, 1997.
[PJ93] Keshav Pingali and Richard Johnson. "Dependence-Based Program Analysis," Proceedings of the 1993 SIGPLAN Conference on Programming Language Design and Implementation , pp.78-89, June 1993.
[PB95] Keshav Pingali and Gianfranco Bilardi, "APT:A Data Structure for Optimal Control Dependence Computation," Proceeding of the ACM Conference on Programming Language Design and Implementation, pp.32-46, June 1995.
[PB97] Keshav Pingali and Gianfranco Bilardi, "Optimal Control Dependence Computation and the Roman Chariots Problem," Proceeding of the ACM Transactions on Programming Languages and Systems, pp.1-30, May 1997.
[SGW93] Eric Stoltz, Michael P. Gerlek, and Michael Wolfe, "Constant Propagation : A Fresh Demand-Driven Look," September 1993.
[SGW94] Eric Stoltz, Michael P. Gerlek, and Michael Wolfe, "Extended SSA with factored use-def chains to support optimization and parallelism," Proceeding of Hawaii International Conferense on Systems Sciences, January 1994.
[Wol96] Michael Wolfe, High Performance Compilers for Parallel Computing, Addison Wesley Press, 1996.
[WZ91] Mark N. Wegman and F. Kenneth Zadeck, "Constant Propagation with Conditional Branches," ACM Transactions on Programming Languages and Systems, Vol.13, No.2, pp.181-210, April 1991.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top