部分的な冗長性の排除

コンパイラ理論では、部分冗長性除去(PRE) は、プログラムのすべてのパスではなく一部のパスで冗長な式を除去するコンパイラ最適化です。PRE は共通部分式除去の一種です。

式によって計算された値が、プログラムからその式に至るパスの一部で既に使用可能である場合、その式は部分的に冗長であると呼ばれます。式によって計算された値が、プログラムからその式に至るパスのすべてで使用可能である場合、その式は完全に冗長です。PRE は、部分的に冗長な式を、まだ計算されていないパスに挿入することで部分的に冗長な式を排除し、部分的に冗長な式を完全に冗長にします。

たとえば、次のコードでは:

 if ( some_condition ) { // x を変更しないコードy = x + 4 ; } else { // x を変更しないその他のコード} z = x + 4 ;  
   
       
 
  
   
 
     

x+4に割り当てられた式は、zが true の場合に 2 回計算されるため、部分的に冗長です。PRE は式に対して コード移動をsome_condition実行し、次の最適化されたコードを生成します。

 if ( some_condition ) { // x を変更しないコードt = x + 4 ; y = t ; } else { // x を変更しないその他のコードt = x + 4 ; } z = t ;  
   
       
     
 
  
   
       
 
   

PREの興味深い特性は、共通部分式の削除（の一種）とループ不変コードの移動を同時に実行することです。^{[1] [2]}さらに、PREを拡張して損傷した部分冗長性を削除し、強度の削減を効果的に実行することができます。これにより、PREは最適化コンパイラーにおける最も重要な最適化の1つになります。伝統的に、PREは語彙的に同等な式に適用されますが、最近、静的単一代入形式に基づくPREの定式化が公開され、PREアルゴリズムを式ではなく値に適用し、PREとグローバル値の番号付けを統合しました。

• 値の番号付け
• 冗長コード
• デッドコードの除去

• Muchnick、Steven S.高度なコンパイラの設計と実装。Morgan Kaufmann。1997 年。
• Knoop, J.、Ruthing, O.、およびSteffen, B. Lazy Code Motion。ACM SIGPLAN Notices Vol. 27、Num. 7、1992 年 7 月、'92 PLDI カンファレンス。
• Paleri, VK, Srikant, YN, Shankar, P.部分的冗長性除去のためのシンプルなアルゴリズムSIGPLAN Notices, Vol. 33(12). 35–43ページ (1998).
• Kennedy, R., Chan, S., Liu, SM, Lo, R., Peng, T., Chow, F. SSA 形式での部分的な冗長性の除去。ACM Transactions on Programming Languages Vol. 21, Num. 3, pp. 627–676, 1999。
• VanDrunen, T.、および Hosking, AL 「値ベースの部分的冗長性除去」、Lecture Notes in Computer Science Vol. 2985/2004、pp. 167 – 184、2004 年。
• Cai, Q. および Xue, J. 「最適かつ効率的な投機ベースの部分的冗長性除去」コード生成および最適化に関する国際シンポジウム (CGO'03)、91-104、2003 年。
• Xue, J. および Knoop, J. 「最大フロー問題としての PRE の新たな考察」 国際コンパイラ構築会議 (CC'06)、139-154 ページ、オーストリア、ウィーン、2006 年。
• Xue, J. および Cai Q.投機的 PRE のライフタイム最適アルゴリズム。ACM Transactions on Architecture and Code Optimization Vol. 3, Num. 3、pp. 115–155、2006 年。