Trova loop nel codice byte LLVM

Question

Desidero trovare semplici loop nel bytecode LLVM ed estrarre le informazioni di base del ciclo .

Ad esempio:

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

Voglio estrarre il limite [0, 1000), l'indice del ciclo "i" e il corpo loop (sum + = i).
Cosa devo fare?

Ho letto il documento API LLVM e ho trovato alcune classi utili come "Loop", "LoopInfo".
Ma non so come usarli in dettaglio.

Potrebbe aiutarmi per favore? Un utilizzo dettagliato potrebbe essere più utile.

Answer 1

Se non si desidera utilizzare il gestore passaggio, potrebbe essere necessario chiamare il metodo Analyze nel LLVM :: LoopInfoBase classe su ogni funzione IR (supponendo che si sta utilizzando LLVM-3.4). Tuttavia, il metodo Analyze prende il DominatorTree di ogni funzione come input, che devi generare all'inizio. I seguenti codici sono quelli che ho provato con LLVM-3.4 (supponendo di aver letto il file IR e convertito in un modulo * chiamato come modulo):

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

In sostanza, con KLoop generato, si ottengono tutti i tipi di informazioni LOOP nel livello IR. È possibile consultare le API nella classe LoopInfoBase per i dettagli. A proposito, potresti voler aggiungere le seguenti intestazioni: "llvm/Analysis/LoopInfo.h" "llvm/Analysis/Dominators.h".

Answer 2

LLVM è solo una libreria. Non troverai nodi AST lì.

Suggerisco di dare un'occhiata a Clang, che è un compilatore costruito su LLVM.

Forse this è quello che stai cercando?

Answer 3

Proprio come ha detto Matteo, affinché LLVM sia in grado di riconoscere la variabile e le condizioni del loop, il file deve essere in LLVM IR. La domanda dice che ce l'hai nel bytecode LLVM, ma dal momento che LLVM IR è scritto in forma SSA, parlare di "variabili di loop" non è in realtà true. Sono sicuro che se descrivi cosa stai cercando di fare, e quale tipo di risultato ti aspetti, possiamo essere di ulteriore aiuto.

del codice per aiutarti a iniziare:

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

Questo frammento di codice è da dentro un passaggio LLVM regolare.

Answer 4

Una volta raggiunto il livello IR LLVM, le informazioni richieste potrebbero non essere più accurate. Ad esempio, clang potrebbe aver trasformato il tuo codice in modo da passare da -1000 a 0 invece. O potrebbe aver ottimizzato "i" completamente, in modo che non ci sia una variabile di induzione esplicita. Se hai davvero bisogno di estrarre le informazioni esattamente come dice il loro valore nominale nel codice C, allora hai bisogno di guardare clang, non LLVM IR. Altrimenti, il meglio che puoi fare è calcolare un conteggio del ciclo, nel qual caso, dare un'occhiata al passaggio ScalarEvolution.

Controllare l'hardware PowerPC loop passaggio di trasformazione, che dimostra il calcolo conteggio viaggio abbastanza bene: http://llvm.org/docs/doxygen/html/PPCCTRLoops_8cpp_source.html

Il codice è abbastanza pesante, ma dovrebbe essere followable. La funzione interessante è PPCCTRLoops :: convertToCTRLoop. Se hai ulteriori domande a riguardo, posso provare a rispondere.

Answer 5

Solo un aggiornamento sulla risposta Junxzm, alcuni riferimenti, puntatori e metodi sono stati modificati in 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);  
     }