ROSE 編譯器框架/程式分析

概述

ROSE 已實現以下編譯器分析

呼叫圖分析
控制流圖
資料流分析：包括活性分析、定義-使用分析等。
依賴分析
副作用分析

控制流圖

ROSE 提供了控制流圖的幾種變體

虛擬控制流圖

虛擬控制流圖 (vcfg) 在需要時動態生成。因此，ROSE AST 與其對應的控制流圖之間不會出現不匹配。缺點是，每次需要時都會重新生成相同的 vcfg。這可能成為效能瓶頸。

事實

文件：虛擬 CFG 在 ROSE 教程的**第 19 章虛擬 CFG**中有所介紹 pdf
原始檔
- src/frontend/SageIII/virtualCFG/virtualCFG.h
- src/frontend/SageIII/virtualCFG/virtualCFG.C // 不僅提供 virtualCFG.h 的定義，還在 VirtualCFG 中擴充套件 AST 節點支援
- src/ROSETTA/Grammar/Statement.code // SgStatement 節點等成員函式的原型
- src/ROSETTA/Grammar/Expression.code // SgExpression 節點等成員函式的原型
- src/ROSETTA/Grammar/Support.code // SgInitialized(LocatedNode) 節點等成員函式的原型
- src/ROSETTA/Grammar/Common.code // 其他節點等成員函式的原型
- src/frontend/SageIII/virtualCFG/memberFunctions.C // 每個 AST 節點與虛擬 CFG 相關的成員函式的實現
  - 此檔案將有助於生成 buildTree/src/frontend/SageIII/Cxx_Grammar.h
測試目錄：tests/CompileTests/virtualCFG_tests
一個點圖生成器：為原始或有趣的虛擬 CFG 生成點圖。
- 原始碼：tests/CompileTests/virtualCFG_tests/generateVirtualCFG.C
- 安裝在 rose_ins/bin 下

如何擴充套件 VirtualCFG 以支援 OpenMP

如何在中新增 SgOmpClause 的 CFGNode
1. 識別 ROSETTA 中前端的類名

例如，如果 SgOmpPrivateClause 或 SgOmpSharedClause 在 VirtualCFG 中不受支援，則有必要檢查 buildTree/src/frontend/SageIII/Cxx_Grammar.h 是否具有為新增 SgOmpClause 的 CFGEdge 的函式原型，例如 SgOmpClause::cfgInEdge() SgOmpClause::cfgOutEdge() 如果沒有原型，則意味著您的 CFGNode 不屬於 SgExpression、SgStatement 和 SgExpression。SgOmpClause 可以新增到 src/ROSETTA/Grammar/Support.code 中，

2. 在 src/frontend/SageIII/virtualCFG/memberFunctions.C 中新增函式定義，以給出新增 CFGNode 和 CFGEdge 的定義

  step1: construct SgOmpClause::cfgndexForEnd()
            this index is based on the AST graph of your source code, the index is explicit in AST node
   real example:

SgOmpClauseBodyStatement::cfgIndexForEnd() const {

  int size = this->get_clauses().size(); // the number of clauses in #pragma omp parallel
  return (size + 1); // clauses + body

}

  step2: construct cfgInEdge() for this CFGNode
           please refer to AST, since AST can show all node information,
           real example:
           std::vector<CFGEdge> SgOmpClauseBodyStatement::cfgInEdges(unsigned int idx) {
 std::vector<CFGEdge> result;
 addIncomingFortranGotos(this, idx, result);

if( idx == 0 )

  {
   makeEdge( getNodeJustBeforeInContainer( this ), CFGNode( this, idx ), result );
   }
  else
  {
     if( idx == ( this->get_clauses().size() + 1 ) )
      {
       makeEdge( this->get_body()->cfgForEnd(), CFGNode( this, idx ) , result ); //connect variables clauses first, then parallel body
      }
     else
      {
          if( idx < ( this->get_clauses().size() + 1 ) )
           {
              makeEdge( this->get_clauses()[idx -1]->cfgForEnd(), CFGNode( this, idx ), result );//connect variables clauses first, then parallel body
           }
          else
           {
            ROSE_ASSERT( !" Bad index for SgOmpClauseBodyStatement" );
           }
      }
  }

return result; }

 step3: construct cfgOutEdge for CFGNode
 For example:
   std::vector<CFGEdge> SgOmpClauseBodyStatement::cfgOutEdges(unsigned int idx) {//! edited by Hongyi for edges between SgOmpClauseBodyStatement  and SgOmpClause
  std::vector<CFGEdge> result;

addIncomingFortranGotos( this, idx, result ); if( idx == (this->get_clauses().size() + 1 ) )

 {
    makeEdge( CFGNode( this ,idx), getNodeJustAfterInContainer( this ), result );
 }
else
 {
   if( idx == this->get_clauses().size()  )
      {
        makeEdge( CFGNode( this, idx ), this->get_body()->cfgForBeginning(), result ); // connect variable clauses first, parallel body last
      }
     else
     {
       if( idx < this->get_clauses().size() ) // connect variables clauses first, parallel body last
         {
           makeEdge( CFGNode( this, idx ), this->get_clauses()[idx]->cfgForBeginning(), result );
         }
        else
         {
           ROSE_ASSERT( !"Bad index for SgOmpClauseBodyStatement" );
         }
      }
 }

return result; }

3. 如何檢查結果

首先檢查 AST 圖 /Users/ma23/Desktop/Screen shot 2012-08-24 at 11.51.33 AM.png 在此示例中，您將發現從 SgOmpParallelStatement 有三個子樹。一個是 get_body，另外兩個分別是 SgOmpPrivateClasue 和 SgOmpSharedClauserespectively。因此索引為 3。// 訪問 CFGNode 的順序是先訪問子句，然後是並行主體

靜態控制流圖

由於虛擬控制流圖的效能問題，我們開發了另一個靜態版本，它像普通圖一樣持久存在記憶體中。

事實

文件：ROSE 教程的**19.7 靜態 CFG** pdf
測試目錄：rose/tests/CompileTests/staticCFG_tests

靜態和過程間 CFG

事實

文件：ROSE 教程的**19.8 靜態、過程間 CFG** pdf
測試目錄：rose/tests/CompileTests/staticCFG_tests

虛擬函式分析

事實

原始貢獻者：來自 UTSA 的 Faizur，完成於 2011 年夏季
程式碼：位於 src/midend/programAnalysis/VirtualFunctionAnalysis。
使用以下論文中使用的技術實現："過程間指標別名分析 - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2382"。該論文將虛擬函式解析簡化為指標別名問題。該論文采用流敏感過程間資料流分析來解決別名問題，使用緊湊表示圖來表示別名關係。
ROSE 儲存庫的 roseTests 資料夾中有一些測試檔案，他告訴我實現支援函式指標以及跨不同檔案（標頭檔案等）編寫的程式碼。
文件：ROSE 教程 pdf 的第 24 章基於資料流分析的虛擬函式分析

定義-使用分析

如果您想要定義-使用分析，請嘗試以下方法 http://www.rosecompiler.org/ROSE_HTML_Reference/classVariableRenaming.html

VariableRenaming v(project);
v.run();
v.getReachingDefsAtNode(...);

測試

cd buildtree/tests/nonsmoke/functional/roseTests/programAnalysisTests/defUseAnalysisTests
輸入 ```make check```

活性分析

請參閱活性分析

指標分析

https://mailman.nersc.gov/pipermail/rose-public/2010-September/000390.html

On 9/1/10 11:49 AM, Fredrik Kjolstad wrote:
> Hi all,
>
> I am trying to use Rose as the analysis backend for a refactoring 
> engine and for one of the refactorings I am implementing I need 
> whole-program pointer analysis.  Rose has an implementation of 
> steensgard's algorithm and I have some questions regarding how to use 
> this.
>
> I looked at the file steensgaardTest2.C to figure out how to invoke 
> this analysis and I am a bit perplexed:
>
> 1. The file SteensgaardPtrAnal.h that is included by the test is not 
> present in the include directory of my installed version of Rose. 
>  Does this mean that the Steensgaard implementation is not a part of 
> the shipped compiler, or does it mean that I have to retrieve an 
> instance of it through some factory method whose static return type is 
> PtrAnal?

I believe it is in the shipped compiler. And you're using the correct 
file to figure out how to use it. It should be in the installed include 
directory --- if it is not, it's probably something that needs to be 
fixed. But you can copy the include file from 
ROSE/src/midend/programAnalysis/pointerAnal/ as a temporary fix

> 2. How do I initialize the alias analysis for a given SgProject?  Is 
> this done through the overloaded ()?

The steensgaardTest2.C file shows how to set up everything to invoke the 
analysis. Right now you need to go over each function definition and 
invoke the analysis explicitly, as illustrated by the main function in 
the file.

> 3. Say I want to query whether two pointer variables alias and I have 
> SGNodes to their declarations.  How do I get the AstNodePtr needed to 
> invoke the may_alias(AstInterface&, const AstNodePtr&, const 
> AstNodePtr&) function?  Or maybe I should rather invoke the version of 
> may_alias that takes two strings (varnames)?

To convert a SgNode* x to AstNodePtr, wrap it inside  an AstNodePtrImpl 
object, i.e., do AstNodePtrImpl(x), as illustrated inside the () 
operator of TestPtrAnal in steensgaardTest2.C.

> 4. How do I query whether two parameters alias?

The PtrAnal class has  the following interface method
     may_alias(AstInterface& fa, const AstNodePtr& r1, const AstNodePtr& 
r2);
It is implemented in SteensgaardPtrAnal class, which inherit PtrAnal 
class. To build AstInterface and AstNodePtr,
you simply need to wrap SgNode* with some wrapper classes, illustrated 
by steensgaardTest2.C

- Qing Yi

void func(void) {
int* pointer;
int* aliasPointer;

pointer = malloc(sizeof(int));
aliasPointer = pointer;
*aliasPointer = 42;

printf("%d\n", *pointer);
}

The SteensgaardPtrAnal::output function returns:
c:(sizeof(int )) LOC1=>LOC2
c:42 LOC3=>LOC4
v:func LOC5=>LOC6 (inparams: ) ->(outparams:  LOC7)
v:func-0 LOC8=>LOC7
v:func-2-1 LOC9=>LOC10
v:func-2-3 LOC11=>LOC12 (pending  LOC10 LOC13=>LOC14 =>LOC4 )
v:func-2-4 LOC15=>LOC16 =>LOC17
v:func-2-5 LOC18=>LOC14 =>LOC4
v:func-2-aliasPointer LOC19=>LOC14 =>LOC4
v:func-2-pointer LOC20=>LOC13 =>LOC14 =>LOC4
v:malloc LOC21=>LOC22 (inparams:  LOC2) ->(outparams:  LOC12)
v:printf LOC23=>LOC24 (inparams:  LOC16=>LOC17  LOC14=>LOC4 ) ->(outparams:
 LOC25)

SSA

ROSE 已實現 SSA 形式。郵件列表中的一些討論：連結。

Rice 分支有一個數組 SSA 的實現。我們正在等待他們的提交被推送到 Jenkins。--Liao (討論 • 貢獻) 2012 年 6 月 19 日 18:17 (UTC)

副作用分析

ROSE 中至少有兩種實現

第一種：推薦使用。

SageInterface 介面函式內部：http://rosecompiler.org/ROSE_HTML_Reference/namespaceSageInterface.html
- 例如 bool SageInterface::collectReadWriteVariables (SgStatement *stmt, std::set< SgInitializedName * > &readVars, std::set< SgInitializedName * > &writeVars) // 可以將 for 迴圈及其主體（基本塊語句）傳遞給此函式，並獲取讀/寫變數。如果分析不成功，它將返回 false。因此，在使用結果之前務必檢查返回值。
- 此函式是以下函式的包裝函式
- bool AnalyzeStmtRefs(LoopTransformInterface &la, const AstNodePtr& n,CollectObject<AstNodePtr> &wRefs, CollectObject<AstNodePtr> &rRefs) // 來自 DepInfoAnal.C
- StmtSideEffectCollect(LoopTransformInterface::getSideEffectInterface())(fa,n,&colw,&colr); //src/midend/astUtil/astSupport/StmtInfoCollect.h

第二種：這種方法不夠健壯，無法使用。它還依賴 sqlite 庫進行安裝。

原始碼：src/midend/programAnalysis/sideEffectAnalysis
測試：tests/roseTests/programAnalysisTests/sideEffectAnalysisTests
該演算法基於以下論文：K. D. Cooper 和 K. Kennedy。1988 年。線性時間內的過程間副作用分析。在程式設計語言設計和實現 (PLDI '88) 1988 年 ACM SIGPLAN 會議論文集中，R. L. Wexelblat（編輯）。ACM，紐約，紐約，美國，57-66。

通用資料流框架

隨著 ROSE 專案的進行，我們收集了相當多的資料流分析版本。維護和使用它們很痛苦，因為它們

重複迭代不動點演算法
分散在不同的目錄中，並且
使用不同的表示來表示結果。

一個持續的努力是將所有資料流分析工作整合到一個框架中。

快速事實

原始作者：Greg Bronevetsky
程式碼審閱者：廖春華
文件
原始碼：./src/midend/programAnalysis/genericDataflow 下的檔案
測試：tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests
當前實現的分析
- 支配者分析：dominatorAnalysis.h dominatorAnalysis.C
- 活躍/死變數分析，或活躍性分析：liveDeadVarAnalysis.h liveDeadVarAnalysis.C
- 常量傳播：constantPropagation.h constantPropagation.C：TODO 需要將檔案從 /tests 移動到 src/

在通用資料流框架中檢視更多內容。

依賴分析

TODO：事實證明，介面工作尚未合併到我們的主分支中。因此，以下說明不適用！

依賴圖的介面可以在 DependencyGraph.h 中找到。底層表示是 n DepGraph.h。需要 BGL 來訪問圖。

這裡附有這封電子郵件的 6 個示例。在 deptest.C 中，還有一些宏可以實現更準確的分析。

如果定義了 USE_IVS，則將執行歸納變數替換。如果定義了 USE_FUNCTION，則依賴項可以採用使用者指定的函式副作用介面。否則，如果兩者都沒有定義，它將執行正常的依賴分析並構建圖形。