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

来源: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
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...