11. Analisi dei loop

Nella pagina precedente abbiamo notato che possiamo convertire particolari configurazioni di blocchi base in un’istruzione condizionale “if-then-(else)”. Tutte le istruzioni “if” hanno salti in avanti, ovvero la destinazione dei salti è un codice che non è stato ancora eseguito.

I compilatori usano istruzioni condizionali per controllare un altro costrutto di alto livello: queste sono istruzioni che implementano loop. In questo caso, la destinazione del salto è il codice che è già stato eseguito almeno una volta.

Potremmo semplicemente lasciare le istruzioni condizionali come coppie “if-goto”, come nelle immagini della pagina precedente, poiché questo è ciò che il processore esegue realmente (i processori non conoscono i loop tranne quando usano istruzioni molto specifiche, come il REP in x86), ma ciò non chiarirebbe cosa fa il codice, in quanto il lettore dovrebbe ricostruire il loop controllando la destinazione del goto. Quindi proveremo a scoprire i loop dalla configurazione dei blocchi di base.

Ogni ciclo può essere descritto con un’istruzione “do-while”.

Il ciclo “while” (ciclo pre-testato) è un caso speciale di un ciclo “do-while”, in cui la condizione inferiore è sempre vera e la prima istruzione del ciclo è un “if” che salta fuori dal ciclo .

Il ciclo “for” è un caso speciale del ciclo “while”.

Do-while

Lhead:
   do {
      statements;
Lcontinue:
   } while(cond);
Lbreak:

While:

Lhead:
   do {
Lcontinue:
      if(cond)
         goto Lbreak;
      statements;
   } while(true);
Lbreak:

For loop:

Lhead:
   var = init_expr;
   if(cond)
      goto Lbreak;
   do {
      statements;
Lcontinue:
      var += incr_expr;
   } while(cond);

Per identificare i cicli abbiamo bisogno di sapere dove si entra nel ciclo, in modo da poter inserire lì l’istruzione “do”, e dove finisce il ciclo, in modo che tutte le istruzioni che appartengono al ciclo possano essere inserite all’interno dell’istruzione “do”.

Il punto di ingresso di un ciclo è in quello che viene chiamato il blocco " header " del ciclo. Tutti i percorsi di esecuzione devono passare attraverso l’header block per entrare nel ciclo (cioè non consideriamo i cicli con più punti di ingresso, anche se questi sono possibili).

Per trovare i loop, prima calcoliamo l’insieme di " dominatori " per ogni blocco nel grafico del flusso di controllo.

Non descriveremo il fondamento teorico dei dominatori. Molte risorse sono disponibili su Internet.

Invece, stiamo mostrando l’implementazione pratica dell’algoritmo che trova l’insieme di dominatori per ogni blocco.

Per prima cosa usiamo un vettore di bit in cui ogni bit corrisponde a un blocco di base nel grafico del flusso di controllo. Associamo uno di questi vettori di bit a ciascun blocco di base.

Quindi usiamo le operazioni and e or bit-wise per ridurre il numero di bit impostati in ciascun vettore, fino a quando non ci sono più modifiche.

Ecco l’algoritmo:

ComputeDominators()
{
   int nBlocks = block_list.size();
   int i = 0;
 
   for each block in block_list {
      block->id = i++;
      block->dominators = new BitVector(nBlocks)
      block->dominators->SetAllBitsTo(1)
   }
 
   block = block_list[0]
   block->dominators->SetAllBitsTo(0)
   block->dominators->SetBit(block->id)
 
   BitVector T(nBlocks)
 
   do {
      changed = false
 
      for each block in block_list {
 
        if (block == entry_block)
            continue
 
        for each pred in block->predecessors {
            T.SetAllBitsTo(0)
            T.Or(block->dominators)
            block->dominators->And(pred->dominators)
            block->dominators->SetBit(block->id)
            if (block->dominators != T)
                changed = true
 
        }
 
      }
 
   } while (changed);
}

Sulla base delle informazioni sui dominatori possiamo calcolare l’insieme di blocchi di base che appartengono a ciascun ciclo utilizzando le seguenti due funzioni:

NaturalLoopForEdge(Block header, Block tail)
{
    Stack workList;
    Loop  loop;
 
    loop = new Loop();
 
    loop->header = header
    loop->blocks += header
 
    if header != tail {
        loop->blocks += tail
        workList += tail
    }
    while workList not empty {
        block = workList.pop
        for each pred in block->predecessors {
            if not loop->find(pred) {
                loop->blocks += pred
                workList += pred
            }
        }
    }
    return loop
}
 
ComputeNaturalLoops()
{
    LoopSet   loopSet;
 
    for each block in block_list {
        if (block == entry_block)
            continue

        for each succ in block->successors {
 
            // Every successor that dominates its predecessor
            // must be the header of a loop.
            // That is, block -> succ is a back edge.
 
            if block->dominators->find(succ)
                loopSet += NaturalLoopForEdge(succ, block)
 
        }
    }
}

L’algoritmo funziona così: per prima cosa troviamo i back edge, cioè i punti in cui l’esecuzione risale a un blocco precedentemente visitato. Questo viene fatto controllando se il successore di un blocco domina il blocco stesso. Il blocco successore sarà l’intestazione del ciclo.

Poi, poiché per raggiungere il blocco (di coda) l’esecuzione deve passare attraverso il suo dominatore, possiamo attraversare i predecessori di ogni blocco a partire dalla coda, fino a raggiungere il blocco di intestazione (che è sempre nel ciclo poiché lo mettiamo lì al inizio di NaturalLoopForEdge() ).