5.1 Il nuovo control-flow graph Implementazione del verificatore basato sull’ipd 5

(1)

C A P I T O L O

5 Implementazione del verificatore

basato sull’ipd

L’algoritmo di verifica del bytecode basato sull’ipd è stato implementato modificando la struttura di due classi del JustIce: è stata riscritta tutta la data-flow analysis e le strutture dei nodi del grafo e del dizionario, è stato aggiunto un metodo per il calcolo dell’ipd e alcuni metodi di varia utilità, ad esempio l’algoritmo quicksort ed alcuni metodi per controlli della coerenza (sanity checks) delle operazioni effettuate.

5.1 Il nuovo control-flow graph

Il control-flow graph è implementato dalla classe CFGraph:

public class CFGraph{

private class InstrContext implements InstructionContext{...}

private class TheDictionary{...}

private HashMap dictionary;

private HashMap currentInFrame;

private final MethodGen method_gen;

private final Subroutines subroutines;

private final ExceptionHandlers exceptionhandlers;

private Hashtable instructionContexts;

private boolean mergeFrames(Frame f1, Frame f2){

...

public InstructionContext[] getSuccessors();

public InstructionContext getImmediateSuccessor(InstructionContext ic){

(2)

CAPITOLO 5:IMPLEMENTAZIONE DEL VERIFICATORE BASATO SULL’IPD

public final InstructionHandle getIPD(InstructionHandle ih);

public final HashMap getCBIPDs();

public InstructionContext[] getInstructionContextsSorted();

public final void viewInstructions();

... }

Analizziamo le principali differenze rispetto alla versione del JustIce:

• è cambiata l’implementazione dell’InstructionContext: il dizionario non è più integrato nei nodi ma viene salvato in una struttura chiamata dictionary (tra poco ne analizzeremo in dettaglio l’implementazione). E’ stato inoltre implementato il caching dei successori: nel JustIce infatti bisognava sempre calcolarli invocando metodi delle APIs del BCEL;

• il dizionario è implementato dalla classe TheDictionary: inoltre, per consentire in futuro una espansione che gestisca le subroutines (attualmente non supportate) è stato pensato di strutturare l’attributo dictionary del CFGraph in modo simile ai frames del JustIce, cioè come un hashmap che ha come chiave l’ultima jsr effettuata.

• è stato creato il frame per l’istruzione corrente (currentInFrame); nel JustIce infatti il frame corrente veniva creato al volo direttamente nella circulationPump(...) perché ogni nodo del grafo salvava il proprio frame quindi creare un currentInFrame nel grafo sarebbe stato ridondante;

• sono stati implementati i metodi per il calcolo dell’ipd; in particolare ne esistono più varianti:

o getAllIPDs(): restituisce l’ipd di tutte le istruzioni del grafo; o getAllCBIPDs(): restituisce l’ipd di tutti i salti condizionati;

o getCBIPDs(): restituisce l’ipd di tutti i salti condizionati tali che l’ipd sia diverso dal nodo END;

o getIPD(InstructionHandle ih): restituisce l’ipd dell’istruzione passata come parametro

(3)

• è stato creato un metodo per l’ordinamento degli oggetti di un array: BCEL e JustIce non danno importanza all’ordine con cui vengono restituiti gli oggetti, ad esempio i successori di una istruzione o la lista dei nodi del grafo. Sono state quindi introdotte delle versioni alternative di alcune funzioni, ad esempio getInstructionContextsSorted() (restituisce i nodi del grafo rispettando l’ordine imposto dalla posizione (nel bytecode) delle istruzioni a loro associate), per facilitare il debugging e la leggibilità dell’output.

• il metodo execute(...) è stato completamente riscritto perché nel JustIce veniva effettuato il merge prima dei controlli strutturali e dell’esecuzione simbolica dell’istruzione [cap 4.4.2.4].

• i due metodi mergeInFrames(...) e getOutFrame() sono stati definiti solamente per compatibilità con l’interfaccia InstructionContext: nell’attuale implementazione non hanno nessun ruolo perché l’out-frame viene generato in seguito all’esecuzione e quindi viene direttamente fatto il merge con l’in-frame dei possibili successori con un metodo (mergeFrames(...)) invocato dal data-flow analyzer (circulationPump(...)).

L’interfaccia InstructionContext, come per il JustIce, viene implementata con una classe privata, InstrContext: infatti solo i metodi del CFGraph devono gestire determinati aspetti della struttura dei nodi. Esaminiamo più in dettaglio la classe InstrContext:

private class InstrContext implements InstructionContext{

private InstructionHandle instruction;

private ArrayList executionPredecessors;

private InstructionHandle[] cachedSuccessors;

private boolean cacheTAG;

private InstrContext cache_ipd;

private boolean ipdcacheTAG = false;

public InstructionContext[] getSuccessors();

public final InstrContext findIPD();

public boolean mergeFrames(Frame f1, Frame f2);

public boolean execute(...);

public int targetCounter()

... }

(4)

Trovare l’ipd ed i successori di un nodo sono due operazioni che solitamente allungano molto i tempi di esecuzione della data-flow analysis: per questo ne è stato implementato il caching. Ogni nodo ha infatti un vettore di InstructionHandles(s) che memorizza un riferimento ai possibili successori del nodo e un campo cache_ipd che punta al nodo ipd dell’istruzione. La struttura di InstrContext è riportata in figura 5.1.

InstrContext InstructionHandle Instruction ex ec u ti on P re d ec e ss o rs instruction instruction prev next InstructionHandle InstructionHandle lenght opcode ( istruzione precedente nel bytecode ) ( istruzione successiva nel bytecode ) cachedSuccessors TAG cache_ipd TAG InstructionHandle InstrContext ( istruzioni successive nel grafo ) ( ipd dell'istruzione )

fig. 5.1: Nuova struttura dei nodi del grafo (InstrContext) e loro relazione con le istruzioni del bytecode

Per gestire correttamente il caching dei nodi è stato previsto anche un bit di validità per successori e ipd: cacheTAG e ipdcacheTAG.

L’algoritmo per il calcolo dell’ipd è ispirato ad un algoritmo implementato in C sviluppato presso il dipartimento. Priorità dell’algoritmo non è il tempo di esecuzione, ma la minimizzazione dello spazio di memoria richiesto per le strutture dati durante il calcolo dell’ipd; il metodo getIPD(...) del CFGraph e le sue varianti utilizzano due metodi della classe InstrContext per svolgere il calcolo dell’ipd:

(5)

findIPD(...) e pd_by(). Il primo metodo (findIPD(...)) serve a selezionare un nodo candidato ed il secondo (pd_by(), post-dominated by) serve a verificare che il nodo candidato sia effettivamente il post-dominator del nodo su cui viene applicato il metodo findIPD(...). Il fatto che il post-dominator trovato sia anche ipd del nodo viene garantito dal fatto che i nodi candidati non vengono presi a caso, ma in modo ordinato sui percorsi da un nodo all’END1_{del grafo. Pre-condizioni per un}

corretto funzionamento della findIPD(...) sono:

• il grafo non deve presentare cicli infiniti, ovvero il nodo END deve essere raggiungibile da qualsiasi nodo del grafo;

• il grafo deve esser ben strutturato (ad esempio non devono esistere salti condizionati con zero successori)

Il metodo execute(...) è stato implementato in modo differente rispetto a quello del JustIce: dopo aver verificato i controlli strutturali esegue simbolicamente l’istruzione ed aggiorna il currentInFrame del CFGraph. Non viene effettuato nessun merge: l’in-frame buono da utilizzare per eseguire simbolicamente l’istruzione viene scelto tra quello passato come parametro ed il currentInFrame, ovvero se il frame passato come parametro vale null allora viene utilizzato il currentInFrame. Il metodo che si occupa di passare l’in-frame alla execute(...) è ovviamente la circulationPump(...) perché solo il data-flow analyzer ha una visione globale dello stato della verifica e quindi sa quando il frame deve essere preso dal dizionario (ad esempio quando viene eseguito un nuovo ramo di un salto condizionato) o quando è buono il currentInFrame (ad esempio nella esecuzione di codice senza salti condizionati).

Il merge che veniva effettuato all’inizio della execute(...) del JustIce viene ora fatto successivamente: la data-flow analysis ha infatti ora un aspetto più simile a quello che viene suggerito dalle specifiche Java 2 [vmspecv2 4.9.2] perché ad ogni ciclo viene eseguita l’istruzione corrente (non i successori).

1_{Il nodo END del grafo è un nodo virtuale ed in quanto tale non è associato ad una reale istanza della}

InstrContext: l’END del grafo viene raggiunto quando il successore dell’istruzione punta a null. Anche il grafo del JustIce è stato implementato in questo modo.

(6)

Esaminiamo ora il dizionario: HashMap dictionary della classe CFGraph implementa un dizionario nell’ottica di una futura implementazione polivariante (attualmente le subroutines non vengono trattate): chiave della tabella è l’ultima jsr effettuata e valore è un oggetto della classe TheDictionary. Quest’ultima classe fornisce strutture dati e metodi adatti ad una gestione dinamica e senza duplicati delle entries del dizionario:

private class TheDictionary{

private class Index{...}

private HashMap dictionaryIndex;

private HashMap frameIndex;

private void updateMaxDictionarySize();

private boolean dictionaryMerge(InstructionHandle ih, Frame inFrame);

public Frame dictionaryGetFrame(InstructionHandle ih);

public void dictionaryRemoveUnusedEntries(ArrayList rem);

public boolean dictionaryContains(InstructionHandle ih);

public boolean dictionaryAddIPD(InstructionHandle ih);

public boolean dictionaryAdd(InstructionHandle ih);

... }

Le strutture dati del dizionario sono pensate per associare ad ogni istruzione (presente nel dizionario) un in-frame: per fare questo in linea di principio basterebbe una semplice tabella che ha come chiave l’istruzione e come valore l’in-frame, ma in questo modo non si ha una memorizzazione efficiente a causa dei potenziali frames duplicati. Per risolvere questo inconveniente la tabella è stata divisa in due: c’è un indice che contiene la lista delle istruzioni del dizionario (dictionaryIndex) ed una che memorizza gli in-frames (frameIndex). In particolare la tabella frameIndex è un HashMap che ha come chiave un intero e come valore il frame da memorizzare: il dictionaryIndex è quindi implementato con un HashMap che ha come chiave l’istruzione e come valore un intero, quello utilizzato appunto come chiave dell’altra tabella. Gli HashMap(s) richiedono che

(7)

valori e chiavi siano dei riferimenti, per questo infatti è stata implementata la classe Index:

private class Index{

private int val=0;

public Index(int val){this.val = val;}

public int getVal(){return val;}

public void inc(){val++;}

public void dec(){val--;}

public String toString(){return Integer.toString(val);}

}

Ogni frame memorizzato nel frameIndex è quindi in relazione 1-a-1 con un Index: in questo modo viene semplificato il legame tra le due tabelle [fig. 5.2].

CFGraph TheDictionary InstrContext InstrContext InstrContext ... no d i de l grafo instructionContexts exceptionhandlers ExceptionHandlers dictionary dictionaryIndex frameIndex A B i1 i2 i4 i3 i5 InstructionHandle Index Frame currentInFrame

(8)

Il metodo dictionaryAdd(...) ha come parametro l’istruzione da inserire nel dizionario: il frame da inserire nel dizionario è sempre il currentInFrame quindi non è necessario passarlo come parametro. Questo metodo effettua automaticamente il merge se l’istruzione passata come parametro esisteva già nel dictionaryIndex: il controllo è semplice perché basta ispezionare la tabella delle istruzioni. In particolare se l’istruzione non è presente nella tabella si passa ad ispezionare il frameIndex alla ricerca di un frame uguale: se non dovesse esistere viene cercato un Index disponibile (ovvero un intero non utilizzato come chiave), viene creata una nuova entry nel frameIndex ed associata all’entry nel dictionaryIndex.

Il merge è più complesso perché bisogna fare i controlli aggiuntivi (stack della stessa altezza e con tipi compatibili) perché bisogna evitare frames duplicati: per questo il codice per il merge non è stato scritto direttamente nella dictionaryAdd(...) ma è stato implementato in un altro metodo: dictionaryMerge(...). Il metodo è privato perché solo la dictionaryAdd(...) deve poterlo invocare. In questo metodo bisogna prestare attenzione ad alcuni casi particolari: il frame presente potrebbe essere un ipd e quindi potrebbe anche valere null; per non memorizzare delle null-entries e quindi sprecare spazio viene infatti utilizzato un Index particolare nel dictionaryIndex, in modo da segnalare che l’entry esiste solo virtualmente e che quindi non va fatto un “vero” merge, ma va semplicemente trovato un Index libero e memorizzato il nuovo frame (se non è uguale a nessun frame già presente nel frameIndex). In seguito al merge può ovviamente accadere di generare un frame identico a qualcuno già esistente, è quindi necessario fare attenzione a questo caso.

E’ stato inoltre implementato un metodo dedicato all’inserimento della null-entry dell’ipd per non aumentare troppo la complessità, e quindi la lentezza, della dictionaryAdd(...). Il metodo è dictionaryAddIPD(...): ha solo il compito di aggiungere l’istruzione nel dictionaryIndex.

Per implementare un passaggio particolare della regola branch≠ [cap 3.4] è stato creato il metodo dictionaryRemoveUnusedEntries(...) che provvede a rimuovere dal dizionario tutte le entries relative alle istruzioni passate come parametro.

(9)

I metodi dictionaryGetFrame(...) e dictionaryContains(...) servono ad accedere alle informazioni contenute nel dizionario: il primo restituisce il frame dell’istruzione passata come parametro, il secondo restituisce un booleano che specifica se l’istruzione (passata come parametro) è contenuta nel dictionaryIndex.

Il dizionario ha anche due interi che ne caratterizzano le statistiche: dimensione corrente e dimensione massima raggiunta, reale ed apparente. Le dimensioni reali (currentRealDictionarySize e maxRealDictionarySize) fanno riferimento alla dimensione del frameIndex, mentre le dimensioni apparenti (currentDictionarySize e MaxDictionarySize) fanno riferimento a quelle del dictionaryIndex. Tutti i metodi che modificano il dizionario, prima di terminare, effettuano un update di queste statistiche.

(10)

5.2 La data-flow analysis del verificatore basato sull’ipd

I controlli strutturali e la data-flow analysis vengono implementate dalla classe Pass3bIPDVerifierOpt. Esaminiamone la struttura:

public class Pass3bIPDVerifierOpt extends PassVerifier {

private class WKList{...}

private ArrayList workList;

private int method_no;

private void circulationPump(...);

public VerificationResult do_verify();

public int getMethodNo();

... }

Come per la classe Pass3bVerifier implementata nel JustIce, Pass3bIPDVerifierOpt offre solo due metodi pubblici, do_verify() e getMethodNo(), che hanno il compito di lanciare il passo della verifica e di restituire il numero del metodo che si sta processando, rispettivamente.

La gestione della coda istruzioni (worklist) è cambiata e ciò che prima era rappresentato dalla classe InstructionContextQueue ora viene sostituito dalla classe WKList: compito di questa nuova classe non è solo mantenere la lista delle istruzioni, ma anche memorizzare le informazioni del contesto, cioè le coppie [salto_condizionato_j, m_branch] come indicato nell’algoritmo di verifica basato sull’ipd. In particolare questa informazione è stata integrata nella struttura della worklist attraverso una implementazione di questa come uno stack di code. Ogni coda viene quindi associata ad un salto condizionato: ogni volta che un salto condizionato viene aperto viene creata una nuova coda nella worklist. Ogni coda della worklist rappresenta un salto condizionato aperto ed il numero di istruzioni contenute nella coda è proprio il numero di branch che restano da verificare per il salto condizionato. Un esempio è mostrato in figura 5.3.

(11)

CAPITOLO 5:IMPLEMENTAZIONE DEL VERIFICATORE BASATO SULL’IPD 404 385 388 401 417 414 376 411 373 worklist START END 414 385 404 388 istruzione corrente prima istruzione del prossimo ramo da

verificare questa coda è vuota perché si sta esaminado

l'ultimo ramo della 414 owner della coda

istruzioni verificate istruzioni da verificare istruzione corrente i i i

fig. 5.3: Worklist durante una esecuzione simbolica delle istruzioni

Esaminiamone in dettaglio la struttura:

private class WKList{

private int qe;

private final class InstructionQueue{...}

private ArrayList workList;

public void addQueue();

public void removeQueue();

public boolean currentQueueIsEmpty();

public boolean isEmpty();

...

public InstructionHandle nextInstruction();

public InstructionContext popInstruction();

public void pushInstruction(InstructionContext instr);

public void setQueueOwner(InstructionHandle ih);

public void restartFromQueueOwner(...);

public boolean cbNotClosed(...);

... }

(12)

L’attributo intero privato qe (queue elements) è utile per mantenere il conto di quante istruzioni restano in totale da verificare: è utile per capire quando viene raggiunto in fixed-point dell’iterazione senza invocare troppi metodi. Lo stack di code viene implementato come un ArrayList di oggetti InstructionQueue: come vedremo in dettaglio tra poco ogni InstructionQueue è caratterizzato da una coda di nodi, equivalente a quella creata nel JustIce dalla classe InstructionContextQueue, da un owner della coda, cioè il salto condizionato che ha “generato” la coda, e da un vettore che individua quali sono le entries del dizionario create quando è stata generata la coda.

La classe offre tutti i metodi necessari per la gestione della coda e delle informazioni del contesto integrate; analizziamone i principali metodi:

• addQueue() e removeQueue() aggiungono e rimuovono una coda; in particolare removeQueue() manda anche un messaggio di errore se si tenta di rimuovere una coda non vuota: una coda viene rimossa solo se il salto condizionato è chiuso, cioè se tutti i rami sono stati verificati, ovvero solo se la coda corrente (dello stack di code) è vuota;

• currentQueueIsEmpty() e queueIsEmpty() restituiscono un booleano e verificano rispettivamente se la coda in cima allo stack (di code) della workList è vuota e se la worklist è vuota (qe==0);

• nextInstruction() restituisce la prossima istruzione da eseguire: è un metodo comodo da utilizzare nella circulationPump(...) per caricare dal dizionario il frame della prima istruzione del prossimo ramo di un salto condizionato aperto da verificare; questo metodo non modifica la workList.

• popInstruction() e pushInstruction() modificano la workList effettuando, rispettivamente, il pop ed il push di una istruzione nella coda in testa alla workList.

• setQueueOwner(...) permette di assegnare un owner ad una coda; le code vengono create solo in seguito all’apertura di un salto condizionato. E’ necessario sapere esattamente quali sono i salti condizionati aperti per applicare correttamente le regole specificate nell’algoritmo di verifica basato sull’ipd, in particolare la regola branch≠, che prevede una estrazione di informazioni dal contesto fino ad un determinato salto condizionato (quello che si incontra di

(13)

nuovo). Per maggiori dettagli fare riferimento alle regole dei salti condizionati [cap 3.4] ed alla spiegazione del metodo restartFromQueueOwner(...) qui di seguito.

•

restartFromQueueOwner(...) è il metodo che applica i passaggi c’= extract(c,j) e D↓_c_' come specificato nella regola branch≠ [cap 3.4]: effettua cioè l’estrazione dal contesto di tutte le coppie fino a quella del salto condizionato “più esterno” da ripetere (l’operazione extract(c,j). In definitiva questa istruzione serve a far ripetere, con il nuovo frame, tutti i salti condizionati annidati dentro il salto condizionato da rieseguire) ed elimina dal dizionario tutte le entries create all’apertura dei salti condizionati che vengono estratti dal contesto.

•

cbNotClosed(...) è un metodo utile per capire se un ipd può essere eseguito: più salti condizionati possono infatti avere lo stesso ipd. Per sapere se è possibile eseguirlo devo controllare che nessun altro salto condizionato aperto abbia lo stesso ipd: questo controllo è necessario per una corretta applicazione della regola ipd=0.

Analizziamo ora la struttura della classe InstructionQueue:

private final class InstructionQueue{

private ArrayList queue;

private ArrayList CDEntries;

private ArrayList ec;

private InstructionHandle owner;

public int size();

public boolean isEmpty();

public ArrayList getEC();

public void addCDEntry(InstructionHandle ih);

public void removeCDEntry(InstructionHandle r);

public ArrayList viewCDEntries();

public void pushInstruction(...);

public InstructionContext popInstruction();

public InstructionHandle nextInstruction();

public void setQueueOwner(InstructionHandle ih)

public InstructionHandle getQueueOwner();

... }

(14)

Alcuni metodi hanno nomi identici a quelli della WKList: sono in particolare i metodi per la gestione della singola coda. Alcuni metodi della WKList infatti non fanno altro che fare sanity checks (ad esempio prima di fare il pop di una istruzione controllano che esistano istruzioni) per poi invocare il metodo omologo della InstructionQueue. I campi privati sono:

• queue: è un ArrayList che memorizza i nodi del grafo;

• CDEntries: (created dictionary entries) serve a memorizzare quali sono le entries del dizionario create quando il salto condizionato (owner della coda InstructionQueue) è stato aperto;

• ec: memorizza le execution chains delle istruzioni presenti nella coda; utilizzato anche nel JustIce, è molto utile per il debugging dell’algoritmo e per tracciare le istruzioni che hanno prodotto il fallimento nella verifica;

• owner: memorizza il salto condizionato che ha “generato” la coda. Fa eccezione la coda numero 0, che appartiene sempre al top-level, che viene individuato con un puntatore null.

L’ultimo metodo che resta da esaminare è il “cuore” della classe Pass3bIPDVerifierOpt: la circulationPump(...). Come per il JustIce, questo metodo implementa la data-flow analysis: questa volta naturalmente viene implementata secondo le regole specificare nell’algoritmo di verifica basato sull’ipd. I parametri non sono cambiati: viene passato il grafo (CFGraph) del metodo da verificare, il suo nodo iniziale (start) ed il relativo in-frame (vanillaFrame) e due oggetti derivati dalla classe Visitor per fare i controlli strutturali (icv, instruction constraint visitor) e l’esecuzione simbolica (ev, execution visitor).

La prima cosa da fare questa volta è inizializzare opportunamente il currentInFrame del grafo con la CFGinit(): prima veniva infatti inizializzato l’in-frame della prima istruzione da eseguire perché il dizionario era integrato nei nodi. La prima istruzione viene quindi aggiunta alla worklist e comincia il loop caratteristico della data-flow analysis: le istruzioni presenti nella worklist sono solo quelle che hanno il changed-bit che vale true.

Ad ogni ciclo viene prelevata una istruzione nell’ultima coda della worklist, oggetto di tipo WKList: la condizione di stop del ciclo è che non ci siano più

(15)

istruzioni nella worklist. Ogni coda, come del resto anche la worklist, viene gestita con politica LIFO, ovvero come uno stack. Prima di poter eseguire l’istruzione è necessario controllare se siamo in presenza di un ipd o di un salto condizionato per poter applicare correttamente le regole dell’algoritmo proposto [cap 3.4]. Se non siamo in presenza di ipd o di salti condizionati si procede con un loop standard:

• vengono controllati i vincoli strutturali;

• viene eseguita simbolicamente l’istruzione (se la verifica dei vincoli ha successo);

• viene trovato il successore e messo nella coda in testa alla worklist;

Bisogna notare che, a differenza delle regole della Sun, quando non siamo in presenza di salti condizionati non viene mai effettuato il merge: un verificatore “standard” controllerebbe sempre se esiste un in-frame per il successore dell’istruzione (perché ad esempio potrebbe essere il target di una istruzione di salto), effettuerebbe il merge ed in base al risultato del merge deciderebbe se il changed-bit del successore deve esser messo a true. Fare il merge anche per i targets dei salti incondizionati porta a due vantaggi nell’algoritmo della Sun:

• funziona su qualsiasi grafo, anche quelli con nodi che non raggiungono il nodo END;

• ottimizza il tempo di verifica: viene evitata l’esecuzione di pezzi di codice che cominciano con istruzioni il cui frame è memorizzato nel dizionario (capita spesso nei salti all’indietro [cap 3.7]).

Memorizzare un frame per ogni target porta però a grossi inconvenienti nella verifica delle subroutines: infatti a causa del frame della istruzione che segue la jsr si ha una propagazione corretta dei tipi all’interno della subroutine, ma una propagazione inesatta alla sua fine [cap 4.4.2.1].

Nell’algoritmo proposto il merge viene solo effettuato per l’ipd e per i targets dei salti condizionati. Le condizioni di stop sono espresse nella regola branch≠: ricordiamo che l’algoritmo proposto è ristretto a grafi senza cicli infiniti [cap 3.1].

(16)

Se siamo in presenza di una istruzione di salto condizionato bisogna controllare se il salto condizionato viene incontrato per la prima volta: questo viene fatto con il metodo seenQueueOwner(...) della WKList, basta infatti andare a controllare gli owner(s) delle altre code presenti nella worklist. Quando il salto condizionato viene incontrato per la prima volta, in seguito al controllo dei vincoli strutturali ed all’esecuzione simbolica dell’istruzione, viene creata una nuova coda nella worklist (questa operazione corrisponde alla immissione di una coppia nel contesto) e vi vengono immessi i successori.

Se il salto condizionato era già stato incontrato si procede al test sui targets con il metodo testSuccessorsFrame(...) della classe CFGraph: se i frames del dizionario cambiano allora bisogna ripetere l’esecuzione del salto condizionato (e di tutti i salti condizionati annidati al suo interno), bisogna cioè eliminare dalla worklist tutte le code fino a quella del salto condizionato incontrato (il che corrisponde ad eliminare tutte le coppie dal contesto, fino a quella del salto condizionato da ripetere) ed eliminare dal dizionario tutte le entries create all’apertura dei salti condizionati. Tutte queste operazioni vengono effettuate dalla restartFromQueueOwner(...) della classe WKList. Se invece i frames (salvati nel dizionario) dei targets del salto condizionato non cambiano si salta direttamente all’ipd dell’ultimo, in ordine di esecuzione, salto condizionato aperto (regola branch=): l’ultimo salto condizionato aperto è proprio l’owner della coda corrente.

Se siamo in presenza dell’ipd del salto condizionato aperto è necessario controllare se è possibile eseguirlo o se si deve rimandare l’esecuzione perché restano rami da eseguire. Se tutti i rami del salto condizionato non sono stati eseguiti allora la coda “creata” dal salto condizionato contiene ancora istruzioni: si rimanda quindi l’esecuzione dell’ipd e si carica nel currentInFrame il frame salvato nel dizionario relativo alla prima istruzione del prossimo ramo da eseguire (regola ipd≠0). Se invece la coda è vuota possiamo eliminarla, cancellare dal dizionario tutti

i frame dei targets che non occorrono più (questo corrisponde a togliere dal contesto la coppia [j,0] relativa al salto condizionato che stiamo chiudendo, ed all’operazione D↓_c_' espressa nelle regole) e “potenzialmente” eseguire l’ipd: per capire se l’ipd può essere eseguito bisogna controllare che nessun altro salto condizionato del contesto abbia lo stesso ipd; basta quindi controllare, come al solito, gli owner(s) delle code nella worklist: il controllo viene svolto dal metodo

(17)

cbNotClosed(...) della classe WKList. Questo controllo è espresso implicitamente nella regola ipd=0 perché l’istruzione non viene prelevata (cosa che invece viene fatta nell’implementazione) e quindi viene fatto più volte il controllo i=ipd(top(c)). Ogni volta che si giunge all’ipd si deve comunque fare il merge tra il currentInFrame ed il frame dell’ipd salvato nel dizionario.

I controlli sull’ipd e sui salti condizionati possono essere omessi se nessun salto condizionato è aperto, cioè se siamo al top-level del metodo (owner==null). In definitiva una versione semplificata della circulationPump(...) è la seguente:

private void circulationPump( CFGraph cfg, InstructionContext start,

Frame vanillaFrame, InstConstraintVisitor icv, ExecutionVisitor ev){

HashMap ipds = cfg.getCBIPDs();

WKList workList = new WKList();

cfg.CFGInit(vanillaFrame); workList.pushInstruction(start);

ArrayList ec = new ArrayList();

while(!workList.isEmpty()){

InstructionContext currentInstruction = workList.popInstruction();

boolean execInstruction = true;

InstructionHandle qh = workList.getQueueOwner(); if((InstructionHandle)ipds.get(qh)==currentInstruction.getInstruction()){ while( ((InstructionHandle)ipds.get(qh)==currentInstruction.getInstruction()) && ((workList.currentQueueIsEmpty()) )

{< regola ipd=0 >; qh = workList.getQueueOwner();}

if(!(workList.currentQueueIsEmpty()){execInstruction = false;}

else if(workList.cbNotClosed(currentIPD, cfg)){execInstruction = false;}

}

if(execInstruction == false){< regola ipd≠0 >}

else{

currentInstruction.execute(null, ec, icv, ev);

InstructionContext[] successors = currentInstruction.getSuccessors();

if(successors.length>1){

if(workList.seenQueueOwner(currentInstruction.getInstruction())){

if(cfg.testSuccessorFrame(successors[i].getInstruction())==true){

< regola branch= >

(18)

else{< regola branch≠ >}

} else{ < regola branch∉> } } else if(successors.length==1){workList.pushInstruction(successors[0]);} } } }

Le regole sono state implementate così:

regola ipd=0 :

//merge tra currentInFrame e dizionario per l'ipd

cfg.dictionaryAdd(currentInstruction.getInstruction());

//copia nello stato corrente dello stato ottenuto con il merge

cfg.setCurrentInFrame(cfg.dictionaryGetFrame(currentInstruction.getInstruction()));

//rimuovo entry del dizionario create durante la coda che sto per rimuovere

ArrayList toRemove = workList.viewCDEntries(); cfg.dictionaryRemoveUnusedEntries(toRemove);

//rimuovo coda corrente

workList.removeQueue();

regola ipd≠0 :

//aggiorno il dizionario per l'ipd facendo il merge con lo stato corrente

cfg.dictionaryAdd(currentInstruction.getInstruction());

//determino il prossimo successore

InstructionHandle nextSuccessor_h = workList.nextInstruction();

//copio l'in-frame della prossima istruzione da eseguire nel currentInFrame

(19)

regola branch_∉:

//creo una nuova coda

workList.addQueue();

//segno chi è l'owner

workList.setQueueOwner(currentInstruction.getInstruction());

boolean addIPD = true;

//metto i successori nella coda di esecuzione ed i targets nel dizionario

for(int i=0; i<succ_no; i++){

workList.pushInstruction(successors[i]); if(!cfg.dictionaryContains(successors[i].getInstruction())){ workList.addCDEntry(successors[i].getInstruction()); } cfg.dictionaryAdd(successors[i].getInstruction()); if(ipds.containsValue(successors[i].getInstruction())){ addIPD = false; } } if(addIPD){ /**

* se l'ipd non è tra i targets e non era nel dizionario * allora aggiungo un null-frame

*/ if(!cfg.dictionaryContains(myIPD_h)){ workList.addCDEntry(myIPD_h); cfg.dictionaryAddIPD(myIPD_h); } } regola branch= :

//determino la prossima istruzione: è l’ipd dell’owner della coda corrente

InstructionHandle ipd_h = (InstructionHandle) ipds.get(workList.getQueueOwner()); workList.pushInstruction(cfg.contextOf(ipd_h));

//copio l'in-frame della prossima istruzione nel currentInFrame

Frame nextF = cfg.dictionaryGetFrame(ipd_h); cfg.setCurrentInFrame(nextF);

(20)

regola branch≠ :

workList.restartFromQueueOwner(currentInstruction.getInstruction(), cfg);

/**

* <branch non appartiene> */

//creo una nuova coda

workList.addQueue();

//segno chi è l'owner

workList.setQueueOwner(currentInstruction.getInstruction());

boolean addIPD = true;

//metto i successori nella coda di esecuzione ed i targets nel dizionario

for(int i=0; i<succ_no; i++){

workList.pushInstruction(successors[i]); if(!cfg.dictionaryContains(successors[i].getInstruction())){ workList.addCDEntry(successors[i].getInstruction()); } cfg.dictionaryAdd(successors[i].getInstruction()); if(ipds.containsValue(successors[i].getInstruction())){ addIPD = false; } } if(addIPD){ /**

* se l'ipd non è tra i targets e non era nel dizionario * allora aggiungo un null-frame

*/ if(!cfg.dictionaryContains(myIPD_h)){ workList.addCDEntry(myIPD_h); cfg.dictionaryAddIPD(myIPD_h); } }

Nella implementazione “completa” vengono inoltre effettuati vari sanity checks e controlli aggiuntivi per gestire il caso di ipd=END: il nodo END infatti è un nodo virtuale e vale null e per questo non può esser messo nella coda di esecuzione: bisogna quindi prestare attenzione all’applicazione delle regole.