Regole del verificatore ipd
Le regole del verificatore ipd possono essere formalizzate e scritte in forma compatta utilizzando la seguente notazione1:
- branch(m) è una istruzione di salto condizionato con m targets: per semplicità faremo riferimento ad istruzioni che prelevano un intero dallo stack e lo confrontano con un altro intero salvato nel registro specificato come operando (ad esempio esistono anche istruzioni if che confrontano due interi dello stack, ed altre che hanno invece come operando un riferimento ad un oggetto perché controllano se vale null: per maggiori dettagli far riferimento dalle specifiche Java 2 [vmspecv2])
- L = {L1,...,Lm}è l’insieme dei targets di un salto condizionato; - ipd(j) è l’ipd del salto condizionato j;
- c=[j,m]·c’ è la struttura del contesto e sta ad indicare che in testa al contesto c c’è la coppia [j,m], ovvero ‘·’ è l’operatore di concatenazione (il contesto è una struttura dati organizzata a stack);
- <h, c, S, D> è la struttura che caratterizza uno stato dell’interprete astratto:
h è l’istruzione da eseguire simbolicamente, c è il contesto, S è il suo stato
(ovvero il suo in-frame) e D è il dizionario. Ogni regola è caratterizzata da una transizione di stato dell’interprete astratto;
- {M,St} è la struttura di un frame: variabili locali (M) e stack (St);
- top(c) restituisce l’istruzione j della coppia {j,m} che si trova in testa al contesto (il contesto è una struttura organizzata a stack);
- extract(c,j) restituisce un contesto c’ da cui sono state estratte tutte le coppie {l,k} fino alla coppia {j,m} inclusa: extract(c1▪{j,m}▪c2) restituisce
c2;
- j+1 è il successore naturale di una istruzione di salto condizionato j;
- restituisce il frame, salvato nel dizionario, relativo al k-esimo target
(L k
L
D
k);
- le 4 operazioni consentite sul dizionario sono:
o D↑j[DL:=S] (creazione o eventuale aggiornamento delle entries
relative ai targets dell’insieme L={L1,..,Lm} e all’ipd del salto condizionato j2 );
o D (rimozione delle entries relative alle istruzioni di salto condizionato che non sono presenti in nessuna coppia del contesto
↓c
3);
o D[Dk:=S] (aggiornamento della k-esima entry del dizionario).
o lub(S,Dh) (least upper bound, ovvero merge tra il frame corrente S e
l’entry del dizionario Dh relativa all’istruzione h-esima)
- le pre-condizioni sono specificate in uno statement if e la regola può essere applicata solo se le sue pre-condizioni sono tutte soddisfatte.
∉
branch
<j,c,S,D>→< j+1, [j,m]▪c, {M,St}, D↑j[DL:=lub(DL ,{M,St})] >
if ( (j∉c) AND (S={M,int▪St}) )
branch non appartiene: Se j, istruzione di salto condizionato, non appartiene al
contesto (j∉c) e il frame corrente è caratterizzato da uno stack con in cima un
cima al contesto viene inserita la coppia relativa al salto condizionato necessaria per contare quanti rami restano da verificare ([j,m]▪c), l’istruzione viene eseguita simbolicamente cioè si preleva l’intero in cima allo stack e quindi il nuovo frame è {M,St}, si aggiungono al dizionario le entries necessarie per la verifica del blocco cioè vengono create, aggiornate se già esistenti, le entries relative ai targets e all’ipd.
branch=
<j,c,S,D>→< ipd(top(c)), c, Dipd(top(c)), D >
if ( (j∈c) AND (S={M,int▪St}) AND (DL=lub(DL ,{M,St})) )
branch uguale: Se j, istruzione di salto condizionato, appartiene al contesto (j∈c) e
il frame corrente è caratterizzato da uno stack con in cima un intero (S={M,int▪St}) e un eventuale merge tra l’out-frame corrente e le entries dei targets contenute nel
dizionario NON provoca un cambiamento nel dizionario (DL=lub(DL ,{M,St})) allora
lo stato corrente dell’interprete astratto effettua questa transizione: la prossima istruzione da esaminare è l’ipd del salto condizionato in cima al contesto (ipd(top(c))), il contesto resta invariato, il nuovo frame è quello salvato nel dizionario e relativo alla prossima istruzione da eseguire, cioè relativo all’ipd (Dipd(top(c))), il dizionario resta invariato.
branch≠
<j,c,S,D>→< j, c’= extract(c,j), S, D↓c' >
branch diverso: Se j, istruzione di salto condizionato, appartiene al contesto (j∈c) e il frame corrente è caratterizzato da uno stack con in cima un intero (S={M,int▪St}) e un eventuale merge tra l’out-frame corrente e le entries dei targets contenute nel
dizionario provoca un cambiamento nel dizionario (DL≠lub(DL ,{M,St})) allora lo
stato corrente dell’interprete astratto effettua questa transizione: la prossima istruzione da esaminare resta l’istruzione di salto corrente (j), vengono estratte dal contesto tutte le coppie fino a quella (compresa) del salto condizionato corrente
(c’= extract(c,j)), il frame resta invariato (S), vengono lasciate nel dizionario SOLO
le entries necessarie alla verifica dei salti condizionati rimasti nel nuovo contesto c’ (D↓c').
ipd≠0
<i,c,S,D>→< Lk, [j,k-1]▪c’ ,DL′k, D’=D[Di:=lub(S,Di)] >
if ( (c=[j,k]▪c’) AND (k≠0) AND (i=ipd(j)) )
ipd diverso da zero: Se j, istruzione di salto condizionato, si trova in testa al contesto (c=[j,k]▪c’) con un contatore di rami da verificare diverso da zero (k≠0) e l’istruzione corrente (i) è ipd di quel salto condizionato (i=ipd(j)), allora lo stato corrente dell’interprete astratto effettua questa transizione: l’ipd non viene eseguito e la prossima istruzione da esaminare è il prossimo target del salto condizionato j
(Lk ), viene decrementato il contatore del salto condizionato j cioè quello in cima al
contesto ([j,k-1]▪c’), il nuovo frame è quello salvato nel dizionario e relativo alla
prossima istruzione da eseguire, cioè relativo al k-esimo target ( ), avendo cura,
prima di caricare il frame dal dizionario, di aggiornare l’entry relativa all’istruzione attuale
′ k
L
D
4, che è un ipd, nel dizionario (D’=D[D
ipd=0
<i,c,S,D>→< i, c’, lub(S,Di), D↓c' >
if ( (c=[j,0]▪c’) AND (i=ipd(j)) )
ipd uguale a zero: Se j, istruzione di salto condizionato, si trova in testa al contesto (c=[j,k]▪c’) con un contatore di rami da verificare uguale a zero (k=0) e l’istruzione corrente (i) è ipd di quel salto condizionato (i=ipd(j)), allora lo stato corrente dell’interprete astratto effettua questa transizione: l’ipd è pronto per essere eseguito, quindi la prossima istruzione da esaminare è proprio l’istruzione corrente (i), viene estratta dal contesto la coppia relativa al salto condizionato j, quindi il contesto diventa c’, il nuovo frame è quello ottenuto dal merge tra l’in-frame
corrente e quello salvato nel dizionario lub(S,Di), vengono estratte dal dizionario
tutte le entries che non sono target o ipd dei salti condizionati che restano nel contesto c’ (D↓c').
Per uno studio più approfondito sull’algoritmo ipd e le sue regole si rimanda al lavoro di Masci Paolo [TPMasci].
