首页
社区
课程
招聘
[原创]OLLVM控制流平坦化之fixStack解析
2021-8-6 11:06 11708

[原创]OLLVM控制流平坦化之fixStack解析

2021-8-6 11:06
11708

在我之前的文章 基于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指令
  • 第二类是逃逸变量

什么是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世界

收藏
点赞6
打赏
分享
最新回复 (2)
雪    币: 878
活跃值: (496)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
Rprop 2021-8-6 22:17
2
0
是的,其实不需要自己fix,直接用
DemoteRegisterToMemoryPass即可。不过,作者实现ollvm时基于llvm4,相比现在llvm13已将近十个版本的迭代,可能早期时各种接口和文档都不甚完善。
雪    币: 2954
活跃值: (3345)
能力值: ( LV3,RANK:35 )
在线值:
发帖
回帖
粉丝
AshCrimson 2023-6-1 00:05
3
0
我不太能够理解为什么当前指令在其他基本块中使用,就是逃逸变量了.
游客
登录 | 注册 方可回帖
返回