Résumé technique : Algorithmes efficaces pour les problèmes de satisfaction de contraintes partielles sur les graphes de flux de contrôle

Définition du problème

Ce travail traite du Problème de Satisfaction de Contraintes Partielles (PCSP) sur les graphes de flux de contrôle (CFG) de programmes structurés sans instruction goto. Alors que le Problème de Satisfaction de Contraintes (CSP) standard exige de trouver une affectation de valeurs aux variables qui satisfait toutes les contraintes, les PCSP permettent la violation de certaines contraintes à un coût spécifié. L'objectif est de trouver une affectation qui minimise le coût total des contraintes violées.

Dans le contexte de l'optimisation des compilateurs, de nombreuses tâches peuvent être modélisées comme des PCSP où :

• Les variables correspondent aux sommets (instructions ou blocs de base) du CFG.
• Les contraintes correspondent aux arêtes entre les sommets.
• Les coûts sont associés aux violations d'arêtes (par exemple, déchargements de registres, calculs redondants ou instructions de sélection de banque).

L'article note que les PCSP sont généralement NP-difficiles, même avec de petites tailles de domaine (par exemple, taille 3 ou même taille 2 sous des réductions spécifiques). Cependant, les CFG des programmes structurés possèdent des propriétés structurelles spécifiques — notamment la parcimonie et la décomposabilité — qui peuvent être exploitées pour concevoir des algorithmes efficaces.

Méthodologie

Les auteurs proposent un algorithme général qui exploite la décomposition Série-Parallèle-Boucle (SPL) des CFG, un concept introduit par Cai et Goharshady [7]. Contrairement aux approches précédentes qui reposent sur les décompositions en arbres et les paramètres de largeur de treillis (treewidth), cette méthode utilise la grammaire spécifique des programmes structurés pour décomposer le graphe en composants atomiques et opérations.

Décomposition SPL

L'algorithme opère sur un graphe SPL $G = (V, E, S, T, B, C)$, qui inclut quatre nœuds spéciaux : Début ($S$), Terminaison ($T$), Interruption (Break, $B$) et Continuité (Continue, $C$). La décomposition est définie de manière récursive via trois opérations :

1. Série ($G_1 \otimes G_2$) : Représente l'exécution séquentielle ($P_1; P_2$). Les sommets $T_1$ et $S_2$ sont fusionnés, tout comme les nœuds $B$ et $C$.
2. Parallèle ($G_1 \oplus G_2$) : Représente une ramification conditionnelle ($if \dots then \dots else \dots$). Les nœuds de Début, de Terminaison, d'Interruption et de Continuité sont fusionnés entre les deux sous-graphes.
3. Boucle ($G_1^\circledast$) : Représente une boucle ($while \dots do \dots$). De nouveaux nœuds $S, T, B, C$ sont ajoutés, se connectant aux nœuds internes du sous-graphe pour modéliser les chemins d'entrée, de sortie, d'interruption et de continuité de la boucle.

Algorithme de programmation dynamique

La contribution centrale est un algorithme de programmation dynamique (DP) par remontée (bottom-up) qui calcule le coût minimum pour une décomposition SPL.

• Définition de l'état : Pour chaque nœud $u$ dans l'arbre de décomposition SPL, représentant un sous-graphe $G_u$, l'algorithme calcule une table DP $dp[u, X]$. Ici, $X$ est une affectation de valeurs issues du domaine $D$ aux quatre sommets spéciaux de $G_u$ ($S_u, T_u, B_u, C_u$).
• Logique de transition :
  • Nœuds atomiques : Le coût est calculé directement sur la base de l'arête unique et des valeurs affectées.
  • Nœuds de série : L'algorithme minimise la somme des coûts des sous-graphes enfants ($v$ et $w$) sous réserve de contraintes de compatibilité (ex: $X_v(T_v) = X_w(S_w)$).
  • Nœuds parallèles : Similaire aux nœuds de série mais avec des contraintes d'égalité plus strictes sur les sommets fusionnés. L'algorithme tient compte des doublons d'arêtes potentiels introduits par la fusion.
  • Nœuds de boucle : L'algorithme calcule le coût des nouvelles arêtes introduites par l'opération de boucle et l'ajoute au coût du corps du sous-graphe.
• Complexité : La complexité temporelle pour traiter chaque nœud de la décomposition est de $O(|D|^6)$, où $|D|$ est la taille du domaine. Puisque la taille de la décomposition SPL est linéaire par rapport à la taille du CFG ($|G|$), le temps d'exécution total est de $O(|G| \cdot |D|^6)$. Pour toute taille de domaine fixée, cela produit une solution en temps linéaire.

Contributions clés

1. Généralisation du PCSP : L'article présente un cadre unifié pour résoudre les PCSP sur les CFG, généralisant les algorithmes spécialisés précédents pour l'allocation de registres [7] et l'élimination de redondance partielle spéculative optimale par cycle de vie (LOSPRE) [6].
2. Efficacité basée sur SPL : En utilisant les décompositions SPL plutôt que les décompositions en arbres, les auteurs évitent la dépendance aux paramètres de largeur de treillis. Cela permet d'obtenir un algorithme plus simple qui exploite directement la structure des programmes structurés.
3. Sélection de banque optimale : Les auteurs appliquent ce cadre général à la Sélection Optimale de Placement d'Instructions de Sélection de Banque, un problème précédemment résolu à l'aide de méthodes basées sur la largeur de treillis [32].
4. Validation expérimentale : L'implémentation démontre que l'approche basée sur SPL surpasse significativement l'approche de pointe basée sur la largeur de treillis pour la sélection de banque, atteignant des temps d'exécution environ quatre fois plus rapides.

Résultats expérimentaux

Les auteurs ont implémenté l'algorithme en C++ et l'ont intégré au Small Device C Compiler (SDCC). Les expériences ont été menées sur la suite de tests de régression du SDCC couvrant trois architectures : HC08, Z80 et MCS51.

• Performance vs État de l'art : Comparée à l'approche basée sur la largeur de treillis de [32] (qui a un temps d'exécution de $O(|G| \cdot tw(G) \cdot |D|^{tw(G)+1})$), l'algorithme proposé a obtenu des temps d'exécution moyens environ 4 fois plus rapides sur toutes les architectures testées.
  • Exemple (HC08) : 1 998,3 ns (proposé) contre 8 558,8 ns (référence).
• Comparaison avec SAT/ILP : La méthode a également été comparée aux solveurs SAT (Kissat) et de programmation linéaire en nombres entiers (Gurobi). L'algorithme proposé s'est avéré presque 10 fois plus rapide que l'approche ILP et environ 1 000 fois plus rapide que le solveur SAT.
• Optimalité : Tant la méthode proposée que la référence [32] produisent des solutions optimales identiques pour la sélection de banque ; l'amélioration concerne strictement l'efficacité computationnelle.

Signification et affirmations

L'article affirme que l'algorithme proposé fournit une solution en temps linéaire pour une large classe de problèmes d'optimisation de compilateur modélisés comme des PCSP sur des CFG de programmes structurés, à condition que la taille du domaine soit fixée.

La signification réside dans :

• Unification : Il consolide des tâches d'optimisation distinctes (Allocation de registres, LOSPRE, Sélection de banque) sous un seul cadre algorithmique général.
• Accélération pratique : La suppression de la dépendance au paramètre de largeur de treillis et l'utilisation des décompositions SPL résultent en un facteur constant nettement plus faible en pratique, menant à des accélérations substantielles dans les scénarios réels de compilateurs.
• Scalabilité : La dépendance linéaire vis-à-vis de la taille du graphe ($|G|$) rend l'approche hautement scalable pour de grandes bases de code, surpassant à la fois les méthodes paramétrées par décomposition en arbres et les solveurs généraux pour problèmes NP-difficiles (SAT/ILP).

Les auteurs soulignent que bien que la complexité théorique dépende de $|D|^6$, dans les applications concrètes de compilateurs (comme la sélection de banque où $|D|$ est petit et constant), l'algorithme se comporte comme un véritable solveur en temps linéaire, offrant une alternative supérieure aux heuristiques et aux algorithmes paramétrés existants.