-
-
[原创]OLLVM控制流平坦化之fixStack解析
-
2021-8-6 11:06
11708
-
[原创]OLLVM控制流平坦化之fixStack解析
在我之前的文章 基于LLVM Pass实现控制流平坦化 中漏掉了对控制流平坦化里一个很重要的函数fixStack
的解释。后来我发现fixStack
这个函数中蕴含的一些原理也是自己在编写 Pass 时需要面对的问题,也是初学LLVM最容易迷惑的一个地方,还是决定补充说明一下。
首先贴上我重构之后的fixStack
函数,该函数较OLLVM中的fixStack
函数有所区别,大家自行比较:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | void llvm::fixStack(Function &F) {
vector<PHINode * > origPHI;
vector<Instruction * > origReg;
do{
origPHI.clear();
origReg.clear();
BasicBlock &entryBB = F.getEntryBlock();
for (BasicBlock &BB : F){
for (Instruction &I : BB){
if (PHINode * PN = dyn_cast<PHINode>(&I)){
origPHI.push_back(PN);
} else if (!(isa<AllocaInst>(&I) && I.getParent() = = &entryBB)
&& I.isUsedOutsideOfBlock(&BB)){
origReg.push_back(&I);
}
}
}
for (PHINode * PN : origPHI){
DemotePHIToStack(PN, entryBB.getTerminator());
}
for (Instruction * I : origReg){
DemoteRegToStack( * I, entryBB.getTerminator());
}
} while (!origPHI.empty() || !origReg.empty());
}
|
从整体上看这个函数处理了两类指令:
什么是PHI指令呢,对LLVM有所研究的话应该都比较熟悉,控制流平坦化会打乱基本块之间的前后关系,PHI指令又是基于前驱块的指令,前驱块被打乱了PHI指令肯定会出现错误,因此我们要对PHI指令进行修复。
修复的方法是调用DemotePHIToStack
这个函数。Demote是降级的意思,DemoteToStack
就是用alloca, store, load三类内存访问指令来代替之前的PHI指令。为什么是Stack呢,因为LLVM IR中的alloca指令是在栈中进行分配的,这点不同于C语言中的malloc
函数。将所有PHI指令用三类内存访问指令表示,并将所有alloca指令都放在入口块,PHI指令的错误就被修复了。
再来看看第二类情况,逃逸变量指的是在当前基本块中被定义,并且在其他的基本块中被引用了的变量。还是因为控制流平坦化会打乱基本块之间的前后关系,这类逃逸变量在编译(LLVM IR->目标平台机器代码)时会出现分不清定义和引用顺序的问题,因此也需要进行修复。
修复的方法是调用DemoteRegToStack
这个函数。Reg是什么意思呢,这里的Reg是寄存器Register的缩写,LLVM IR中所有本地变量都称做“虚拟寄存器”,所以这里是DemoteReg。
1 | isa<AllocaInst>(&I) && I.getParent() = = &entryBB
|
这段代码用来判断当前指令是否是alloca指令,并且是否位于函数入口块,该类指令不算是逃逸变量,所以不做处理(因为修复逃逸变量就是靠入口块的alloca指令和store, load指令)。
1 | I.isUsedOutsideOfBlock(&BB)
|
这段代码则是判断当前指令是否在除当前基本块以外的基本块被使用,成立则为逃逸变量,需要调用DemoteRegToStack
函数进行处理。
比较OLLVM中的fixStack
函数和我在上面贴的fixStack
函数后就会发现,OLLVM中的fixStack
函数还引用了一个valueEscape
函数:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | bool valueEscapes(Instruction * Inst) {
BasicBlock * BB = Inst - >getParent();
for (Value::use_iterator UI = Inst - >use_begin(), E = Inst - >use_end(); UI ! = E;
+ + UI) {
Instruction * I = cast<Instruction>( * UI);
if (I - >getParent() ! = BB || isa<PHINode>(I)) {
return true;
}
}
return false;
}
...
if (!(isa<AllocaInst>(j) && j - >getParent() = = bbEntry) &&
(valueEscapes(& * j) || j - >isUsedOutsideOfBlock(& * i))) {
...
|
valueEscapes
函数是用来判断指令使用的操作数中是否包含逃逸变量以及PHINode,但事实上修复PHI指令和逃逸变量的DemotePHIToStack
以及DemoteRegToStack
两个函数在修复当前指令的同时还会修复所有引用了当前指令的指令(详见llvm/lib/Transforms/Utils/DemoteRegToStack.cpp源代码),因此我觉得valueEscape
函数有点多余,不知道我的想法是否正确,如果有误欢迎大家指正。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界