Tìm các vòng lặp trong LLVM bytecode

Question

Tôi muốn tìm các vòng đơn giản trong mã byte bytecode LLVM và trích xuất thông tin cơ bản của vòng lặp.

Ví dụ:

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

tôi muốn trích xuất các ràng buộc [0, 1000), biến vòng lặp "i" và cơ thể vòng lặp (tổng + = i).
Tôi nên làm gì?

Tôi đã đọc tài liệu API LLVM và tìm một số lớp hữu ích như "Vòng lặp", "LoopInfo".
Nhưng tôi không biết cách sử dụng chúng chi tiết.

Bạn có thể vui lòng cho tôi một số trợ giúp không? Việc sử dụng chi tiết có thể hữu ích hơn.

Answer 1

Nếu bạn không muốn sử dụng trình quản lý vượt qua, bạn có thể cần phải gọi phương pháp phân tích trong lớp llvm :: LoopInfoBase trên từng chức năng trong IR (giả sử bạn đang sử dụng LLVM-3.4). Tuy nhiên, phương pháp Phân tích lấy DominatorTree của mỗi hàm làm đầu vào, mà bạn phải tạo ra lúc đầu. Các mã sau đây là những gì tôi đã thử nghiệm với LLVM-3.4 (giả sử bạn đã đọc các tập tin IR và chuyển đổi nó thành một Module * tên là mô-đun):

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());   
} 

Về cơ bản, với KLoop tạo ra, bạn sẽ có được tất cả các loại thông tin LOOP ở mức IR. Bạn có thể tham khảo các API trong lớp LoopInfoBase để biết chi tiết. Nhân tiện, bạn có thể muốn thêm tiêu đề sau: "llvm/Phân tích/LoopInfo.h" "llvm/Phân tích/Dominators.h".

Answer 2

LLVM chỉ là một thư viện. Bạn sẽ không tìm thấy các nút AST ở đó.

Tôi khuyên bạn nên xem Clang, một trình biên dịch được xây dựng trên đầu trang của LLVM.

Có thể this là những gì bạn đang tìm kiếm?

Answer 3

Giống như Matteo đã nói, để LLVM có thể nhận biết biến và điều kiện vòng lặp, tệp cần phải có trong LLVM IR. Câu hỏi cho biết bạn có nó trong bytecode LLVM, nhưng kể từ khi LLVM IR được viết dưới dạng SSA, nói về "biến vòng lặp" không thực sự là đúng. Tôi chắc chắn nếu bạn mô tả những gì bạn đang cố gắng làm, và loại kết quả bạn mong đợi chúng tôi có thể giúp đỡ thêm.

Một số mã để giúp bạn bắt đầu:

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; 
    } 

Đoạn mã này là từ bên trong một đường chuyền LLVM thường xuyên.

Answer 4

Khi bạn đạt đến cấp IR LLVM, thông tin bạn yêu cầu có thể không còn chính xác nữa. Ví dụ: clang có thể đã thay đổi mã của bạn để tôi chuyển từ -1000 lên 0. Hoặc nó có thể đã tối ưu hóa "i" hoàn toàn, do đó không có biến cảm ứng rõ ràng. Nếu bạn thực sự cần trích xuất thông tin chính xác như nó nói ở giá trị mặt trong mã C, thì bạn cần phải nhìn vào clang chứ không phải LLVM IR. Nếu không, tốt nhất bạn có thể làm là tính toán một số lượng chuyến đi vòng lặp, trong trường hợp đó, có một cái nhìn tại PassarEvolution vượt qua.

Kiểm tra phần cứng PowerPC vòng chuyển đổi pass, mà minh chứng cho tính đếm chuyến đi khá tốt: http://llvm.org/docs/doxygen/html/PPCCTRLoops_8cpp_source.html

Mã này là khá nặng, nhưng phải followable. Hàm thú vị là PPCCTRLoops :: convertToCTRLoop. Nếu bạn có thêm bất kỳ câu hỏi nào về điều đó, tôi có thể cố gắng trả lời chúng.

Answer 5

Chỉ cần cập nhật câu trả lời Junxzm, một số tham chiếu, con trỏ và phương thức đã thay đổi trong 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);  
     }