Optimisation des compilateurs/Les optimisations des branchements

Les branchements sont une véritable plaie pour les processeurs modernes dotés d'un pipeline. Certes, les processeurs modernes disposent de techniques pour réduire leur impact sur les performances, la plus connue étant de loin la prédiction de branchements. Cependant, éliminer des branchements a quand même des effets sur les performances. Elle libère de la place dans les tampons de l'unité de prédiction de branchement (les Brnch Target Buffer), elle améliore l'utilisation du pipeline, etc. Mais surtout, supprimer des branchements permet aux autres optimisations du compilateur de mieux faire leur travail. En effet, les branchements entrainent l'apparition de dépendances de contrôles, qui empêchent certains déplacements de calculs : il est impossible de déplacer certains calculs avant un branchement, de les faire sortir d'une fonction, etc. Pour comprendre cela, rappelons que la majorité des optimisations travaillent sur des suites d'instructions linéaires, libres de tout branchements, ces suites portant le nom de blocs de base (basic blocs, en anglais). Les ré-ordonnancements d'instructions, ainsi que certaines optimisations, ne peuvent se faire qu'à l'intérieur d'un de ces bloc de base. Éliminer des branchements permet d'obtenir des blocs de base plus gros, donnant plus de possibilités de ré-ordonnancement ou de simplifications au compilateur. Bref, éliminer des branchements est toujours une bonne chose, et nous allons voir comment le compilateur s'y prend pour ce faire.

L'inlining

Une autre optimisation bien connue est l'inlining. Cette technique consiste à éliminer les appels de fonction d'un programme : le corps de la fonction est intégralement recopié à chaque endroit où celle-ci est appelée. Les gains liés à cette optimisation ont plusieurs origines :

• En premier lieu, cela permet d'éliminer l'appel de la fonction, ainsi que tout le code qui prépare l'appel, qui sauvegarde les registres, etc. Celui-ci étant assez couteux (sauvegarder des registres et empiler les arguments n'est pas gratuit), le gain en performance peut être substantiel.
• Dans certains cas, cela permet aussi d'améliorer l'usage de la mémoire cache. En effet, l'inlining donne un code plus linéaire. Après inlining, le processeur balaye la mémoire octet par octet, au lieu de sauter d'une fonction à une autre à chaque appel. La suite d'instruction obtenue repsecte donc mieux le principe de localité spatiale, ce qui est apprécié autant par le cache que par les circuits de prefetching.
• L'inlining permet aussi à d'autres optimisations de fonctionner plus efficacement, comme la propagation de constantes. Il permet aussi d'obtenir des blocs de code linéaires de « grande taille », permettant au ré-ordonnancement d'instructions de fonctionner au mieux.

Il faut remarquer que cette technique a tendance à fortement augmenter la taille du code : au lieu d'un seul exemplaire de la fonction, celle-ci est recopiée en autant d'exemplaires qu'il y a de sites d'appel. Le programme final prend donc plus de place. Il faut signaler que cette augmentation de la taille du code peut avoir un effet négatif sur les performances, en perturbant l'usage de la mémoire cache. En effet, qui dit code plus gros dit plus de mémoire cache utilisée. On comprend pourquoi cette optimisation n'est effectuée que pour des fonctions relativement petites, pour éviter de trop faire augmenter la taille du code et de nuire aux performances.

Le Bound Cheking

Dans certains langages de programmation, les accès à un tableau avec un indice invalide vont lever une exception ou faire planter le programme. Pour cela, le compilateur insère des comparaisons qui vérifient la validité de l'indice. Ces comparaisons prennent évidemment du temps de calcul, et le compilateur dispose d'optimisations pour en éviter qui seraient inutiles. Il peut notamment prouver que certains morceaux de code ne peuvent pas donner lieu à des accès en dehors du tableau, pour éviter d'ajouter les tests de validité de l'indice. C'est notamment le cas avec ce code :

int sum = 0;

for (int i = 0; i < Array.size(); ++i)
{
    sum += Array[i];
}

La fusion de branchements

Maintenant, prenons le cas d'un branchement A, dont l'instruction/adresse de destination est un autre branchement B, qui lui-même pointe sur une instruction C. Au cours de l'exécution, le branchement va envoyer le processeur sur B, qui va aussitôt brancher vers C : autant brancher directement vers C. Dans ce cas, le compilateur va modifier l'adresse de destination du branchement A pour qu'il pointe directement sur l'instruction C.