静态测试—基于WorkList的活跃变量分析

csdn推荐

本文主要用于记录在活跃变量分析实验中的报错及解决,涉及静态测试的详细原理内容较少,编译运行底层逻辑偏多。

一、实验要求

1)使用llvm基于框架实现一个基于WorkList的活跃变量分析demo。变量在某个程序点有两种状态,live 或 dead。对于变量 x 和程序点 p,判断 x 在点 p 上的值是否会在 CFG 中的某条从点 p 出发的路径中使用。如果是,就说 x 在 p 上 live;否则就说x在p上是 dead。

目前本实验假设的输入程序当中只有整型变量(即,没有浮点、指针、结构、枚举、数组等)。

即实现LivenessAnalysis中的如下函数:

这些函数对应如下Worklist算法当中的如下四个部分:

活跃变量分析为后向的数据流分析,本实验实现的demo将通过一个Worklist的大循环对LLVM IR当中的每条指令进行活跃变量的计算,其中计算的结果将以llvm::BitVector的形式存储在std::map INSetOUTSet当中。

上述输出为最终预期的输出结果,其中右侧为每个指令对应的活跃变量分析结果,以 [ INSet[inst] –> OUTSet[inst] ]形式表现,且由于是后向分析,所以最后右侧的输出结果是从下到上的形式表现的。

二、实验内容: 2.1实验环境: 2.1.1环境配置:

安装LLVM 10.0.1:

##llvm10.0.1安装wget -zxvf llvmorg-10.0.1.tar.gzcd llvm-projectmkdir build cd buildcmake -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS=”clang” -G “Unix Makefiles” -DCMAKE_INSTALL_PREFIX=llvm_install_dir ../llvmmake -j 4 ##4为编译运行时的线程数sudo make install ##若未安装到默认目录当中,需要在~/.bashrc当中添加路径:sudo gedit ~/.bashrc##在文本末尾添加:export PATH=”$PATH:llvm_install_dir/bin”##更新shell:source ~/.bashrc

安装完环境后,在实验框架目录下执行以下指令编译运行:

mkdir buildcd buildcmake ..make

若能够编译成功,你将在build目录下见到LivenessPass.so。 之后在test目录下运行./auto.sh test01得到以下输出:

Running Liveness on mainBitVec map:Liveness Analysis Result:%retval = alloca i32, align 4: [ –> ]%a = alloca i32, align 4: [ –> ]%b = alloca i32, align 4: [ –> ]%c = alloca i32, align 4: [ –> ]%d = alloca i32, align 4: [ –> ]store i32 0, i32* %retval, 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* %d, align 4: [ –> ]%2 = load i32, i32* %d, align 4: [ –> ]store i32 %2, i32* %b, align 4: [ –> ]%3 = load i32, i32* %a, align 4: [ –> ]store i32 %3, i32* %c, align 4: [ –> ]ret i32 0: [ –> ] 2.1.2环境情况:

Ubuntu:

Linux:

Llvm:

2.2 flowIn实现:

2.2.1文件框架:

// Inst:当前处理的Inst; InVec:当前处理的Inst的前一轮分析的Input Bitvector
 void LivenessPass::flowIn(Instruction *Inst, BitVector InVec) {
 ///TODO 将所有上一个Inst(由于是后向分析,所以是当前Inst的后继Inst)的Output Bitvector进行join操作作为当前Inst的Input Bitvector
  auto  successors = getSuccessors(Inst);
    BitVector InputVec = InVec;
  // 遍历后继指令,并进行合并操作
  for (auto successor : successors) {
    BitVector OutputVec = OUTSet[successor];
    InputVec |= OutputVec;
  }
  INSet[Inst] = InputVec;
  // 将合并后的结果设置为当前指令的输入位向量
}

这是一个成员函数,用于计算指定指令Inst的输入位向量InVec。输入位向量InVec表示在Inst执行之前活跃的变量集合。函数的目标是将所有Inst的后继指令的输出位向量进行合并(join操作),得到Inst的输入位向量。

获取Inst的所有后继指令。在控制流图中,后继指令是指在控制流中直接跟随Inst的指令。

创建了一个新的位向量InputVec,它是InVec的副本,用于存储Inst的最终输入位向量。

这个循环遍历Inst的所有后继指令。对于每个后继指令,它获取其输出位向量OutputVec,这是在successor执行之后活跃的变量集合。

执行位向量的逻辑或操作,将OutputVec合并到InputVec中。合并操作是将所有后继指令的输出位向量合并到当前指令的输入位向量中,表示这些变量在Inst执行之前也是活跃的。

计算得到的输入位向量InputVec存储在INSet映射中,INSet用于存储每个指令的输入位向量。

用于比较两个位向量是否相等。它首先检查两个位向量的长度是否相同,如果不同,则它们不相等。然后,它遍历位向量的每个位,如果发现任何不匹配的位,则返回false。如果所有位都匹配,则返回true

2.3 flowOut实现 :

void LivenessPass::flowOut(Instruction *Inst, BitVector Pre, BitVector Post){
///TODO
//判断当前输出的Output Bitvector和上一轮迭代的Output Bitvector是否一致,
//如果不一致就将当前Inst的所有下一个Inst(由于是后向分析,所以是当前Inst的前继Inst)加入InstVector当中
  if(bitVectorsEqual(Pre,Post) )
  {
    //Pass;
  }
  else{
    auto nextnodes = getPredecessors(Inst);
    for(auto eachnodes : nextnodes)
      InstVector.push_back(eachnodes);
  }
  OUTSet[Inst] = Post;//?
}

这个成员函数接受三个参数:Inst是当前正在处理的指令,Pre是指令执行前的位向量(即输入位向量),Post是指令执行后的位向量(即输出位向量)。

用于检查当前指令的输出位向量Post是否与上一轮迭代的输出位向量Pre相同。如果它们相同,说明对于当前指令的输出位向量没有新的信息,因此不需要进行任何操作。

如果输出位向量发生了变化,即Pre和Post不相同,那么需要更新依赖于当前指令的其他指令的活性信息。

更新当前指令Inst的输出位向量OUTSet为新的值Post。OUTSet是一个映射,用于存储每个指令的输出位向量。

2.4 transfer实现:

BitVector LivenessPass::transfer(Instruction *Inst) {// 实现活跃变量分析的转移函数
    // 初始化Use和Def集合
    BitVector Use = BitVector(InstCounter, false);
    BitVector Def = BitVector(InstCounter, false);
    // 根据指令类型进行分类处理
    if (auto *BinOp = dyn_cast(Inst)) {
        Value *Operand0 = BinOp;
        Value *Operand1 = BinOp->getOperand(0);
        Value *Operand2 = BinOp->getOperand(1);
        Def[InstBitMap[Operand0]] = true;
        if (!isImmutable(Operand1))
            Use[InstBitMap[Operand1]] = true;
        if (!isImmutable(Operand2))
            Use[InstBitMap[Operand2]] = true;
    } else if (auto *Load = dyn_cast(Inst)) {
        Value *Operand0 = Load;
        Value *Operand1 = Load->getOperand(0);
        Def[InstBitMap[Operand0]] = true;
        if (!isImmutable(Operand1))
            Use[InstBitMap[Operand1]] = true;
    } else if (auto *Store = dyn_cast(Inst)) {
        Value *Operand0 = Store->getOperand(0);
        Value *Operand1 = Store->getOperand(1);
        Def[InstBitMap[Operand1]] = true;
        if (!isImmutable(Operand0))
            Use[InstBitMap[Operand0]] = true;
    } else if (auto *Alloc = dyn_cast(Inst)) {
        Value *Operand0 = Alloc;
        Def[InstBitMap[Operand0]] = true;
    } else if (auto *Cmp = dyn_cast(Inst)) {
        Value *Operand0 = Cmp;
        Value *Operand1 = Cmp->getOperand(0);
        Value *Operand2 = Cmp->getOperand(1);
        Def[InstBitMap[Operand0]] = true;
        if (!isImmutable(Operand1))
            Use[InstBitMap[Operand1]] = true;
        if (!isImmutable(Operand2))
            Use[InstBitMap[Operand2]] = true;
    }
    // 计算输出活跃变量集合
    BitVector Out = BitVector(InstCounter, false);
    BitVector Temp = INSet[Inst];
    for (int i = 0; i < Temp.size(); ++i) {
        if (Def[i])
            Temp[i] = false;
    }
    for (int i = 0; i < Use.size(); ++i) {
        if (Use[i] || Temp[i])
            Out[i] = true;
    }
    
    return Out;
}

这段代码是一个活跃变量分析(Liveness Analysis)的迁移函数transfer的实现。迁移函数用于计算在执行当前指令后,哪些变量是活跃的。活跃变量是指在指令执行后仍然有效的变量,它们可能是使用(Use)或定义(Def)的变量。

代码的主要部分是针对不同类型的指令(二元运算符、加载指令、存储指令、内存分配指令、比较指令)的分支处理。对于每种类型的指令,代码会更新Use和Def集合,然后使用这些集合来计算输出活跃变量集合。

这两行代码初始化了两个位向量Use和Def,它们分别用于表示指令的“使用”集合和“定义”集合。InstCounter是指令的数量,用于确定位向量的长度。初始化时,位向量的所有位都设置为false。

这段代码处理二元运算符指令。dyn_cast是一个类型转换函数,用于安全地将指令转换为BinaryOperator类型。如果转换成功,说明当前指令是一条二元运算符指令。

对于二元运算符,它的结果(Operand0)被加入到Def集合中,表示这个指令定义了结果值。如果操作数(Operand1和Operand2)不是不可变的(isImmutable返回false),则它们被加入到Use集合中,表示这些操作数被使用了。

这段代码处理加载指令(Load)。加载指令的结果被加入到Def集合中,表示这个指令定义了加载的值。加载指令的源操作数(Operand1)如果是可变的,则被加入到Use集合中。

处理存储指令(Store)。存储指令的目标操作数(Operand1)被加入到Def集合中,表示这个指令定义了存储的目标。存储指令的源操作数(Operand0)如果是可变的,则被加入到Use集合中。

处理分配指令(Alloca)。

分配指令的结果被加入到Def集合中,表示这个指令定义了分配的内存。

处理比较指令(ICmp)。

比较指令的结果被加入到Def集合中,表示这个指令定义了比较的结果。

比较指令的操作数(Operand1和Operand2)如果是可变的,则被加入到Use集合中。

初始化了输出位向量Out,它将用于存储当前指令执行后的活跃变量集合。

获取了当前指令的输入位向量INSet[Inst],并将其存储在临时位向量Temp中。

遍历临时位向量Temp,如果某个位在Def集合中为true,则将该位在Temp中设置为false。

这是因为如果一个变量在当前指令中被定义,那么它之前的活跃状态就不重要了。

遍历Use集合,如果某个位在Use集合中为true或者该位在Temp中为true,则将该位在Out中设置为true。

这表示这个变量在当前指令执行后仍然是活跃的。

最后,返回输出位向量Out,它表示当前指令执行后的活跃变量集合。

2.5 InstAnalysis实现:

初次尝试:

结果:

更新后,成功!:

void LivenessPass::InstAnalysis() {
  ///TODO
  ///基于实现基本的WorkList循环,使用你刚刚实现的flowIn, flowOut, transfer函数实现活跃变量分析
  
  while (!InstVector.empty())
  {
    auto instruction = *InstVector.begin(); // 获取指向 Value* 的指针,注意*号,否则返回的是迭代器
    
    Instruction *Inst = dyn_cast(instruction);
    InstVector.erase(InstVector.begin());
    if (Inst) // 确保转换成功
    {
        BitVector Pre = OUTSet[instruction];
        flowIn(Inst, INSet[instruction]);
        OUTSet[instruction] = transfer(Inst); //transfer函数导致段错误
        flowOut(Inst, Pre, OUTSet[instruction]);
    }

代码解释如下:

成员函数,用于执行活跃变量分析。

遍历指令集合InstVector。

InstVector是一个待处理的指令列表,包含了在活跃变量分析中需要考虑的指令。

尝试将迭代器指向的元素转换为Instruction类型的指针。

dyn_cast是一个类型转换函数,用于安全地将迭代器指向的元素转换为Instruction类型。

如果转换成功,这行代码从InstVector中移除当前指令。

移除操作通常发生在指令被处理后,以确保在后续迭代中不会重复处理同一个指令。

用于确保转换成功,即当前迭代器指向的元素确实是一个指令。

获取当前指令的输出位向量preOut。

OUTSet是一个映射,用于存储每个指令的输出位向量。

调用flowIn函数,计算当前指令的输入位向量。

INSet是一个映射,用于存储每个指令的输入位向量。

更新当前指令的输出位向量。

transfer函数用于计算指令的输出位向量,即在该指令执行后活跃的变量集合。

调用flowOut函数,计算当前指令的前继指令的输出位向量。

preOut是当前指令在执行前的输出位向量,OUTSet[Inst]是当前指令在执行后的输出位向量。

2.6 测试结果:

三、补充内容: 报错1:no LivevessPass.so

.SO文件是共享对象文件(Shared Object File)的缩写,它是一种用于链接的文件格式,其中包含了可执行代码和数据,这些代码和数据可以被多个程序共享。.SO文件通常用于Unix-like操作系统,如Linux,它们用于动态链接,允许应用程序在运行时链接到这些文件,而不是在编译时链接。

这让我想起来之前学习时用的.a静态库,查阅资料发现:

.SO文件:.a文件:.dll文件: 解决1:

原因是没有camke .. 和make编译…..

相关资料学习:

CMake:Make:

成功解决。

报错2: make报错(代码内变量未定义):

尝试2.1:改头文件(and make文件里的include)

看到众多未定义,我以为是头文件库的包含有误;

改动为:

但无效,查看cmake发现:

已经包含了include:

include_directories(${LLVM_INCLUDE_DIRS} include):将LLVM的头文件目录和项目中的include目录添加到编译器的头文件搜索路径中。

解决2:

实际是我的代码编写有误,确实没定义该内容;应该是livenesspass;

报错3: ./auto.sh 脚本内对输入处理有误

解决3:先输入一个符号避免报错,随后输入测试文件名;

Cat查看内容,如下:

同样需要换行后才能输入(为什么?)

报错4:./auto.sh执行完没有输出:

尝试4.1:print函数是否修改

教辅表示查看print,但是我并没有改动过其他print函数的文件.

解决4: 恢复原auto.sh

恢复原auto.sh.查看区别:

3,4行的cd原因见【报错5】,测试路径是在/myshixun下;

5,6行是把正确和错误输出都重定向到null;

第9行是问题关键: 没有-Liveness是没有正确输出的;

opt 是 LLVM 优化器的一个命令行工具,它用于对 LLVM IR(中间表示)进行各种优化。LivenessPass.so 是一个共享库,它包含了一个自定义的 LLVM pass(优化过程),这个 pass 被命名为 Liveness。

寻找Liveness,两个文件下找到:

加入Liveness后,成功得到输出:

报错5:头哥平台评测错误:

报错显示没有LivenessPass.so这个共享库(类似动态库);

根据之前的试错中得知这个是make后生成的—-定位错误到make环节;

解决5:

pwd先看本地路径是什么:

发现是make失败,即代码有误(见报错2)

细看,发现报错是中括号中的变量处理有误:

对比成功代码,发现是:

我使用迭代器instIterator来访问InstVector中元素,并使用它作为OUTSet和INSet的索引。而std::map不支持使用迭代器作为索引。

应该使用Inst作为索引,因为Inst是一个指向Instruction的指针,这是OUTSet和INSet中键的类型:

且这里的代码也同样出错【InstVector是向量vector,erase操作没有返回值;】:

探索6:命令行输出不一:

发现: 此处make时只有2个cpp.o:

而之前都是4个:

尝试在更改一个cpp文件后,直接make:—发现只有一个cpp.o—说明只会重新make更改过的文件【除非make clean 了 会重新make所有】

报错7:段错误【代码导致的】

是指针处的问题;(具体细节见前面【报错 4】)

文章来源:https://blog.csdn.net/weixin_70874886/article/details/139161833



微信扫描下方的二维码阅读本文

© 版权声明
THE END
喜欢就支持一下吧
点赞9 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容