如何通过LLVM Pass提取数组索引变量及循环迭代变量？

问题背景 #

我希望编写一个LLVM Pass，获取程序的数组索引信息与循环索引信息。以下是访问二维数组的示例程序：

int main()
{
    int i, j, arr2d[5][10];
    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 10; j++)
        {
            arr2d[i][j] = i * j;
        }
    }
    return 0;
}

该程序中，数组由i、j索引，循环也由这两个变量控制。已知程序的LLVM IR文件，能否通过LLVM Pass识别出这些数组索引变量与循环控制变量？

从IR文件来看，似乎可以回溯到变量i和j，但不清楚如何实现。例如，IR中计算左值的GEP指令如下：

%21 = getelementptr inbounds [10 x i32], [10 x i32]* %18, i64 0, i64 %20

回溯变量j的路径：

%20 = sext i32 %19 to i64
%19 = load i32, i32* %3, align 4
%3 = alloca i32, align 4 // Allocation of j

回溯变量i的路径：

%18 = getelementptr inbounds [5 x [10 x i32]], [5 x [10 x i32]]* %4, i64 0, i64 %17
%17 = zext i32 %16 to i64
%16 = load i32, i32* %2
%2 = alloca i32, align 4 // Allocation of i

能否通过上述路径回溯到数组索引与循环索引对应的%2和%3？现有资料仅介绍了提取常量索引的方法，未涉及变量索引的提取。

解决方案 #

完全可以通过回溯GEP指令的索引操作数，找到对应的数组索引变量（即alloca指令），并通过LLVM的LoopInfo分析器关联到循环控制变量。具体实现步骤如下：

1. 核心思路 #

• 数组访问在LLVM IR中必然通过getelementptr（GEP）指令实现，因此先定位所有GEP指令。
• 对GEP的每个索引操作数（跳过第一个基址操作数），回溯其依赖链，跳过类型扩展（zext/sext）和load指令，最终找到变量的分配点alloca。
• 借助LoopInfo分析器，检查该alloca是否被用作循环的控制变量（循环起始值、条件判断、增量操作中使用的变量）。

2. Pass实现示例 #

#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

namespace {
struct ArrayIndexPass : public FunctionPass {
    static char ID;
    ArrayIndexPass() : FunctionPass(ID) {}

    bool runOnFunction(Function &F) override {
        LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

        // 遍历函数内所有指令
        for (BasicBlock &BB : F) {
            for (Instruction &I : BB) {
                // 筛选GEP指令
                if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
                    errs() << "找到GEP指令: " << *GEP << "\n";
                    // 遍历GEP的索引操作数（从第1个开始，第0个是数组基址）
                    for (unsigned idx = 1; idx < GEP->getNumOperands(); ++idx) {
                        Value *indexOperand = GEP->getOperand(idx);
                        errs() << "  索引操作数" << idx << ": " << *indexOperand << "\n";
                        
                        // 回溯到原始alloca变量
                        Value *rootVal = traceToAlloca(indexOperand);
                        if (auto *alloca = dyn_cast<AllocaInst>(rootVal)) {
                            errs() << "    追踪到变量分配点: " << *alloca << "\n";
                            // 检查是否为循环控制变量
                            checkLoopVariable(alloca, LI);
                        }
                    }
                }
            }
        }
        return false;
    }

    // 辅助函数：追踪值到对应的alloca指令
    Value* traceToAlloca(Value *V) {
        while (true) {
            // 处理类型扩展指令
            if (auto *extInst = dyn_cast<ZExtInst>(V)) {
                V = extInst->getOperand(0);
                continue;
            }
            if (auto *extInst = dyn_cast<SExtInst>(V)) {
                V = extInst->getOperand(0);
                continue;
            }
            // 处理load指令
            if (auto *loadInst = dyn_cast<LoadInst>(V)) {
                V = loadInst->getPointerOperand();
                continue;
            }
            // 无法继续回溯时返回
            break;
        }
        return V;
    }

    // 检查alloca是否为循环控制变量
    void checkLoopVariable(AllocaInst *alloca, LoopInfo &LI) {
        for (Loop *loop : LI) {
            // 遍历循环内所有基本块
            for (BasicBlock *loopBB : loop->getBlocks()) {
                for (Instruction &I : *loopBB) {
                    // 检查load操作是否使用该alloca
                    if (auto *loadInst = dyn_cast<LoadInst>(&I)) {
                        if (loadInst->getPointerOperand() == alloca && !loop->isLoopInvariant(&I)) {
                            errs() << "    该变量是循环控制变量，所属循环: " << *loop << "\n";
                            return;
                        }
                    }
                    // 检查store操作是否修改该alloca（比如循环增量i++）
                    if (auto *storeInst = dyn_cast<StoreInst>(&I)) {
                        if (storeInst->getPointerOperand() == alloca && !loop->isLoopInvariant(&I)) {
                            errs() << "    该变量是循环控制变量，所属循环: " << *loop << "\n";
                            return;
                        }
                    }
                }
            }
        }
    }

    void getAnalysisUsage(AnalysisUsage &AU) const override {
        AU.addRequired<LoopInfoWrapperPass>();
        AU.setPreservesAll();
    }
};
}

char ArrayIndexPass::ID = 0;
static RegisterPass<ArrayIndexPass> X("array-index-pass", "数组索引与循环控制变量检测Pass");

3. 关键说明 #

• traceToAlloca函数：跳过IR中常见的类型扩展和加载操作，直接定位到变量的分配点，对应示例中的%2和%3。
• checkLoopVariable函数：通过LoopInfo遍历所有循环，判断该变量是否在循环内被修改或使用（且不是循环不变量），从而确认其为循环控制变量。
• Pass依赖：需要依赖LoopInfoWrapperPass来获取循环信息，因此必须在getAnalysisUsage中声明。

内容的提问来源于stack exchange，提问作者Atanu Barai