在 LLVM 字节码中查找循环

Question

我想在 LLVM 字节码中找到简单的循环，并提取基本的循环信息。

例如：

 for (i=0; i<1000; i++)
    sum += i;

我想提取绑定 [0, 1000]、循环变量 "i" 和循环体 (sum += i).
我该怎么办？

我阅读了 LLVM API 文档，找到了一些有用的类，例如 "Loop"， "LoopInfo".
但是不知道具体怎么用。

你能帮我一些忙吗？详细的用法可能更有帮助。

Answer 1

LLVM 只是一个库。你不会在那里找到 AST 节点。

我建议看一下 Clang，它是一个构建在 LLVM 之上的编译器。

也许 this 就是您要找的东西？

Answer 2

就像 Matteo 所说的那样，为了让 LLVM 能够识别循环变量和条件，文件需要在 LLVM IR 中。这个问题说你在 LLVM 字节码中有它，但是由于 LLVM IR 是以 SSA 形式编写的，所以谈论 "loop variables" 并不是真的 true。我敢肯定，如果您描述了您正在尝试做的事情，以及您期望的结果类型，我们可以提供进一步的帮助。

一些帮助您入门的代码：

    virtual void getAnalysisUsage(AnalysisUsage &AU) const{
        AU.addRequired<LoopInfo>();
    }

    bool runOnLoop(Loop* L, LPPassManager&){
        BasicBlock* h = L->getHeader();
        if (BranchInst *bi = dyn_cast<BranchInst>(h->getTerminator())) {
            Value *loopCond = bi->getCondition();
        }
        return false;
    }

此代码片段来自常规 LLVM pass。

Answer 3

一旦达到 LLVM IR 级别，您请求的信息可能不再准确。例如，clang 可能已经转换了您的代码，因此 i 从 -1000 变为 0。或者它可能已经完全优化了 "i"，因此没有明确的归纳变量。如果您真的需要完全按照 C 代码中的面值提取信息，那么您需要查看 clang，而不是 LLVM IR。否则，您能做的最好的事情就是计算循环次数，在这种情况下，请查看 ScalarEvolution pass。

检查 PowerPC 硬件循环转换过程，它很好地演示了行程计数计算：http://llvm.org/docs/doxygen/html/PPCCTRLoops_8cpp_source.html

代码相当繁重，但应该可以理解。有趣的函数是PPCCTRLoops::convertToCTRLoop。如果您对此有任何疑问，我可以尝试回答。

Answer 4

如果您不想使用传递管理器，您可能需要在 llvm::LoopInfoBase class 中的每个函数上调用 Analyze 方法IR（假设您使用的是 LLVM-3.4）。但是，Analyze 方法将每个函数的 DominatorTree 作为输入，您必须首先生成它。以下代码是我用 LLVM-3.4 测试的代码（假设您已经阅读了 IR 文件并将其转换为名为 module 的模块*）：

for(llvm::Module::iterator func = module->begin(), y=module->end(); func!=y; func++){
        //get the dominatortree of the current function
        llvm::DominatorTree* DT = new llvm::DominatorTree();         
        DT->DT->recalculate(*func);
        //generate the LoopInfoBase for the current function
        llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>* KLoop = new llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>();
        KLoop->releaseMemory();
        KLoop->Analyze(DT->getBase());        
}

基本上，有了KLoop的生成，就可以得到IR层级的各种LOOP信息。您可以参考 LoopInfoBase class 中的 API 了解详细信息。顺便说一句，您可能想添加以下内容 headers： "llvm/Analysis/LoopInfo.h" "llvm/Analysis/Dominators.h".

Answer 5

只是对 Junxzm 回答的更新，一些参考、指针和方法在 LLVM 3.5.

中发生了变化

for(llvm::Module::iterator f = m->begin(), fe=m->end(); f!=fe; ++f){
        llvm::DominatorTree DT = llvm::DominatorTree();
        DT.recalculate(*f);
        llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>* LoopInfo = new llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>();
        LoopInfo->releaseMemory();
        LoopInfo->Analyze(DT);    
      }

在 LLVM 字节码中查找循环

Find loops in LLVM bytecode

llvm

clang