對於LLVM之類的編譯器是如何實現在構造SSA形式的IR的時候，計算出def-use鏈？

在做基於SSA形式的優化的時候，發現def-use鏈和use-def是基本的問題，我找到的資料基本上都僅僅只是採用傳統的數據流方法——擴展的liveness analysis演算法，https://www.cs.rice.edu/~keith/512/2009Lectures/11DUChains.pdf，而我想要知道的是如何從AST構造SSA形式的中間代碼的時候，計算出指令的def-use鏈。

——————————————————————————————————

麻煩各位了！！！，如果內容多，只需要給個LLVM中的文件名或者論文即可，謝謝！

——————————————————————————————————

更新：我已經有了初步的思路，不知是否正確，按照LLVM的IR的構造方式，將所有的原始程序

中的變數都視作存儲在內存中，每次讀取的時候，採用load指令，對其寫入採用store指令，見下面的代碼：

int main(void)
{
int a;
int b;
int c;
a = 42;
b = a;
c = a + b;
a = c + 23;
c = a + 1;
return 0;
}


其生成的LLVM彙編如下：

define void @fun() #0 {
entry:
%a = alloca i32, align 4
%b = alloca i32, align 4
%c = alloca i32, align 4
// 下面是變數內容讀取
store i32 2, i32* %a, align 4
store i32 1, i32* %b, align 4
// 讀取
%0 = load i32, i32* %a, align 4
%1 = load i32, i32* %b, align 4
// 運算
%add = add nsw i32 %0, %1

store i32 %add, i32* %c, align 4
%2 = load i32, i32* %b, align 4
%add1 = add nsw i32 %2, 1
store i32 %add1, i32* %b, align 4
ret void
}


比如，在執行 c = a + b的時候，分別使用%0 = load i32, i32* %a, align 4和%1 = load i32, i32* %b, align 4讀取a與b之後，在執行a + b 的時候就可以給%0和%1的user集合添加%add指令了。

不知該方法是否正確？

——————————————————————————————————————

更新：R大回復的第二部分也就是我剛剛好做了一個一個閱讀筆記，LLVM的提升流程，我放在我下面的回答了。

---

題主的問題其實是兩個問題。或者說我知道題主關心的其實是後者，但這問題的表述方式看起來像前者：

1. 在創建SSA形式的LLVM IR時，SSA value之間的def-use信息是如何建立的？

2. 在把alloca/load/store表達的局部變數提升為SSA value時，LLVM是如何分析出def-use關係的？

1. SSA value之間的def-use信息是如何建立的？

那麼先看前者。假定我們的IR已經是SSA形式的了，只是要建立SSA value之間的def-use/use-def關係。

很簡單，LLVM IR中的SSA value的def-use與use-def信息其實是用同一套雙向引用來維護的。所以說只要A use了B，A與B之間的use-def與def-use關係就同時建立好了。

這個維護雙向引用的數據結構叫做「Use」。LLVM官方文檔對其有很不錯的介紹：LLVM Programmer"s Manual: The User and owned Use classes" memory layout

請讀完這塊文檔再繼續讀下文。

有趣的是，這種「Use」結構在V8 TurboFan和Adobe Flash VM的Halfmoon編譯器里都有應用：

• V8 TurboFan：v8/node.h at master · v8/v8 · GitHub
• Halfmoon：avmplus/hm-instrgraph.h at master · adobe/avmplus · GitHub

舉例來說，假如我們要創建一個Add指令，BinaryOperator::CreateAdd(Value *V1, Value *V2, const Twine Name)，這條新創建的Add（BinaryOperator）指令是如何跟它的兩個輸入（V1、V2）建立起def-use/use-def聯繫的呢？請看下面的代碼：

class Value {
void addUse(Use U) { U.addToList(UseList); }

// ...
};

class Use {
Value *Val;
Use *Next;
PointerIntPair& Prev;

// ...
};

void Use::set(Value *V) {
if (Val) removeFromList();
Val = V;
if (V) V-&>addUse(*this);
}

Value *Use::operator=(Value *RHS) {
set(RHS);
return RHS;
}

class User : public Value {
template & static Use OpFrom(const U *that) {
return Idx &< 0 ? OperandTraits&::op_end(const_cast&(that))[Idx]
: OperandTraits&::op_begin(const_cast&(that))[Idx];
}
template & Use Op() {
return OpFrom&(this);
}
template & const Use Op() const {
return OpFrom&(this);
}

// ...
};

class Instruction : public User,
public ilist_node_with_parent& {
// ...
};

class BinaryOperator : public Instruction {
/// Construct a binary instruction, given the opcode and the two
/// operands. Optionally (if InstBefore is specified) insert the instruction
/// into a BasicBlock right before the specified instruction. The specified
/// Instruction is allowed to be a dereferenced end iterator.
///
static BinaryOperator *Create(BinaryOps Op, Value *S1, Value *S2,
const Twine Name = Twine(),
Instruction *InsertBefore = nullptr);

// ...
};

BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
Type *Ty, const Twine Name,
Instruction *InsertBefore)
: Instruction(Ty, iType,
OperandTraits&::op_begin(this),
OperandTraits&::operands(this),
InsertBefore) {
Op&<0&>() = S1;
Op&<1&>() = S2;
init(iType);
setName(Name);
}

BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
const Twine Name,
Instruction *InsertBefore) {
assert(S1-&>getType() == S2-&>getType()
"Cannot create binary operator with two operands of differing type!");
return new BinaryOperator(Op, S1, S2, S1-&>getType(), Name, InsertBefore);
}


從BinaryOperator的構造器開始看，會看到裡面有：

Op&<0&>() = S1;
Op&<1&>() = S2;


的看起來很有趣的代碼。追溯源頭會來到Use::set(Value *V)，這裡就藉助Use對象來把def與use的雙向引用給聯繫起來了。

2. alloca/load/store形式的局部變數是如何進入SSA形式的？

關鍵詞：mem2reg pass

源碼：

lib/Transforms/Utils/Mem2Reg.cpp

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

這個第二部分的本質其實是：假定我們的IR其實還不是SSA形式的，如何把它轉成SSA形式的IR。這包括計算Phi節點的安插位置（Phi insertion），以及計算變數版本/變數重命名（variable renaming）。

LLVM IR雖然是SSA形式的，但如果所有生成LLVM IR的前端都要自己計算好如何生成SSA形式，對前端來說也是件麻煩事。

所以LLVM IR藉助「memory不是SSA value」的特點來開了個後門來妥協：前端在生成LLVM IR時，可以選擇不生成真正的SSA形式，而是把局部變數生成為alloca/load/store形式：

• 用alloca來「聲明」變數，得到一個指向該變數的指針；
• 用store來把值存進變數里；
• 用load來把值讀出為SSA value。

這樣，對局部變數的讀寫就跟對普通內存的讀寫一樣，不需要是SSA形式的。

然後，LLVM在mem2reg pass中，會識別出這種模式的alloca，並把它提升為SSA value（並消除掉store與load，改為普通的SSA層面的def-use/use-def關係，並且在合適的位置安插Phi和變數重命名）。

Clang就是這樣把生成SSA形式的任務交給LLVM處理的：Clang的前端只會把某些臨時值生成為SSA value；對顯式的局部變數，Clang前端都只是生成alloca/load/store形式的LLVM IR。

交給LLVM之後，經過mem2reg pass，IR才真正進入了普通的SSA形式。

LLVM Tutorial也提到了這點：7. Kaleidoscope: Extending the Language: Mutable Variables

例如說這樣的函數：

int foo(int x, bool cond) {
int inc;
if (cond) {
inc = 1;
} else {
inc = -1;
}
return x + inc;
}


Clang的前端生成的LLVM IR是：

; Function Attrs: nounwind uwtable
define i32 @_Z3fooib(i32 %x, i1 zeroext %cond) #0 {
entry:
%x.addr = alloca i32, align 4
%cond.addr = alloca i8, align 1
%inc = alloca i32, align 4
store i32 %x, i32* %x.addr, align 4
%frombool = zext i1 %cond to i8
store i8 %frombool, i8* %cond.addr, align 1
%0 = load i8, i8* %cond.addr, align 1
%tobool = trunc i8 %0 to i1
br i1 %tobool, label %if.then, label %if.else

if.then: ; preds = %entry
store i32 1, i32* %inc, align 4
br label %if.end

if.else: ; preds = %entry
store i32 -1, i32* %inc, align 4
br label %if.end

if.end: ; preds = %if.else, %if.then
%1 = load i32, i32* %x.addr, align 4
%2 = load i32, i32* %inc, align 4
%add = add nsw i32 %1, %2
ret i32 %add
}


可以看到局部變數都在函數的最開頭（entry block）有對應的alloca來「聲明」它們——申請棧上空間。後面賦值的地方用store、取值的地方用load指令，就跟操作普通內存一樣。

而經過mem2reg之後它才真正進入了SSA形式：

; Function Attrs: nounwind uwtable
define i32 @_Z3fooib(i32 %x, i1 zeroext %cond) #0 {
entry:
%frombool = zext i1 %cond to i8
%tobool = trunc i8 %frombool to i1
br i1 %tobool, label %if.then, label %if.else

if.then: ; preds = %entry
br label %if.end

if.else: ; preds = %entry
br label %if.end

if.end: ; preds = %if.else, %if.then
%inc.0 = phi i32 [ 1, %if.then ], [ -1, %if.else ]
%add = add nsw i32 %x, %inc.0
ret i32 %add
}


可以看到進入SSA形式後的LLVM IR里，那些局部變數就變成了普通的SSA value，而不再需要alloca/load/store了。

LLVM的mem2reg pass本質上就是識別「局部變數」的模式，並對它們構建SSA形式。

它用的演算法也很常規——經典的Lengauer-Tarjan的iterated dominance frontier演算法。

mem2reg的演算法有同學寫過簡介，我懶就不重複了：https://www.cs.rice.edu/~mc29/Milind/Publications_files/report_1.pdf

1. LLVM assumes that all locals are introduced in the entry basic block of a function with an alloca instruction. LLVM also assumes that all allocas appear at the start of the entry block continuously. This assumption could be easily violated by the front-end, but it is a reasonable assumption to make.
2. For each alloca seen in step 1, LLVM checks if it is promotable based on the use of this local. It is deemed promotable iff:

1. (a) It is not used in a volatile instruction.
2. (b) It is loaded or stored directly, i.e, its address is not taken.
3. For each local selected for promotion in step 2, a list of blocks which use it, and a list of block which define it are maintained by making a linear sweep over each instruction of each block.

4. Some basic optimizations are performed:

1. (a) Unused allocas are removed.
2. (b) If there is only one defining block for an alloca, all loads which are dominated by the definition are replaced with the value.
3. (c) allocas which are read and written only in a block can avoid traversing CFG, and PHI-node insertion by simply inserting each load with the value from nearest store.
5. A dominator tree is constructed.

6. For each candidate for promotion, points to insert PHI nodes is computed as follows:

1. (a) A list of blocks which use it without defining it (live-in blocks or upward exposed blocks) are determined with the help of using and defining blocks created in Step 3.
2. (b) A priority queue keyed on dominator tree level is maintained so that inserted nodes corresponding to defining blocks are handled from the bottom of the dominator tree upwards. This is done by giving each block a level based on its position in the dominator tree.
3. (c) For each node — root, in the priority queue:
1. i. Iterated dominance frontier of a definition is computed by walking all dominator tree children of root, inspecting their CFG edges with targets elsewhere on the dominator tree. Only targets whose level is at most root level are added to the iterated dominance frontier.
2. ii. PHI-nodes are inserted at the beginning in each block in the iterated dominance frontier computed in the previous step. There will be predecessor number of dummy argument to the PHI function at this point.
7. Once all PHI-nodes are prepared, a rename phase start with a worklist containing just entry block as follows:

1. (a) A hash table of IncomingVals which is a map from a alloca to its most recent name is created. Most recent name of each alloca is an undef value to start with.
2. (b) While (worklist != NULL)
1. i. Remove block B from worklist and mark B as visited.
2. ii. For each instruction in B:
1. A. If instruction is a load instruction from location L (where L is a promotable candidate) to value V, delete load instruction, replace all uses of V with most recent value of L i.e, IncomingVals[L].
2. B. If instruction is a store instruction to location L (where L is a promotable candidate) with value V, delete store instruction, set most recent name of L i.e, IncomingVals[L] = V.
3. C. For each PHI-node corresponding to a alloca — L , in each successor of B, fill the corresponding PHI-node argument with most recent name for that location i.e, IncomingVals[L].
3. iii. Add each unvisited successor of B to worklist.

嗯先就寫這麼多。

---

我就接著R大的部分粗淺的補充下，LLVM IR的def-use鏈，是通過Use對象來管理的，R大說的是最新的LLVM IR中def-use鏈的構造情況，我先補充一下早期的LLVM IR中def-use的構造方式，然後再補充下最新的LLVM IR中def-use鏈構造時的源碼形式。

1.LLVM 1.3中def-use鏈的構造

我以BinaryOperator為例，下面是LLVM 1.3中class Value的源碼：

class Value;
class User;
class Use {
Value *Val;
User *U;
Use *Prev, *Next;
public:
Value *get() const { return Val; }
User *getUser() const { return U; }
};
// 每次創建一個新的Use對象時，就會將Use對象掛載到Value的Uses鏈表上
// 由於每次Use對象的創建都是在User端進行的，所以User端創建Use對象時，就會將該對象掛載到
// Value的User鏈表上。
Use::Use(Value *v, User *user) : Val(v), U(user) {
if (Val) Val-&>addUse(*this);
}

~Use::~Use() {
if (Val) Val-&>killUse(*this);
}


從上述代碼中可以看出，Use對象一頭連接著 User(所有Instruction都繼承自User)，一頭連接著Value，然後這些Use對象以鏈表的形式組織起來。每次創建一個新的Use對象時，就會調用構造函數將當前的Use對象掛在到Val的Uses鏈表上。如下圖所示：

指令 "%add = add nsw i32 %tmp, 10" 用到了值 "%tmp"，所以兩者可以使用Use對象勾連起來。下面是Use對象在User 和 Value中的存在形式。

struct Value {
private:
PATypeHolder Ty;
// 每個Value都有可能被其他User用到，使用iplist來組織Use Object
iplist& Uses;
std::string Name;
public:
// addUse/killUse - These two methods should only used by the Use class.
void addUse(Use U) { Uses.push_back(U); }
void killUse(Use U) { Uses.remove(U); }
User *use_back() { return Uses.back().getUser(); }
// ...
};

struct User : public Value {
// 相對應的，User使用vector來組織Use Object
std::vector& Operands;
public:
typedef std::vector&::iterator op_iterator;
unsigned getNumOperands() const { return Operands.size(); }
void op_reserve(unsigned NumElements) { Operands.reserve(NumElements); }
op_iterator op_begin() { return Operands.begin(); }
// ...
};

class Instruction : public User {
BasicBlock *Parent;
Instruction *Prev, *Next;
// ...
};

class BinaryOperator : public Instruction {
protected:
void init(BinaryOps iTyps, Value *S1, Value* S2);

BinaryOperator(BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
const Type *Ty, const std::string Name, Instruction *InsertBefore)
: Instruction(Ty, iType, Name, InsertBefore) {
init(iType, S1, S2);
}
BinaryOperator(BinaryOps iType, Value *S1, Value *S2, const Type *Ty,
const std::string Name, BasicBlock *InsertAtEnd)
: Instruction(Ty, iType, Name, InsertAtEnd) {
init(iType, S1, S2);
}
};

//===-----------------------------------------------------------------===//
// BinaryOperator class
//===-----------------------------------------------------------------===//
void BinaryOperator::int(BinaryOps iType, Value *S1, Value *S2)
{
Operands.reserve(2);
Operands.push_back(Use(S1, this));
Operands.push_back(Use(S2, this));
// ...
}


下圖所示是LLVM 1.3中 BinaryOperator對象的內存布局：

BinaryOperator既有可能被別的User用到，也一定會用到別的Value。BinaryOperator通過使用 "Uses"鏈表來維護有可能會被哪些User用到， 通過vector "Operands"來維護用到的Value值，注意BinaryOperator會被哪些User用到是未知不確定的，所以用節點數量靈活的鏈表來組織比較合適，相對應的，BianaryOperator需要用到的Value對象數量是確定的，所以使用可以手動設定size值的vector實現。注意這一點在代碼中也有體現，例如:BinaryOperator中的init函數中調用了「Operands.reserve(2)」來設置Operands的capacity為2。關於如何在IR build時建立起這種def-use關係，是在BinaryOperator初始化函數中實現的，通過

Operands.push_back(Use(S1, this));
Operands.push_back(Use(S1, this));


實現的，在創建一個新的BinaryOperator指令的時候，Create() -&> BinaryOperator() -&> init() ，在init()函數中構造一個新的Use對象來維護def-use關係。前面曾經提到過，每次創建一個新的Use對象時，就通過Use的構造函數將Use對象掛載到Value的Uses鏈表上。如下示例代碼：

int add()
{
int start = 10;
int end = 10;
return start + end;
}


%start會被用到兩次，一次是賦值"int start = 10;"，一次是加法操作"return start + end;"

%start = alloca i32, align 4 ; & [#uses=2]
%end = alloca i32, align 4 ; & [#uses=2]
store i32 10, i32* %start ; use %start
store i32 10, i32* %end ; use %end
%tmp = load i32* %start ; use %start
%tmp1 = load i32* %end ; use %end
%add = add nsw i32 %tmp, %tmp1


在遍歷到「int start = 10;」，首先會創建一個alloca指令，然後判斷是否有init expression，有init expression，則EmitExpr(InitE)得到一個Value，最後創建一個Store指令將Value值存儲到alloca指令指定的位置。在創建store指令的時候會創建一個新的Use對象（在創建的同時將該Use對象掛載到Alloca指令的Uses鏈表中），然後將該Use對象push到自己的Operands vector中。如下圖所示：

Use對象中的Prev Next是以Val為主線來索引的，例如我們從 "%start = alloca i32, allign 4"的Uses數據成員，就可以索引到所有的使用 "%start = alloca i32, align 4"。而Operands直接遍歷vector就可獲得use的Value。

LLVM 1.3中的def-use很簡單，但是現在的LLVM 3.7的實現已經很複雜了，主要區別在於Use對象是否包括"User *U"數據成員以及在User中的放置方式。

2. LLVM 3.6

R大已經給出了如今LLVM的def-use的構造方式，也給出了LLVM Programmer』s Manual 這個網址，這裡面有兩幅圖示描述了User與Use之間的關係。

...---.---.---.---.-------...
| P | P | P | P | User
"""---"---"---"---"-------"""


第一種 "The Use object(s) are inside (resp. at fixed offset) of the User object and there are a fixed number of them." 也就是說User中的Operands不像LLVM 1.3中將Operands作為數據成員放在User對象中，而是直接放在User對象的前面，是固定長度的。為了實現這樣的形式，就需要重載new運算符，來手動修改內存分配的方式。

class User : public Value {
protected:
Use *OperandList;
// 以User首地址為基準，來獲取下標Idx的操作數
template & static Use OpFrom(const U *that) {
return Idx &< 0 ? OperandTraits&::op_end(const_cast&(that))[Idx] :
OperandTraits&::op_begin(const_cast&(that))[Idx];
}
// Op&<&>()是Instruction獲取Operand的通用介面
template & Use Op(){
return OpFrom&(this);
}
}
void *User::operator new(size_t s, unsigned Us) {
// 除了分配User大小的內存空間以外，還分配了固定個數Use大小的內存空間
void *Storage = ::operator new(s + sizeof(Use) * Us);
// Operands 頭部
Use *Start = static_cast&(Storage);
// Operands 尾部
Use *End = Start + Us;
// Operands 尾部作為User首地址（this）
User *Obj = reinterpret_cast&(End);
Obj-&>OperandList = Start;
Obj-&>NumOperands = Us;
Use::initTags(Start, End);
return Obj;
}


在創建一個新的User對象的時候，會調用重載的new()函數，來分配內存空間，我們還是以BinaryOperator為例。

class BinaryOperator : public Instruction {
// ...
public:
void *operator new(size_t s) {
return User::operator new(s, 2);
}
};

BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2, Type *Ty,
const Twine Name, Instruction *InsertBefore)
: Instruction (Ty, iType, OperandTraits&::op_begin(this),
OperandTraits&::operands(this), InsertBefore) {
Op&<0&>() = S1;
Op&<1&>() = S2;
// ...
}


BinaryOperator中的operator new()調用User::new(s, 2)，分配內存時，分配BinaryOperator對象的大小加上2個Use對象大小的內存。後面在BinaryOperator的構造函數中，使用了"Op&<0&>() = S1;"以及"Op&<1&>() = S2;"來將Value存放到Operands中。BinaryOperator中Use對象存放方式如下：

.------.------.-------...
| P, 0 | P, 1 | User
"------"------"-------"""


下面分析 "Op&<0&>" 以及 "Op&<1&>" ，先給出OperandTraits的定義：

template &
struct FixedNumOperandTraits {
// 上面在User::OpFrom()，我們就是通過op_begin()獲取Operands的首地址，然後通過
// 下標運算符[Idx]，來獲取操作數，而固定長度Operands的首地址就是 SubClass首地址
// 減去 ARITY 個Use對象長度的地址（例如BinaryOperator中ARITY就是2）。
static Use *op_begin(SubClass* U) {
return reinterpret_cast&(U) - ARITY;
}
static Use *op_end(SubClass* U) {
return reinterpret_cast&(U);
}
}

template&<&>
struct OperandTraits& :
public FixedNumOperandTraits& {
};


我們可以看到OperandTraits&繼承的是FixedNumOperandTraits，就是第一種固定長度的形式，Operand begin就是BinaryOperator首地址減去2個Use對象大小的位置。

在創建BinaryOperator時，會首先調用 new() 分配一塊內存空間，然後調用BinaryOperator構造函數，在函數中通過 "Op&<0&>() = S1;"以及"Op&<1&> = S2;"來將Value放置在BinaryOperator對象的頭部，如下圖所示：

.------.------.-------...
| S1 | S2 | User
"------"------"-------"""


在執行 "Op&<0&> = S1"時，會調用 Use::operator=()函數：

class Use {
Value *operator=(Value *RHS) {
set(RHS);
return RHS;
}
// 類似於LLVM1.3，set()函數也會把該Use對象掛載到Value的Uses鏈表上
set(Value *V)
{
if (Val) removeFromList();
Val = V;
if (V) V-&>addUse(*this);
}
private:
Value *Val;
Use *Next;
PointerIntPair& Prev;
};


也就是每次初始化一個新的Use對象時（也就是調用operator=()時），都會將該Use對象掛載在Value的鏈表上，同樣，Use中的Next和Prev是以Value為主線來進行連接的，也就是說如果兩個Use對象使用了同一個Value值，那麼這兩個Use對象肯定都在同一條鏈表上。如下圖所示：

Use對象放在User對象的頭部，Value可以通過UseList來索引所有的Use對象，也可以通過Use對象來索引到User對象，由於Use對象沒有存放指向User的數據成員，不能直接獲得，但是由於Use對象存放在User對象的頭部，我們還是可以獲取到User地址的（這個過程有點兒瑣碎，我就不貼代碼了 :)關於第二種方式，就是變長Operands方式，這種方式通過在調用User::new()時，傳遞不同的參數，來分配出不同的內存，內存分配函數和第一種方式相同，Use對象也是分配在User對象的頭部。只是在通過Op&()來獲取Use對象的時候是通過Use Array[]的尾部來獲取的，例如：Op&<-1&>()或者Op&<-3&>()等。無聊的代碼已經很多了，就不再貼了。。。

---

上面R大已經說了我想要知道的第一部分了，也就是LLVM是如何在構造SSA形式的IR的時候，建立def-use鏈。

第二部分我以前看的時候，做了一些閱讀筆記，有什麼錯誤的話，請提示我，謝謝！

下面的代碼是我使用Java根據LLVM的代碼重寫的。

// promotes every alloca instruction one by one.
for (Alloca AI : allocas)
{
// 判斷是否可以提升
assert AI.isAllocaPromoteable()

// 跳過無使用者的alloca指令

// 收集alloca指令的使用，定義信息
info.analyzeAlloca(AI);

// 下面的函數，對只有一次定義（即只有一條store指令）的alloca進行優化
// if there is only a single store to this value, this is said
// that there is only a single definition of this variable.
// replace any loads of it that are directly dominated by the
// definition with the value stored.
if (info.definingBlocks.size() == 1)
{
rewriteSingleStoreAlloca(AI, info, LBI, DT))
}

// 下面的代碼僅僅對只在一個基本塊中使用和定義的alloca指令進行優化
// If the alloca is only read and written in one block.
// just perform a linear scan sweep over the block to
// eliminate it.
if (info.onlyUsedOneBlock)
{
promoteSingleBlockAlloca(AI, info, LBI);
}

// 插入無參數的Phi函數，使用標準的基於支配邊界的演算法，其中使用DJ圖的方式進行了優化
// Using standard SSA construction algorithm to promoting the alloca.
// Determine which blocks need PHI nodes and see if we can optimize out
// some work by avoiding insertion of dead phi nodes.
determineInsertionPoint(AI, allocaNum, info);

// 使用一個工作流演算法，對插入的Phi函數設置輸入參數，同時進行重命名操作
// wolk all basic block in the function performing
// SSA construction algorithm and inserting the phi nodes
// we marked as necessary.

// 最後執行一趟消除平凡Phi函數的操作，
while (eliminatedAPHI)
{
// if the phi merges one value and/or undefs, get the value
if ((V = simplifyInstruction(phi, DT)) != null)
{
phi.replaceAllUsesWith(V);
phi.eraseFromBasicBlock();
newPhiNodes.remove(entity);
eliminatedAPHI = true;
continue;
}
}


---

IR裡面的Use list是一種關係的表示，真正後端需要的UD Chain還是需要經過liveness（數據流）分析。

---

推薦閱讀：