編譯器優化:何為別名分析

来源:https://www.cnblogs.com/huaweiyun/archive/2022/09/16/16698988.html
-Advertisement-
Play Games

摘要:別名分析是編譯器理論中的一種技術,用於確定存儲位置是否可以以多種方式訪問。 本文分享自華為雲社區《編譯器優化那些事兒(6):別名分析概述》,作者:畢昇小助手。 1.簡介 別名分析是編譯器理論中的一種技術,用於確定存儲位置是否可以以多種方式訪問。如果兩個指針指向相同的位置,則稱這兩個指針為別名。 ...


摘要:別名分析是編譯器理論中的一種技術,用於確定存儲位置是否可以以多種方式訪問。

本文分享自華為雲社區《編譯器優化那些事兒(6):別名分析概述》,作者:畢昇小助手。

1.簡介

別名分析是編譯器理論中的一種技術,用於確定存儲位置是否可以以多種方式訪問。如果兩個指針指向相同的位置,則稱這兩個指針為別名。 但是,它不能與指針分析混淆,指針分析解決的問題是一個指針可能指向哪些對象或者指向哪些地址,而別名分析解決的是兩個指針指向的是否是同一個對象。指針分析和別名分析通常通過靜態代碼分析來實現。

別名分析在編譯器理論中非常重要,在代碼優化和安全方面有著非常廣泛且重要的應用。編譯器級優化需要指針別名信息來執行死代碼消除(刪除不影響程式結果的代碼)、冗餘載入/存儲指令消除、指令調度(重排列指令)等。編譯器級別的程式安全使用別名分析來檢測記憶體泄漏和記憶體相關的安全漏洞。

2.別名分析分類

別名分析種類繁多,通常按如下屬性進行分類:域敏感(field-sensitivity)、過程內分析(Intra-Procedural)v.s.過程間分析(Inter-Procedural)、上下文敏感度(context-sensitivity)和流敏感度(flow-sensitivity)。

2.1 域敏感(Field-Sensitivity)

域敏感是對用戶自定義類型進行分析的一種策略(亦可以處理數組)。在域敏感維度共有三種分析策略:域敏感(field-sensitive)、域非敏感(field-insensitive)、域基礎分析(field-based)。以下麵代碼為例:

struct Test {
int field1;
int field2;
}
Test a1;
Test a2;

Note:field這裡為結構體或者類的數據成員。

域非敏感:對每個對象建模,而對對象中的成員不進行處理;其建模後的結果如下圖,僅有a1.*和a2.*的區別:

域基礎分析:僅對結構體中的成員進行建模,而不感知對象。其建模後的結果如下圖,僅有*.field1和*.field2:

域敏感:既對對象建模,又對成員變數進行處理。其建模後的結果如下圖,有a1.field1、a1.field2、a2.field1、a2.field2:

處理數組時,相同的原則亦適用。以C整數數組為例:int a[10],域非敏感分析僅使用一個節點建模:a[*],而域敏感分析創建10個節點:a[0]、a[1]、...、a[9]。

總結:域敏感別名分析準確性高,但是當存在嵌套結構或者大數組時,節點數量會迅速增加,分析成本也會陡然上升。

2.2 過程內分析(Intra-Procedural)v.s.過程間分析(Inter-Procedural)

過程內分析僅分析函數體內部的指針,並沒有考慮與其他函數之間的相互影響。需要特別指出的是,過程內分析當處理包含指針入參的函數或者返回指針的函數時,其分析可能不夠準確。相反,過程間分析會在函數調用過程中處理指針的行為。

過程內分析不易於擴展,精度較低。相比過程間分析,過程內分析更容易實現,且過程內/間分析與上下文敏感度分析高度相關,因為一個上下文敏感分析必定是一個過程間分析。

2.3 上下文敏感度(Context-Sensitivity)

上下文敏感度用來控制函數調用該如何分析。有兩種分析方法:上下文敏感(context-sensitive) 和上下文非敏感(context-insensitive)。上下文敏感在分析函數調用的目標(被調用者)時考慮調用上下文(調用者)。以如下代碼為參考[1]:

1 public static void main(String[] args) {
2      String name1 = getName(3);  // Tainted
3      String sql1 = "select * from user where name = " + name1;
4 sqlExecute(sql1);  // Taint Sink
5 
6      String name2 = getName(-1);  // Not Tainted
7      String sql2 = "select * from user where name = " + name2;
8 sqlExecute(sql2);
9  }
10 
11 private static String getName(int x) {
12 if (x > 0) {
13 return System.getProperty("name");
14   } else {
15 return "zhangsan";
16   }
17  }

如上所示,getName()方法基於入參的不同,會返回不同的結果,在第2行和第6行,獲取到的name1和name2的污點信息不同,當入參為3時,返回的是一個從環境變數中獲取的污染的數據,導致sql註入,而當入參為-1時,返回的是一個常量,不是污染數據,不會有問題。 在上下文敏感的分析中,在第4行應該報一個sql註入問題,而在第8行則不應該報sql註入問題。而上下文非敏感的分析中,不考慮傳入參數的不同,getName()方法則全部返回一個{System.getProperty("name")}∨{zhangsan},從而導致第4行和第8行都會報一個sql註入的問題。

上下文敏感別名分析需要有一種方法,為函數getName創建抽象描述,以便每次調用它時,分析器都可以將調用上下文應用於抽象描述。

總結:上下文敏感分析比較準確,但是增加了複雜度。

2.4 流敏感度Flow-Sensitivity

流敏感度是一種是否考慮代碼順序的原則。有兩種方法:流敏感(flow-sensitive)和流非敏感(flow-insensitive)。

流非敏感不考慮代碼順序,併為整個程式生成一組別名分析結果,而流敏感考慮代碼順序,計算程式中每個指針出現的位置的別名信息。以如下代碼為例:

1 int a,b;
2 int *p;
3   p = &a;
4   p = &b;

流非敏感的分析結果是針對整個代碼塊,其結果應該是:指針p可能指向變數a或者變數b。流敏感生成的別名信息是,在第3行,指針p指向變數a,在第4行以後指針p指向變數b。

Note:當程式具有許多條件語句、迴圈或遞歸函數時,流敏感分析的複雜性會大大增加。要執行流敏感分析,需要完整的控制流圖。因此,流敏感分析非常精確,但對於大多數情況來說,它的分析成本過高,無法在整個程式上執行。

3.別名分析常見演算法介紹

常見的別名演算法共有三種:Andersen's指針分析演算法、Steensgaard's指針分析演算法和數據結構分析演算法。

Andersen's指針分析是一種流非敏感和上下文非敏感的分析演算法。Andersen's指針分析演算法複雜度較高,實踐應用性較差,其時間複雜度為,其中n為指針節點個數。

Steensgaard's指針分析演算法也是一種流非敏感,上下文非敏感且域非敏感的別名分析演算法。其時間複雜度較低,實現相對簡單,實踐應用廣,其時間複雜度為,其中無限接近於1,但是其別名分析的準確性較低。

數據結構分析演算法是一種流非敏感,上下文敏感和域敏感的演算法。其時間複雜度較低,為O(n * log(n)) ,應用性較好,但是由於不支持MustAlias(參考“AliasAnalysis Class概覽”章節),導致其應用有局限性。

4.別名分析在LLVM中的應用與實現

4.1 應用

別名分析在代碼優化和安全方面有著非常重要且廣泛的應用,以下麵C代碼為例,來簡單介紹別名分析在代碼優化方面的應用[2]。

int foo (int __attribute__((address_space(0)))* a,
 int __attribute__((address_space(1)))* b) {
 *a = 42;
 *b = 20;
 return *a;
}

__attribute__屬性指定了變數a指向地址0,變數b指向地址1。我們知道在ARM架構中,地址0和地址1是完全不同的,修改地址0中的記憶體永遠不會修改地址1中的記憶體。以下為該函數可能生成的LLVM IR信息:

define i32 @foo(i32 addrspace(0)* %a, i32 addrspace(1)* %b) #0 {
entry:
  store i32 42, i32 addrspace(0)* %a, align 4
  store i32 20, i32 addrspace(1)* %b, align 4
 %0 = load i32, i32* %a, align 4
  ret i32 %0
}

第一個store將42存儲到變數a指向的地址,第二個store指令將20存儲到變數b指向的地址。%0 = ... 指向的行將變數a中的值載入到一個臨時變數0中,併在最後一行返回該臨時變數0。

上述代碼是未對foo函數進行優化的情況,下麵我們考慮對foo函數進行優化。

我們優化後的代碼可能如下:刪除了load指令對應的行,最後一行直接返回了常量42。

define i32 @foo(i32 addrspace(0)* %a, i32 addrspace(1)* %b) #0 {
entry:
  store i32 42, i32 addrspace(0)* %a, align 4
  store i32 20, i32 addrspace(1)* %b, align 4
  ret i32 42
}

然而,我們進行優化的時候需要仔細一些,因為上述優化僅在a和b指向的地址不會相互影響時有效。例如:當我們給foo函數傳遞的指針相互影響時:

int i = 0;
int result = foo(&i, &i);

在未開啟優化的版本中,變數i將先被設置為42,然後被設置為20,最後返回20。然而,在優化版本中,雖然我們執行了兩次store操作依次將42、20賦值給變數i,但是返回值是42,而不是20。因此優化版本破壞了foo函數本身的行為。

如果應用了別名分析,編譯器能夠合理的執行上述優化。在執行優化前判斷入參a和b是否為別名,如果是別名,則不執行刪除load指令對應行的操作,否則執行刪除操作。

4.2 實現

本文以LLVM16.0.0版本為參考,從代碼介面入手,帶領大家學習別名分析的代碼實現。

LLVM AliasAnalysis類是LLVM系統中客戶使用和別名分析實現的主要介面,或者說一個“基類” 。除了簡單的別名分析信息外,這個類還聲明瞭Mod/Ref信息,從而使強大的分析和轉換能夠很好地協同工作。

源碼參考鏈接:AliasAnalysis.h[3]、AliasAnalysis.cpp[4]。

4.2.1 基礎知識

MemoryLocation:LLVM中對記憶體地址的描述,主要應用在別名分析中,我們需要掌握該類中三個屬性:

其中,Ptr表示記憶體開始地址,Size表示記憶體大小,AATags是描述記憶體位置別名的metadata節點集合 。

4.2.2 AliasAnalysis Class 概覽

AliasAnalysis類定義了各種別名分析實現應該支持的介面。這個類導出兩個重要的枚舉:AliasResult和ModRefResult,它們分別表示別名查詢或mod/ref查詢的結果。

1、關鍵代碼如下,AliasAnalysis為AAResults類別名:

2、AliasResult關鍵代碼如下:

其中NoAlias表示兩個記憶體對象沒有任何重疊區域;MayAlias表示兩個指針可能指向同一對象;PartialAlias表示兩個記憶體對象對應的地址空間有重疊;MustAlias表示兩個記憶體對象總是從同一位置開始。

3、ModRefResult關鍵代碼

其中NoModRef表示訪問記憶體的操作既不會修改該記憶體也不會引用該記憶體; Ref表示訪問記憶體的操作會可能引用該記憶體;Mod表示訪問記憶體的操作可能會修改該記憶體;ModRef表示訪問記憶體的操作既可能引用該記憶體也可能修改該記憶體。

alias介面

其介面定義如下:

別名方法是用於確定兩個MemoryLocation對象是否相互別名的主要介面。它接受兩個MemoryLocation對象作為輸入,並根據需要返回MustAlias、PartialAlias、MayAlias或NoAlias。 與所有AliasAnalysis介面一樣,alias方法要求其入參的兩個MemoryLocation對象定義在同一個函數中,或者至少有一個值是常量。

其介面實現如下:

getModRefInfo 介面

getModReInfo方法返回關於給定的指令執行是否可以讀取或修改給定記憶體位置的信息。Mod/Ref信息具有保守性:如果一條指令可能讀或寫一個位置,則返回ModRef。 其介面定義眾多,我們以如下介面為例來進行學習。

其介面實現如下:

從上述代碼可知,處理共分為四步:

(1)遍歷AAs,如果發現其任一結果是NoModRef,則直接返回,對應代碼行228-234;

(2)調用節點(call)操作中是否訪問了一個在LLVM IR中無法訪問的地址,如果是的話,直接返回NoModRef,否則獲取其調用節點的ModRefInfo信息,對應代碼行239-240;

(3)處理調用節點中指針入參的ModRefInfo信息,如果發現是NoModRef,則直接返回NoModRef,否則將ModRefInfo信息和之前的結果合併,對應代碼行247-266;

(4)如果getModRefInfo函數中的入參Loc指定的記憶體地址具有常量屬性並且ModRefInfo信息包含Mod,則調用節點一定不會修改Loc記憶體,因此需要將Ref屬於與之前的結果做邏輯與操作,對應代碼行271-272。

4.2.3 LLVM中已經實現的別名分析

-basic-aa pass

-basic-aa pass是一種激進的本地分析,它提供許多重要的事實信息[5]:

  • 不同的全局變數、堆棧分配和堆分配永遠不能別名。
  • 全局變數、棧分配的變數和堆分配變數永遠不會和空指針別名。
  • 結構體中的不同欄位不能別名。
  • 同一數組,索引不同的兩個對象不能別名。
  • 許多通用的標準C庫函數從不訪問記憶體或只讀取記憶體。

-globals-aa pass

這個pass實現了一個簡單的對內部全局變數(該變數的地址沒有被獲取過)進行上下文敏感的mod/ref分析和別名分析。 如果某個全局變數的地址沒有被獲取,則該pass可以得出如下結論:沒有指針作為該全局變數的別名。該pass還會識別從不訪問記憶體或從不讀取記憶體的函數。這允許某些指定的優化(例如GVN)完全消除調用指令。

這個pass的真正威力在於它為調用指令提供了上下文敏感的mod/ref信息。這使優化器清楚的瞭解到對於某些函數的調用不會破壞或讀取全局變數的值,從而允許消除載入和存儲指令。

Note:該pass在使用範圍上有一定限制,僅支持沒有被取過地址的全局變數,但是該pass分析速度非常快。

除了上述pass外,LLVM中還實現了cfl-steens-aa、cfl-anders-aa、tbaa、scev-aa。目前LLVM中O1,O2,O3優化預設開啟的別名分析是basic-aa,globals-aa和tb-aa。

5.寫在最後

編譯器技術從20世紀50年代起,已經發展了近70年的歷史,但是編譯器技術發展到今天,依然是一個非常熱門的技術,各大硬體廠商都在開發自己的編譯器,包括因特爾推出的Inter C++、ARM公司推出的armclang以及華為推出的畢昇編譯器等,且上述三款編譯器都是基於LLVM開發。

編譯器技術是一門龐大且繁雜的技術,對於初學者來說,這條學習之路道阻且長,盼那些熱愛這門技術的趕路人能夠行而不輟,未來可期。

參考

[1]https://bbs.huaweicloud.com/blogs/234041

[2]https://blog.tartanllama.xyz/llvm-alias-analysis/

[3]https://llvm.org/doxygen/AliasAnalysis_8h_source.html

[4]https://llvm.org/doxygen/AliasAnalysis_8cpp_source.html

[5]https://llvm.org/docs/AliasAnalysis.html

 

點擊關註,第一時間瞭解華為雲新鮮技術~


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 本人的工作項目中,需求是: 點擊“列印”按鈕,打開pdf預覽彈出框,彈出框有:頭部選擇列印模板、列印方式、印表機,都是下拉選擇框;中部是pdf預覽塊;底部是確定列印。 準備工作: 預覽pdf,後端介面返回了pdf預覽地址,可線上直接打開。vue-pdf插件可以滿足需求。 選擇方式如果選擇本地列印,下 ...
  • 1.如果只比較兩個值的話 效果是這種的 // 這是<template>的 <el-row> <el-col :span="12"> <el-form-item label="計劃評審日期(起)" prop="planPsDateStart"> <el-date-picker v-model="vm. ...
  • 每日3題 1 以下代碼執行後,控制臺中的輸出內容為? // 以下代碼執行後,瀏覽器的控制臺中輸出的內容是什麼 var arr = [0, 1, 2]; arr[10] = 10; var newArr = arr.filter((x) => x undefined); console.log(new ...
  • 這裡給大家分享我在網上總結出來的一些知識,希望對大家有所幫助 uniapp上如何實現安卓app微信登錄功能?下麵本篇文章給大家分享一下uniapp上實現安卓app微信登錄的許可權申請、開發的具體操作流程,希望對大家有所幫助! 微信開放平臺提供了微信的一些開放介面,比如微信登錄、分享支付等,為其他各平臺 ...
  • 我的前端之旅。本節整合了"A Complete Guide to Flexbox"最新版本,介紹了flexbox的所有屬性,外帶幾個實用的例子。 ...
  • 如果你覺得 UITableViewDelegate 和 UITableViewDataSource 這兩個協議中有大量方法每次都是複製粘貼,實現起來大同小異;如果你覺得發起網路請求並解析數據需要一大段代碼,加上刷新和載入後簡直複雜度爆表,如果你想知道為什麼下麵的代碼可以滿足上述所有要求: 解耦後的V ...
  • 我的設計模式之旅,本節使用抽象工廠模式實現阿迪達斯、耐克品牌服飾生產,分別用C#跟Golang實現。對抽象方法模式進行了細緻的介紹。 ...
  • 享元模式(Flyweight Pattern)主要用於減少創建對象的數量,以減少記憶體占用和提高性能。這種類型的設計模式屬於結構型模式,它提供了減少對象數量從而改善應用所需的對象結構的方式。 ...
一周排行
    -Advertisement-
    Play Games
  • 隨著Aspire發佈preview5的發佈,Microsoft.Extensions.ServiceDiscovery隨之更新, 服務註冊發現這個屬於老掉牙的話題解決什麼問題就不贅述了,這裡主要講講Microsoft.Extensions.ServiceDiscovery(preview5)以及如何 ...
  • 概述:通過使用`SemaphoreSlim`,可以簡單而有效地限制非同步HTTP請求的併發量,確保在任何給定時間內不超過20個網頁同時下載。`ParallelOptions`不適用於非同步操作,但可考慮使用`Parallel.ForEach`,儘管在非同步場景中謹慎使用。 對於併發非同步 I/O 操作的數量 ...
  • 1.Linux上安裝Docken 伺服器系統版本以及內核版本:cat /etc/redhat-release 查看伺服器內核版本:uname -r 安裝依賴包:yum install -y yum-utils device-mapper-persistent-data lvm2 設置阿裡雲鏡像源:y ...
  • 概述:WPF界面綁定和渲染大量數據可能導致性能問題。通過啟用UI虛擬化、非同步載入和數據分頁,可以有效提高界面響應性能。以下是簡單示例演示這些優化方法。 在WPF中,當你嘗試綁定和渲染大量的數據項時,性能問題可能出現。以下是一些可能導致性能慢的原因以及優化方法: UI 虛擬化: WPF提供了虛擬化技術 ...
  • 引言 上一章節介紹了 TDD 的三大法則,今天我們講一下在單元測試中模擬對象的使用。 Fake Fake - Fake 是一個通用術語,可用於描述 stub或 mock 對象。 它是 stub 還是 mock 取決於使用它的上下文。 也就是說,Fake 可以是 stub 或 mock Mock - ...
  • 為.net6在CentOS7上面做準備,先在vmware虛擬機安裝CentOS 7.9 新建CentOS764位的系統 因為CentOS8不更新了,所以安裝7;簡單就一筆帶過了 選擇下載好的操作系統的iso文件,下載地址https://mirrors.aliyun.com/centos/7.9.20 ...
  • 經過前面幾篇的學習,我們瞭解到指令的大概分類,如:參數載入指令,該載入指令以 Ld 開頭,將參數載入到棧中,以便於後續執行操作命令。參數存儲指令,其指令以 St 開頭,將棧中的數據,存儲到指定的變數中,以方便後續使用。創建實例指令,其指令以 New 開頭,用於在運行時動態生成並初始化對象。方法調用指... ...
  • LiteDB 是一個輕量級的嵌入式 NoSQL 資料庫,其設計理念與 MongoDB 類似,但它是完全使用 C# 開發的,因此與 C# 應用程式的集成非常順暢。與 SQLite 相比,LiteDB 提供了 NoSQL(即鍵值對)的數據存儲方式,並且是一個開源且免費的項目。它適用於桌面、移動以及 We ...
  • 1 開源解析和拆分文檔 第三方的工具去對文件解析拆分,去將我們的文件內容給提取出來,並將我們的文檔內容去拆分成一個小的chunk。常見的PDF word mark down, JSON、HTML。都可以有很好的一些模塊去把這些文件去進行一個東西去提取。 優勢 支持豐富的文檔類型 每種文檔多樣化選擇 ...
  • OOM是什麼?英文全稱為 OutOfMemoryError(記憶體溢出錯誤)。當程式發生OOM時,如何去定位導致異常的代碼還是挺麻煩的。 要檢查OOM發生的原因,首先需要瞭解各種OOM情況下會報的異常信息。這樣能縮小排查範圍,再結合異常堆棧、heapDump文件、JVM分析工具和業務代碼來判斷具體是哪 ...