LLVM Pass LoopAnalysis

안상준·2025년 8월 6일

LLVM

목록 보기

9/12

https://github.com/leejaymin/llvm8-tutorials-jemin/tree/master
해당 GitHub를 참고하여 Loop를 분석하는 LLVM Pass를 제작해 보았다.
각 Loop의 시작 라벨과 CIV를 출력하는 Pass

Pass Code

코드를 부분적으로 살펴보도록 하자

run

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) {
        LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
        ScalarEvolution &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);

        for (auto *L : LI)
            analyzeLoop(L, SE);

        return PreservedAnalyses::all();
    }

먼저 run 함수다. Function Pass 이다.
LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
루프 구조를 파악하기 위한 루프 분석 정보를 가져온다. LoopInfo는 루프의 헤더, 바디, 중첩 구조 등의 정보를 제공한다.
ScalarEvolution &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
루프 내의 변수가 어떻게 진화하는지 분석해주는 도구다.
반복 횟수 측정, 루프 종료 조건 계산, 일정 패턴 탐지 등에 사용된다.
for (auto *L : LI)
현재 함수에서 발견된 루프들을 순회한다.

analyzeLoop

void analyzeLoop(Loop *L, ScalarEvolution &SE) {
        BasicBlock *header = L->getHeader();
        errs() << "loop : " << getBlockLabel(header) << "\n";

        if (PHINode *civ = findCIV(L, SE))
            errs() << "CIV  : " << getValueLabel(civ) << "\n";

        for (auto *sub : L->getSubLoops())
            analyzeLoop(sub, SE);
    }

*header는 루프 헤더의 베이직 블럭 포인터다.
getBlockLabel함수를 호출하여 라벨을 출력한다.
findCIV(L, SE)함수를 이용하여 루프에서 카운터 역할을 하는 PHI노드(CIV)를 찾는다.
getValueLabel()을 통하여 해당 주소에 있는 IR을 출력한다.
마지막으로 for (auto *sub : L->getSubLoops()) 재귀적으로 루프를 탐색하며 위 과정을 반복한다.

findCIV

CIV(Canonical Induction Variable)란? : 루프 내에서 일정한 패턴으로 증감하는 PHI노드를 의미

PHINode* findCIV(Loop *L, ScalarEvolution &SE) {
        BasicBlock *header = L->getHeader();
        for (auto &I : *header) {
            if (auto *phi = dyn_cast<PHINode>(&I)) {
                const SCEV *scev = SE.getSCEV(phi);
                if (auto *addRec = dyn_cast<SCEVAddRecExpr>(scev))
                    if (addRec->getLoop() == L)
                        return phi;
            }
        }
        return nullptr;
    }

루프 내의 CIV를 자동으로 찾아주는 함수로 루프의 헤더블록을 가져옴
대부분의 CIV는 루프의 헤더블록에서 초기화
헤더블록의 모든 명령어를 순회
각 명령어가 PHI노드인지 확인
ScalarEvolution 분석기를 이용해 해당 PHI노드에 대한 SCEV 표현식을 가져옴
SCEV는 LLVM 내부에서 값의 변화 양상을 수학적으로 추상화한 표현
SCEV 표현식이 SCEVAddRecExpr인지 확인
선형적인 패턴, 반복문에서 인덱스처럼 변화하는 수열인지
찾은 표현식이 현재 루프의 반복 패턴을 나타내는 것인지 확인

get IR

std::string getBlockLabel(BasicBlock *BB) {
        std::string s;
        raw_string_ostream os(s);
        BB->printAsOperand(os, /*PrintType=*/false);
        os.flush();
        // if (!s.empty() && s[0] == '%')
        //     return s.substr(1) +;
        return s;
    }

    std::string getValueLabel(Value *V) {
        std::string s;
        raw_string_ostream os(s);
        V->print(os);
        os.flush();
        return s;
    }

마지막으로 BasicBlock의 라벨을 문자열로 반환하는 함수와 LLVM IR의 Value 객체를 문자열화하는 함수다.

전체 코드

#include "llvm/IR/PassManager.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/raw_ostream.h"

#include <string>
#include <sstream>

using namespace llvm;

namespace {

class LoopAnalysisPass : public PassInfoMixin<LoopAnalysisPass> {
public:
    PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) {
        LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
        ScalarEvolution &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);

        for (auto *L : LI)
            analyzeLoop(L, SE);

        return PreservedAnalyses::all();
    }

private:
    void analyzeLoop(Loop *L, ScalarEvolution &SE) {
        BasicBlock *header = L->getHeader();
        errs() << "loop : " << getBlockLabel(header) << "\n";

        if (PHINode *civ = findCIV(L, SE))
            errs() << "CIV  : " << getValueLabel(civ) << "\n";

        for (auto *sub : L->getSubLoops())
            analyzeLoop(sub, SE);
    }

    PHINode* findCIV(Loop *L, ScalarEvolution &SE) {
        BasicBlock *header = L->getHeader();
        for (auto &I : *header) {
            if (auto *phi = dyn_cast<PHINode>(&I)) {
                const SCEV *scev = SE.getSCEV(phi);
                if (auto *addRec = dyn_cast<SCEVAddRecExpr>(scev))
                    if (addRec->getLoop() == L)
                        return phi;
            }
        }
        return nullptr;
    }

    std::string getBlockLabel(BasicBlock *BB) {
        std::string s;
        raw_string_ostream os(s);
        BB->printAsOperand(os, /*PrintType=*/false);
        os.flush();
        // if (!s.empty() && s[0] == '%')
        //     return s.substr(1) +;
        return s;
    }

    std::string getValueLabel(Value *V) {
        std::string s;
        raw_string_ostream os(s);
        V->print(os);
        os.flush();
        return s;
    }
};

} // namespace

extern "C" ::llvm::PassPluginLibraryInfo llvmGetPassPluginInfo() {
    return {
        LLVM_PLUGIN_API_VERSION,
        "LoopAnalysisPass", LLVM_VERSION_STRING,
        [](PassBuilder &PB) {
            PB.registerPipelineParsingCallback(
                [](StringRef Name,
                   FunctionPassManager &FPM,
                   ArrayRef<PassBuilder::PipelineElement>) {
                    if (Name == "loopanalysis") {
                        FPM.addPass(LoopAnalysisPass());
                        return true;
                    }
                    return false;
                });
        }
    };
}

C Code

#include <stdio.h>
int main() {
    int x, y, z;
    scanf("%d %d %d ", &x, &y, &z);
    for(int i=0;i<x;i++) {
        for(int j=0;j<y;j++) {
            for(int k=0;k<z;k++) {
                printf("i: %d, j: %d, k: %d\n", i, j, k);
            }
        }
    }
    return 0;
}

최적화 가능성이 있어 side effect가 있는 함수로 진행

LLVM IR

코드가 길어 루프의 헤더 블럭만 가져왔다. 3중 for문 이고, for문의 시작 label은 각 10, 20, 40이다. PHI노드를 보면 SSA에 0을 저장하는 것을 볼 수 있다.이는 for문에서 변수를 0으로 초기화 하는 부분이며, 이를 통해 해당 PHI노드가 CIV라는 것을 유추할 수 있다.