Optimizing the translation out-of-SSA with renaming constraints

Static Single Assignment form is an intermediate representation that uses phi instructions to merge values at each confluent point of the control flow graph. phi instructions are not machine instructions and must be renamed back to move instructions when translating out of SSA form. Without a coalescing algorithm, the out of SSA translation generates many move instructions. Leung and George use a SSA form for programs represented as native machine instructions, including the use of machine dedicated registers. For this purpose, they handle renaming constraints thanks to a pinning mechanism. Pinning phi arguments and their corresponding definition to a common resource is also a very attractive technique for coalescing variables. In this paper, extending this idea, we propose a method to reduce the phi-related copies during the out of SSA translation, thanks to a pinning-based coalescing algorithm that is aware of renaming constraints. This report provides also a discussion about the formulation of this problem, its complexity and its motivations. We implemented our algorithm in the STMicroelectronics Linear Assembly Optimizer. Our experiments show interesting results when comparing to the existing approaches of Leung and George, Sreedhar et al., and Appel and George for register coalescing.La forme SSA est une représentation intermédiaire de compilateur quiutilise des fonctions virtuelles phi pour fusionner les valeurs à chaque point de confluence du graphe de contrôle. Les fonctions phi n’existant pas physiquement,elles doivent être remplacées par des instructions move lors de la translation en code machine. Sans coalesceur, la translation hors-SSA génère beaucoup de move.Dans cet article, nous proposons une extension de l’algorithme de Leung et George [8] qui effectue la minimisation de ces instructions de copie. Leunget al. proposent un algorithme de translation d’une forme SSA pour du code assembleur, mais non optimisé pour le remplacement des instructions phi. Par contre, ils utilisent la notion d’épinglage pour représenter les contraintes de renommage. Notre idée est d’utiliser cette notion d’épinglage afin de contraindre le renommage des arguments des phi pour faire du coalescing. C’est une formulation du problème de coalescing non équivalente au problème initial toujours considéré comme ouvert dans la littérature [8, 10]. Nous prouvons néanmoins la NP-complétude de notre formulation, une conséquence de la preuve étant la NP-complétude du problème initial en la taille de la plus grande fonction phi.Enfin, nous avons implémenté notre algorithme dans le LAO [5], optimiseur d’assembleur linéaire. La comparaison avec différentes approches possibles fournit de nombreux résultats intéressants. Nous avons aussi essayé, à l'aide d’exemples faits à la main, d’expliquer les avantages et limitations des différentes approches