Este trabalho teve como objetivo construir uma ferramenta capaz de determinar a freqüência com que cada tipo de instrução assembly é executada em um programa, dado seu código fonte em C.

Para esta freqüência ser determinada, é necessário que estruturas que gerem instruções de desvio condicionais (i.e. ifs e loops) sejam previamente "anotadas" pelo projetista, fornecendo em forma de comentário no código C. No caso de um if, deve ser inserido a probabilidade da condição do if ser verdadeira, e no caso de um loop, a quantidade de iterações.
--

O primeiro passo a ser tomado é compilar o código C, requisitando ao compilador algumas informações de debug. Durante o nosso trabalho, foi utilizado o compilador GCC para processadores ARM, com as opções -S e -g. A opção -S é necessária para obter a saída em código assembly legível em editores de texto (extensão .s) e a opção -g fornece informações de debug, como comentários que indicam o número da linha do código C que gerou as linhas assembly subseqüentes.

Estas informações de debug serão úteis para determinar a probabilidade de um desvio condicional ser tomado, tornando possível saber a linha C que gerou aquela instrução de branch condicional e capturando através do comentário inserido nesta linha (C) a probabilidade procurada.

Com o código assembly e as probabilidades de desvio em mãos, é possível criar um grafo de fluxo de controle (CFG) que representa o funcionamento do programa, onde cada nó representa um trecho do código, cada aresta representa um branch, e os pesos das arestas representam as probabilidades de desvio.

Este grafo é convertido para uma Cadeia de Markov irredutível, adicionando uma aresta com peso (probabilidade) 1, que parte do nó inicial do grafo até o nó final.