P4 Compiler 系列 – IR 及 Visitor

5 月 19, 2018

在講 Midend 之前,首先要先講一下 IR 大致的架構,以及目前 P4 Copmiler 處理 IR 的方式。

本文是基於 p4c 中的 compiler-design.pptx 文件所撰寫。

Intermediate representation (IR)

首先我們可以將 P4 所定義的 IR 視為 Parser 解析完後儲存程式結構的資料結構,而這一個結構是基於 DAG (Directed Acyclic Graph) 設計,在這個圖(Graph)的特性就是他是有向且不存在環(circle)。

依據官方文件,IR 有以下幾個特點:

  • 不可更改的(Immutable):當 IR 被產生之後,則其他程式不可更改 IR Node 的內容。
  • 強型態(Strongly-Type):每一個 IR Node 都有固定不可變的型態。
  • DAG 架構
  • 透過 Visitor 進行超做:P4 Compiler 無論那一部分都是使用「訪問者設計模式」(Visitor Design Pattern)去對 IR 去處理的。
  • IR 的 Class 可以依據不同的 Backend 去擴充


註:本圖僅供參考,確切 DAG 請參考 P4 官方所提供的 IR 定義檔

在前一章節有提到說 Frontend 並沒有產生 IR,而是對 IR 去進行檢查以及優化,Midend 也是對 IR 進行優化,只不過 Midend 會針對不同的 Target 或 Architecture 去做優化處理。

處理完後的 IR 是可以在被轉換回 P4 程式的,由於可以轉換回 P4 程式,開發者可以去確認自己開發的 Midend 是否有做出正確的優化。

此外 IR 的結構當中也會保留該 IR Node 所對應到的程式位址,方便讓開發者得知這一個 IR 是基於哪一段程式去產生的。

Visitor

剛剛提到 P4 Compiler 透過 Visitor 去走訪 Parser 所產生的 DAG 中的 IR Node 並進一步去處理每一個 Node。

這邊簡介一下在 P4 Compiler 中所用的 Visitor Design Pattern。

在這一個設計模式當中,每一個資料結構的類別都會包含一個 accept 方法,而開發者會設計出一個 Visitor 類別,所有的資料節點都會去 accept 這一個 Visitor ,若該資料節點擁有子節點,則一樣會讓子節點們去 accept 同一個 Visitor。

當節點 accept 這一個 Visitor 之後,集會呼叫 Visitor 的 visit 方法,Visitor 必須實作與該節點類別相關的 visit 方法。

P4 Copmiler 函式庫提供了與 IR 相關的 Visitor,而開發著無需針對所有 IR 的類別(P4Table, P4Control, P4Action…..) 去設計 visit 方法,僅需撰寫該 Visitor 需要處理的類別即可。

在 P4 Copmiler 函式庫中定義了 3 種不同的 Visitor,方別是:

  • Inspactor:僅走訪節點,不對節點做任何的修改,用於蒐集資訊用。
  • Modifier:除了走訪以外,還可能會修改節點內容,但不會去動到 DAG 結構。
  • Transform:會去修改節點內容以及更改 DAG 結構。

除了這三個需要實作的 Visitor 以外,還有一個常用的 Visitor 類別:PassManager,其主要是用來包裝一系列的 Visitor,被包裝的 Visitor 們會依據順序去被 IR 節點給 accept

基本上上面的 Visitor 都會透過 Preorder 的方法去走訪各個節點。


註:本圖僅供參考,確切 DAG 請參考 P4 官方所提供的 IR 定義檔

preorder, postorder

各類型的 Visitor 可以依據需求去實作 preorder 以及 postorder 方法,preorder 會在走訪至一個節點時就被呼叫,而 postorder 會在該節點的子節點(Children)被走訪完之後才會呼叫。

以虛擬碼呈現的話大概會向這樣子:

if visit_preorder(node) {
    for child in node.children {
        visit(child)
    }
    visit_postorder(node)
}

ReferenceMap

P4 Compiler Library 中有提供一個名為 ResolveReference 的 Visitor,用途是將所有的 P4 程式走一遍,有些地方描述了一個 P4 的資源(Table, Headers…)是如何實作的,而有些地方則是去使用他們,Visitor 可以透過 ReferenceMap 去查詢某一個名稱所對應到的定義。

Code

每一組 IR 都會被定義在一個 .def 檔案中,例如 ir.def 就定義了基本的 IR 類別。

而 Visitor 相關的類別則是定義在 visitor.h 當中

Evaluation

剛剛提到說 Compiler 在經過 Frontend 以及 Midend 去進行檢查以及優化,而在 Midend 最後的階段通常會透過 Evaloator 這一個 Visitor 去把 IR Node 轉換成為 CompileTimeValue。每一個 CompilerTimeValue 都是在編譯階段所使用的常數。

此外,Evaluator 會將各個定義好的 P4 資源轉換成一個個的 Block,目前會轉換成 Block 的資源有:Parser, Control, Package, Extern 以及 Table。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料