# L'optimisation de code pourra-t-elle s'affirmer grace aux attributs semantiques ?

Mahvash Michaneh Amirchahy, Danielle Neel

► To cite this version:

Mahvash Michaneh Amirchahy, Danielle Neel. L'optimisation de code pourra-t-elle s'affirmer grace aux attributs semantiques?. [Rapport de recherche] IRIA-RR-162, IRIA. 1976, pp.46. hal-04716384

HAL Id: hal-04716384

https://inria.hal.science/hal-04716384v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

L'OPTIMISATION DE CODE
POURRA-T-ELLE
S'AFFIRMER GRÂCE AUX
ATTRIBUTS SÉMANTIQUES?

M. Amirchahy, D. Néel
(présenté par C. Pair)

Rapport de Recherche N° 162

Mars 1976
# Translation of Fuzzy Queries for Relational Database System

SHI-KUO CHANG AND JYH-SHENG KE

*Abstract*—The concept of a database skeleton which reflects both the user's conception of the real world and the system's understanding of the interrelationships among database entities is described. It consists of a conceptual schema (conceptual graphs) and a relational schema (information graph). With the aid of the database skeleton, fuzzy queries can be translated and disambiguated by analyzing the queries using the conceptual graphs of a database skeleton. The query language XQL is introduced, and the XQL translator is described in some detail.

*Index Terms*—Artificial intelligence, database management system, database modeling, fuzzy query, intelligent user interface, query translation.

## I. INTRODUCTION

RECENT advances in database systems design have indicated the desirability of flexible, intelligent user interfaces. An intelligent user interface serves as an intermediary between the user and the database system. A central issue in the design of an intelligent user interface is the representation and modeling of a user's knowledge of the meaning of a collection of data. The advantages of a user's information model are: 1) it can facilitate specifying the contents and meaning of a collection of data; 2) it can be used as a semantic basis for query languages; and 3) it can support approximate reasoning to infer conclusions that are not explicitly stated.

In previous papers [12], [13] we have presented the concept of a database skeleton for the representation of a user's knowledge of a collection of data. A database skeleton is a concise description of a collection of data as understood by the user. It contains user-defined database properties, such as functional and semantic interrelationships among database entities, domain specifications for the attributes, contents description for the files, etc. The database skeleton also includes definitions of descriptors and files, and contents descriptions for files. In [12] it is shown that the problem of logical database synthesis can be formulated as a problem of completing a partially specified database skeleton by introducing additional interrelationships among database entities. Depending upon the types of interrelationships to be added, different data models—relational, network, or hierarchical—can be derived from the database skeleton. With the database skeleton, the problem of logical database synthesis from multiple user views can be treated in a systematic way.

Manuscript received April 7, 1978; revised October 7, 1978.

The authors are with the Knowledge Systems Laboratory, Department of Information Engineering, University of Illinois, Chicago, IL 60680.

In this paper we further generalize the concept of the database skeleton to include conceptual and semantic information. This generalized database skeleton is a model which reflects both the user's conception of the reality and the system's understanding of the interrelationships among database entities.

The formalism we use to represent the user's conceptions about the real world is a *conceptual schema* which is a variation of Sowa's *conceptual graphs* [57]. The formalism we use to represent the database from the system's view is an extended *relational schema* of Codd's third normal form, which is called an *information graph* [12].

The difference between the relational schema and the conceptual schema is that the relational schema is a description of the system's view of the stored data, and the conceptual schema is a description of the user's view at the conceptual level. The two schemas represent two different levels of database abstraction and are both needed for a full description of the database. We will call the integration of the conceptual schema and the relational schema the *database skeleton*.

In this paper we apply the concept of a database skeleton to the translation of *fuzzy queries*. Most query languages require that the user specify his queries precisely. However, with an intelligent user interface, it is often desirable that the user need not precisely specify his information retrieval requests. In this paper we describe a query language called *extensible query language (XQL)*, which realizes the above-mentioned objective to a certain extent. An imprecise, or fuzzy, query can be stated without mentioning file names and how files are to be linked. In a fuzzy query semantic information can also be incorporated to serve as clues to query translation. Moreover, fuzzy concepts can also be used in the fuzzy query. This query language is motivated by previous researches on database semantics [31], [36], [43], [46], [50], [54], [67]. XQL is based upon EQL, the elementary query language, which has been described in a previous paper [13]. The reader is referred to the following references for other approaches in query language design: a) frame-oriented languages [2], [3]; b) relational calculus [20]; c) relational algebra [21]; d) structure-oriented languages [1], [4], [6], [8], [24], [28], [42]; e) graphics-oriented languages [35], [39], [51], [69]; f) natural languages [22], [26], [27], [32], [34], [37], [41], [65]; and g) structure-free languages [13], [48]. The query language XQL described in this paper belongs to the last category of structure-free languages.
<figure><img src="image_3.png" /><figcaption>Fig. 1. The intelligent coupler.</figcaption></figure>

With the aid of the database skeleton, fuzzy queries can be translated and disambiguated by analyzing the queries using the conceptual graphs of a database skeleton. Therefore, the database skeleton is not only useful as a user's model for data definition, but also suitable for translating user's imprecise queries, and similar techniques of manipulation of abstract graphs can be applied to the solution of both problems.

In Section II the concept of an intelligent coupler is introduced. The definition of conceptual graphs is presented in Section III, followed by discussion of conceptual generality (Section IV) and the representation of logical connectives (Section V). The generation of virtual entities, and the representation of fuzzy concepts, are discussed in Section VI. Section VII presents the concept of query graphs, and Section VIII describes the extensible query language XQL and its translator in some detail. The XQL translator has been implemented using the C programming language and runs on a PDP11/40 minicomputer under the UNIX operating system. More details on the XQL translator, query optimization techniques, techniques for constructing the database skeleton, and a formal model for the database skeleton, can be found in [29], [30].

## II. THE INTELLIGENT COUPLER

In this section the concept of an intelligent coupler is introduced. More details on the intelligent coupler concept can be found in [10].

The intelligent coupler serves as the intermediary between the end user and the distributed database system. The intelligent coupler listens to the user's retrieval requests, helps the user formulate his retrieval requests correctly, efficiently translates user's retrieval requests into a database retrieval command language, and obtains authorization from the system for data retrieval and/or update. In short, the intelligent coupler serves as the user's surrogate in a distributed database system. However, from the user's viewpoint, the intelligent coupler also serves as the system's surrogate.

The term "coupler" is conceptually important. It implies that the main function of an intelligent coupler is to couple the user with the system. It also implies that the user and the system are shielded from one another by this coupler. The coupling can be tight or loose, depending on the importance and privileges of the particular user in question. For the most privileged user, the coupling can be very tight, and almost nothing is shielded from him. For the casual end user, the

coupling can be rather loose, and he can only access a limited portion of the integrated database.

The intelligent coupler uses the database skeleton to couple the user with the distributed database system. Depending on the degree of precision of the database skeleton, the coupling can be made tight or loose, or any degree between the two extremes.

The main functions of the intelligent coupler fall into four categories: intelligent data entry (IDE), semantic data compression, query translation, and authorization and access control.

The intelligent coupler consists of two parts: a user coupler and a database coupler. The user coupler is the part of the intelligent coupler dealing with the user. It consists of the following modules, whose interrelationships are illustrated in Fig. 1: 1) the query handler, 2) the defuzzifier, 3) the query tester, and 4) the query translator.

The query handler interacts with the user and decodes the user's query. If the query contains ambiguous names, such as descriptor names that are not attached to files, or files with unspecified locations, or unspecified files, or arbitrary mixture of descriptor names belonging to different files, then the defuzzifier is invoked to disambiguate the query. When a test query has been satisfactorily formulated, the query tester can be invoked to test run this query on typical records. Finally, the query translator can be used to translate this original query into network compatible query commands. The query translator uses the statistical contents description of files to optimize the translated query command. Thus, the query translator acts like an optimizing compiler for language compilation.

The second part of the intelligent coupler is the database coupler, which couples the user with the distributed database system. The database coupler performs several important functions: access authorization, maintenance of the database skeleton, and system recovery. The authorization controller issues access requests by checking the access authorization hierarchy in the database skeleton. The skeleton maintenance module periodically performs maintenance operations to keep the skeleton up to date and forget useless data. In case of system failures, the maintenance module always takes control and attempts to redefine such vital items as location maps, so that harmful retrieval/update commands can be prevented from entering the system. The deadlock controller prevents deadlock situations from occurring, and the measurement module collects user profiles and usage statistics.

In the remainder of this paper we will concentrate on the user coupler of the intelligent coupler.
# L'OPTIMISATION DE CODE POURRA-T-ELLE S'AFFIRMER
GRÂCE AUX ATTRIBUTS SÉMANTIQUES ?

M. Amirchahy, D. Néel

(présenté par C. Pair)

IRIA/LABORIA

<figure><img src="image_4.png" /></figure>

## Résumé :

Les méthodes d'optimisation interviennent pendant la phase de compilation des programmes, pour améliorer leur code intermédiaire selon un compromis entre l'encombrement en mémoire et le temps d'exécution. Cependant aucune garantie n'est donnée en ce qui concerne les compilateurs optimiseurs. Ceci est dû au manque de rigueur sémantique des langages de programmation. Grâce à la méthode de compilation par attributs, la description sémantique des langages va bénéficier de la rigueur de leur définition syntaxique et les optimisations traitées seront plus formellement définies.

## Abstract:

Optimization methods intervene during the compile-phase of programs to improve their intermediate code according to some space/time criterion. However, owing essentially to a lack of rigour in semantic definition of languages, no correctness guarantees are provided as to optimizing compilers. The development of attributed grammars and compiling by the method of attributes tend to remove this major handicap. And a more formal definition of optimizations becomes feasible.
<figure><img src="image_5.png" /></figure>
## SOMMAIRE

<table><tr><td>Introduction</td><td>1</td></tr><tr><td>I - Classification et revue des optimisations</td><td>3</td></tr><tr><td>I - 1. Optimisations rencontrées dans la littérature</td><td>4</td></tr><tr><td>I - 1.1. Optimisations locales</td><td>6</td></tr><tr><td>I - 1.2. Optimisations globales</td><td>7</td></tr><tr><td>I - 1.3. Optimisations liées au calculateur</td><td>9</td></tr><tr><td>I - 2. Optimisations supplémentaires</td><td>10</td></tr><tr><td>II - La méthode des attributs</td><td>11</td></tr><tr><td>II - 1. Exemple</td><td>12</td></tr><tr><td>II - 2. Application à la métacompilation</td><td>16</td></tr><tr><td>II - 2.1. Possibilités</td><td>17</td></tr><tr><td>II - 2.2. Limites</td><td>18</td></tr><tr><td>II - 2.3. Principe</td><td>19</td></tr><tr><td>III - Description par attributs de quelques algorithmes d'optimisation</td><td>21</td></tr><tr><td>III - 1. Optimisation des expressions logiques</td><td>22</td></tr><tr><td>III - 2. Détermination des blocs de base</td><td>27</td></tr><tr><td>III - 3. Elimination des sous-expressions communes redondantes</td><td>31</td></tr><tr><td>III - 4. Déplacement des instructions invariantes</td><td>37</td></tr><tr><td>Conclusion</td><td>45</td></tr></table>

## Bibliographie
<figure><img src="image_6.png" /></figure>
L'OPTIMISATION DE CODE POURRA-T-ELLE S'AFFIRMER

GRACE AUX ATTRIBUTS SEMANTIQUES ?

Le mot "optimisation" convient mal en fait, car le code optimisé n'est pas toujours le meilleur possible. Nous l'utiliserons malgré tout pour faciliter le rapprochement de notre travail et des recherches effectuées dans le même domaine.

Les méthodes d'optimisation interviennent pendant la phase de compilation des programmes, pour améliorer leur code intermédiaire selon un compromis entre l'encombrement en mémoire et le temps d'exécution. Cependant aucune garantie n'est donnée en ce qui concerne les compilateurs optimiseurs. En effet, les risques de résultats faux sont actuellement imprévisibles. Ceci est dû au manque de rigueur de la définition de la sémantique des langages de programmation; aucun outil n'est universellement accepté et utilisé en ce domaine comme la BNF pour la syntaxe.

La notion d'attributs [1] permet de décrire sémantiquement les non-terminaux d'une grammaire par des déclarations introduites au niveau de chaque règle de production syntaxique. Grâce à la méthode de compilation par attributs, la description sémantique des langages va bénéficier de la rigueur de leur définition syntaxique. La puissance de cette méthode est dûe au fait qu'elle permet d'exprimer l'aspect sémantique d'une façon déclarative, c'est-à-dire qu'elle offre une liberté de programmation qui permet de définir l'optimisation avant même de chercher un algorithme pour l'effectuer. Les méthodes classiques de compilation ne comportent pas les mêmes avantages de description sémantique.

Cependant il n'existe aucune méthode pour justifier d'une application correcte de ces algorithmes. Mais des études théoriques [2] ont montré qu'il était possible de faire la preuve de programmes et les recherches actuelles tendent à développer ce domaine. C'est dans le but d'obtenir par cette voie des garanties sur les compilateurs optimiseurs que nous nous efforçons d'introduire les algorithmes d'optimisation dans la description des règles de production.
Ainsi, l'optimisation faisant corps avec la définition des langages, nous pensons franchir un premier pas nécessaire et décisif vers la preuve de l'application des optimisations.

Le chapitre I de cet article commence par une revue des optimisations rencontrées dans la littérature, classées en fonction de leur enchaînement. Nous distinguons de plus celles qui peuvent traiter directement le texte source de celles qui ne s'appliquent qu'au code intermédiaire de compilation (eg. Triplets). Certaines optimisation sont liées au calculateur cible, mais par souci de généralité, nous nous attacherons plus particulièrement à citer celles qui sont indépendantes du calculateur.

Dans le chapitre II nous initions le lecteur à la méthode des attributs, nous en donnons ses possibilités tout en précisant ses limites actuelles; nous proposerons un moyen de les dépasser. Nous traitons un exemple simple qui consiste à numéroter les instructions d'un programme, puis nous dirons quelques mots sur le métacompilateur DELTA [3] [4] qui est basé sur la notion d'attributs sémantiques.

Le chapitre III décrit par attributs quelques algorithmes d'optimisation. Nous donnons la définition d'un bloc de base, notion fondamentale en optimisation et nous définissons des attributs sémantiques capables de déterminer ces blocs dans un programme. Nous terminons par la description par attributs des deux principales optimisations algorithmiques : l'élimination des sous-expressions communes redondantes et le déplacement des instructions invariantes. Nous verrons alors la stratégie à suivre pour traiter par attributs sémantiques tout algorithme de transformation de programme qu'il soit d'optimisation ou non.

En conclusion nous introduisons les preuves de programmes par attributs sémantiques et nous proposons de les appliquer à la recherche de l'équivalence entre les différentes formes d'un programme en particulier entre deux versions, l'une optimisée et l'autre non, de la description sémantique d'un même programme. Ceci devrait contribuer à garantir l'application des algorithmes d'optimisation et, de ce fait, accroître la fiabilité des compilateurs optimiseurs.
Les programmes en langage évolué subissent pour être opérationnels un processus de traduction qui, de par la généralité de son automatisme, engendrera pour un programme source même optimisé, un code plus lourd qu'il ne l'aurait été, écrit directement en langage de bas niveau. La facilité d'écriture qui nous est offerte par ces langages de haut niveau, a donc l'inconvénient de réduire la performance des programmes.

L'optimisation de code intervient pendant la phase de traduction d'un programme et consiste à le transformer en une forme équivalente généralement moins encombrante et plus rapide à l'exécution. Soit un programme P qui réalise une certaine fonction sur un ensemble I de paramètres. Moyennant le respect de quelques contraintes utiles pour l'optimisation, il est possible de produire un programme P' qui effectue sur I la même fonction. On dira que P et P' sont équivalents si $P(i)=P'(i)$ quelque soit i. L'efficacité résultant de ces contraintes répond généralement à un compromis entre la taille du code et son temps d'exécution.

Il est intéressant pour un programme d'atteindre un niveau raisonnable d'optimisation puisqu'il est nécessaire de le traduire pour pouvoir l'exécuter, mais les techniques d'optimisation de code ne sont pas aussi formellement définies que celles de l'analyse syntaxique [20] [21] [22] et c'est ce qui cause une difficulté. De récentes études ont montré qu'il n'est pas possible de réaliser un programme général d'optimisation de code [25]. Ceci confirme comme nous l'avons souligné, que l'optimisation n'est qu'une amélioration plus ou moins poussée et non un processus optimal.

En général, l'équivalence arbitraire de deux programmes P et P' est indéciable mais si P dérive de P' par des applications successives de relations d'équivalence alors on peut montrer cette équivalence [21] [19] [22] optimisation de code les algorithmes traduisent justement des relations d'équivalence mais en pratique seulement cette équivalence n'est pas garantie [17]
[26] et ceci parceque l'optimisation consiste à modifier la syntaxe d'un texte source tout en conservant son sens qui, lui, n'est pas aussi rigoureusement défini. Des travaux ont été publiés concernant des optimisations plus ou moins poussées suivant le langage, nous citerons FORTRAN [27] [17] [15] , ALGOL [28] [29] et PL/1 [26] [30].

## I - 1 - Optimisations rencontrées dans la littérature

Quand elles sont indépendantes du calculateur, les optimisations sont alors généralement étroitement liées au langage. Nous n'en citerons que quelques types. Nous proposons de traiter les parties de programme les plus fréquemment exécutées, mais il est toujours possible bien sûr de pratiquer une optimisation plus poussée. Les méthodes que nous signalons pour améliorer la performance du code sont valables sur la majorité des calculateurs et s'appliquent aussi bien aux langages de haut niveau qu'à leur traduction intermédiaire nécessaire en compilation.

Pour un même type d'optimisation, l'algorithme diffère selon qu'il traite une zone bouclée ou non du programme. En effet, pour le traitement local de l'optimisation, on considère une instruction par rapport à son environnement immédiat, c'est-à-dire en fonction des instructions qui l'entourent syntaxiquement dans le programme. Tandis que l'optimisation globale s'exprime en fonction du graphe du programme et tient compte pour chaque instruction, de son enchaînement dynamique défini par l'ordre d'exécution de toutes les instructions.

Tous les algorithmes que nous citerons analysent et rendent du texte source [41], et ceci pour deux raisons essentielles :

- Notre premier souci est de mettre en évidence l'optimisation réalisée entre un programme source et son code optimisé. Il est clair que la comparaison est immédiate si le texte une fois optimisé s'exprime dans le même langage que le source. Il est alors facile de repérer les instructions qui ont changé et celles qui ont été déplacées.
- Chacun sait combien la clarté d'un programme se complique pendant la phase de mise au point. Dans le but de conserver intactes les parties déjà testées, tout programmeur préfère rajouter des instructions plutôt que de modifier celles qui sont au point. Ceci conduit rapidement à des programmes inextricables. L'optimisation peut dans ce cas intervenir pour remettre de l'ordre et éliminer les instructions qui ne servent plus. Ainsi il est possible de continuer la mise au point sur un programme plus clair, ce qui doit faciliter la tâche du programmeur dont le travail sera alors plus efficace.

L'optimisation résout donc non seulement des problèmes d'encombrement et de coût, elle apporte aussi une aide à la programmation.

Nous citerons ici les optimisations les plus classiques en fonction de leur enchaînement. Le traitement local est à effectuer d'abord :

1 - La propagation des constantes et variables.

2 - L'élimination des sous-expressions communes redondantes.

3 - La suppression des affectations inutiles.

En effet il est logique dans un premier temps d'évaluer et de substituer tout ce qui est connu, avant de déterminer quels sont les calculs à éviter.

Enfin on recherchera les affectations qui ne serons jamais utilisées, celles-ci sont généralement la conséquence des deux optimisations précédentes.

Le traitement global commence par le déplacement des invariants de façon à déjà minimiser le nombre d'instructions contenues dans chaque boucle. Puis on applique la réduction de puissance des opérateurs, là où elle permet de réduire encore le temps d'exécution des boucles.

On retrouve ensuite tous les types d'optimisation locale mais traités globalement cette fois.
- " La propagation des constantes". Elle consiste à détecter les expressions à valeur constante et à leur substituer cette valeur [24] [5] . Dans la plupart des cas un programmeur s'efforce, pour faciliter la compréhension du code et lui conférer une certaine souplesse, de référencer symboliquement les constantes de ses programmes. Il définit les constantes dans la zone d'initialisation du programme et utilise partout ailleurs leur nom symbolique. Ce procédé a l'avantage de n'avoir qu'une seule instruction à modifier si l'on veut changer la valeur d'une constante. Il est possible aussi d'appliquer cette méthode de propagation aux variables qui gardent localement une valeur constante.

- " L'élimination des sous-expressions redondantes". Cette optimisation a inspiré de nombreuses recherches [42] [24] [5] et son traitement par attributs sémantiques a fait l'objet d'une publication de l'auteur [43] . Elle revient à déterminer les expressions qui correspondent à des calculs déjà évalués. Il s'agit alors de sauvegarder le résultat trouvé et de s'en servir pour remplacer la nouvelle référence de l'expression qui est redondante. Le procédé est plus délicat quand des tableaux figurent en opérandes [28] . Généralement le bénéfice obtenu se traduit par un gain de temps et d'espace mémoire.

Ces deux types d'optimisation sont liés au langage car ils nécessitent la connaissance des opérateurs du langage.

- "La suppression des affectations inutiles". Cette optimisation a pour mission de supprimer les instructions dont le résultat ne sert jamais, ainsi que certains calculs qui après quelques modifications de misà au point, ne servent plus à rien. La propagation des constantes ou variables peut elle même provoquer aussi l'inutilité de certaines affectations, il est important que l'optimisation sache supprimer les lourdeurs qu'elle introduit [24] [5] [9].
- "Le déplacement des instructions invariantes". Il s'agit ici de sortir d'une boucle les instructions qui sont exécutables indépendamment de cette boucle. C'est souvent dans les boucles les plus internes que les programmes passent la majorité de leur temps. Il est important de minimiser le nombre d'instructions de ces boucles. Le déplacement d'une instruction n'est possible que si aucun de ses opérandes ne varie pendant l'activation de la boucle [24], et il se fait de proche en proche par passes successives depuis la boucle la plus interne vers le niveau d'imbrication le plus externe. Nous avons donné [41] [44] par la méthode des attributs, le moyen de déterminer et de déplacer une instruction invariante, pour la placer à sa position optimale en une seule passe effective de compilation. Nous attirons l'attention sur le fait que cette optimisation dépend de la sémantique du langage source. En effet considérons l'exemple suivant en FORTRAN puis en PL/1.

## Avant optimisation

```
FORTRAN
DO 1 I = 1, N
K = J / 3
T(I) = I * K;
1 CONTINUE

PL/I
DO 1 = 1 TO N;
K = J / 3;
T(I) = I * K;
END;
```

## Après optimisation

```
K = J / 3
DO 1 I = 1, N
T(I) = I * K;
1 CONTINUE

K = J / 3;
DO 1 = 1 TO N;
T(I) = I * K;
END;
```
Dans le cas de N < 1 le programme optimisé est juste en FORTRAN et faux en PL/1. Car dans la version FORTRAN, la boucle est toujours exécutée une fois tandis qu'elle ne l'est pas du tout en PL/1. Après optimisation, le calcul de K se faisant hors de la boucle, la valeur de K change dans les deux versions. Le programme PL/1 est donc sémantiquement faux [19].

Ceci montre bien la nécessité de formuler rigoureusement l'aspect sémantique des langages.

«La réduction de puissance des opérateurs». Elle consiste à remplacer par exemple les multiplications par des additions dont le temps d'exécution est en principe plus court.

Exemple :

```
DO I = 1 TO N;
T = I * K;
END;
```

Après remplacement de la multiplication :

```
T1 = I * K;
DO I = 1 TO N;
T = T1;
T1 = T1 + K;
END;
```

Cette optimisation n'est valable que lorsque les opérandes sont des entiers car l'addition qui remplace la multiplication ne donne pas tout à fait le même résultat dans le cas d'opérandes réels, à cause des erreurs d'arrondi qui s'accumulent à chaque exécution de la boucle. Ce traitement peut entraîner une autre amélioration possible, celle qui aboutit au remplacement du test de la boucle. En effet si la variable de boucle n'apparaît plus dans le corps de la boucle, elle ne sert plus que de compteur. Il est alors préférable de la remplacer par une autre variable, ce qui donne pour l'exemple précédent après remplacement du test propagation des constantes
et élimination des affectations inutiles, on obtient :

DO T1 = K TO N * K BY K ;
T = T1 ;
END ;

Bien que sa justification dépende en partie du calculateur, la réduction
de puissance des opérateurs peut être intéressante même quand la
multiplication est aussi rapide que l'addition, car elle détecte en même
temps les sous-expressions communes redondantes d'une boucle, qui font
des calculs sur les indices de tableaux. Cependant elle n'est pas toujours
efficace et suivant le nombre de multiplications remplacées, le programme
peut s'alourdir notablement [GR71].

I - 1 - 3 - Optimisations liées au calculateur

Elles dépendent d'abord du nombre et de la nature des registres
disponibles sur le calculateur auquel le programme est destiné. D'une
part il s'agit de réordonner les calculs pour minimiser le nombre de
registres nécessaires [31] [32] [33] [34] . D'autrepart il convient
d'effectuer un choix des registres utiles pour limiter au maximum les accès
aux mémoires de chargement et de sauvegarde [35] [36] [37] [4] . Il s'agit
alors d'allouer le mieux possible les ressources disponibles. Les techniques
utilisées relèvent essentiellement de la théorie des graphes. Quand un cal-
culateur dispose de plusieurs unités arithmétiques indépendantes (eg. CDC 6600)
il est possible de développer une optimisation spécifique car le meilleur code
en calcul série n'est pas toujours le meilleur en calcul parallèle [38] [13]
[39] [14] . Enfin il est possible de tenir compte du jeu d'instructions of-
fert par le calculateur. En effet il comprend souvent des instructions spécia-
les qui remplacent avantageusement une suite d'opérations plus élémentaires. Il
est alors intéressant de faire apparaître de telles séquences [40] [8].
I - 2 - Optimisations supplémentaires

Ces optimisations sont nombreuses et désordonnées et leur
application coûte plus ou moins cher. Tel programme appelé à être utilisé
souvent sera plus économique s'il s'exécute plus rapidement. Tel autre
programme, dont la taille pose des problèmes, pourra après optimisation
être traité quand même. Généralement on se contentera d'une optimisation limitée en établissant un juste milieu entre le prix de revient et le service
rendu. Nous citerons :

- Le remplacement des séquences d'appel de sous-programmes par le développement du corps des procédures. Ceci réduit le temps d'exécution mais allonge le programme [5],

- L'élimination des instructions jamais exécutées. Le code se raccourcit sans entraîner de gain de temps à l'exécution. Nous avons montré dans une précédente publication, comment la compilation par attributs permet d'éliminer ces instructions [6].

Nombre de ces optimisations transforment les boucles de
programme [7] car souvent, si l'amélioration obtenue est maigre, elle
peut devenir conséquente une fois multipliée par la fréquence d'exécution de
la boucle. Beaucoup d'améliorations manipulent des expressions,
cependant elles sont plus ou moins facile à réaliser suivant la forme du
langage à traiter. Par exemple, il est plus commode d'exprimer
la factorisation des expressions [8] sur un texte source que sur ses
triplets [9] . Le choix du support de l'information peut donc favoriser
le degré d'amélioration du code qui n'est plus alors limité que par
la complexité de réalisation. Nous citerons quelques études concernant :

- L'utilisation d'une forme pelonaise postfixée [10] ou la mise en arbre des expressions [11].

- Le réarrangement des opérations pour atteindre une factori-
sation optimale et minimiser ainsi le nombre d'opérations [12] [13].
- Le calcul partiel des expressions, qui peut s'avérer suffisant pour déterminer le résultat [14].

- Le remplacement d'une opération par une autre : A/B devient A*(1/B), dans le but de calculer hors d'une boucle le facteur B et son inverse pour améliorer ainsi le temps d'exécution de la boucle [15].

- Des résultats intéressants ont été obtenus sur l'amélioration des calculs d'expression matricielles [16]. Et particulièrement en ce qui concerne la transformation de plusieurs boucles imbriquées en une seule boucle simple [17] : en tenant compte de l'implantation linéaire des tableaux, il est possible de considérer des vecteurs à plusieurs dimensions comme des scalaires (cf. EQUIVALENCE de FORTRAN ou DEFINED de PL/1), et de remplacer alors tous les indices par un seul [18]. Cette liste d'améliorations n'est pas exhaustive, nous nous attarderons plutôt sur les optimisations qui sont structurées logiquement sous forme d'algorithmes élaborés et dont la justification n'est pas toujours une simple évidence.

Quel que soit le type d'optimisation traitée, il s'agit dans tous les cas d'une transformation de programme qui, au moins dans le cas des langages évolués, aura intérêt à être exprimée sur l'arbre syntaxique; car pour optimiser une phrase, on a en général besoin de son contexte, notemment pour l'optimisation globale. Ceci confirme l'utilisation de la méthode des attributs qui permet des descriptions sémantiques claires et précises.

## II - LA METHODE DES ATTRIBUTS

La méthode des attributs apporte au processus de compilation plus de rigueur et une plus grande clarté dans la description sémantique. Pour la présente, nous allons traiter à fond un exemple simple dont le seul mérite est d'être pédagogique.
## II - 1 - Exemple

Soit la grammaire donnée par les règles de production suivantes :

<P> ::= <L> ; (P : Programme, L : Liste d'instructions)

<L> ::= <I> (I : Instruction)

<L> ::= <L> ; <[>

Considérons l'arbre syntaxique du programme formé de trois instructions : Ia ; Ib ; Ic ; et numérotons les différentes occurrences d'un même non-terminal sur l'arbre syntaxique :

<figure><img src="image_7.png" /></figure>
Supposons que la sémantique d'un tel langage ait pour but de compter et numéroter les instructions contenues dans tout programme écrit dans ce langage. Le rôle des attributs est donc de calculer et porter les numéros des instructions. Définissons deux attributs :

PI : numéro de la Première Instruction produite par le non-terminal décrit.

DI : numéro de la Dernière Instruction produite par le non-terminal décrit.

Dans chaque règle de production, nous allons définir les PI et DI des non-terminaux. Etablissons des relations entre ces attributs pour décrire leurs liens sémantiques de façon à calculer DI(P), c'est-à-dire DI rattaché au noeud P racine de l'arbre, il donne effectivement le nombre d'instructions qui composent le programme. Si on attribue le numéro 1 à la première instruction, soit PI(P)=1 alors DI(P) qui porte le numéro de la dernière instruction donnera le nombre total d'instructions du programme. La description sémantique est la suivante :

<P> ::= <L> ;
PI(P)= 1
PI(L)=PI(P) (car la lère instruction de L a le même numéro que la lère instruction de P)

<L> ::= <I>
PI(I)=PI(L)
DI(L)=DI(I)
DI(I)=PI(I) (car I ne représente qu'une seule instruction, les deux numéros sont alors confondus)

<L> ::= <L'> ; <I>
PI(L')=PI(L)
PI(I)=DI(L')+1 (car l'instruction représentée par I suit syntaxiquement la dernière instruction de L' dans la liste L des instructions)
DI(I)=PI(I)
DI(L)=DI(I)
Chaque équation définit l'attribut de gauche en fonction de ceux de droite.

Un attribut peut :

1er cas : être connu. Ex : $PI(P)=1$.

2ème cas : qualifier le non terminal de gauche et dépendre d'attributs des non-terminaux de droite. Ex : $DI(L) = DI(I)$.
On dit qu'il est synthétisé.

3ème cas : qualifier un non-terminal de droite et dépendre d'attributs du non-terminal de gauche. Ex : $PI(L) = PI(P)$.
On dit qu'il est de type hérité.

4ème cas : qualifier un non-terminal de droite et dépendre d'attributs des autres non-terminaux de droite. Ex : $PI(I) = DI(L') + 1$.
On établit alors une liaison entre les deux types d'attributs.

Pour reporter sur l'arbre syntaxique toute cette information d'attributs sémantiques, nous proposons d'accrocher à chaque noeud la définition de tous les attributs qui lui correspondent quelle que soit la règle qui les contient.

Par exemple au noeud L nous accrochons l'équation sémantique $PI(L) = PI(P)$ que l'on trouve dans la règle `<P> ::= <L>;` et nous lui ajoutons $DI(L) = DI(I)$ donnée par `<L> ::= <L'>; <I>`.

On voit clairement ci-dessous, que la valeur de l'attribut $PI$ part de la racine et se propage vers les feuilles, car le $PI$ d'un noeud ne dépend que du $PI$ de son prédécesseur immédiat (père) On dit que l'attribut $PI$ est hérité, il répond au 3ème cas.

Inversement l'attribut $DI$ remente dans l'arbre sémantique des feuilles vers la racine, il ne dépend que du $DI$ de ses successeurs immédiats (fils). On dit que $DI$ est un attribut synthétisé, il répond au 2ème cas.

La circulation de l'information dans l'arbre s'établit donc conformément à la nature des attributs et c'est le cas numéro 4 qui transmet cette information d'un type d'attribut à l'autre.
<figure><img src="image_8.png" /></figure>

Nous avons vu que la sémantique d'un langage pouvait se décrire par des relations entre attributs. Nous expliquerons brièvement dans ce qui suit comment on réalise le programme d'évaluation à partir de ces relations.

Reprenons la règle qui ajoute une instruction à la liste et expliquons la sémantique qui s'y rattachera.

<L> ::= <L1> ; <I1>

modèle 1 PI(L1) = PI(L)

modèle 2 PI(I1) = DI(L1) + 1

modèle 3 DI(L1) = DI(I1)

modèle 4 DI(I1) = PI(I1)
Le non-terminal L comporte en tout deux attributs : PI et DI.
Chacun d'eux est défini par une équation sémantique. Nous dirons qu'un
attribut est défini par un modèle sémantique. Les modèles associés aux
règles conduisent à un système d'équations qui décrit l'arbre sémantiquement.
Pour résoudre ce système on ordonne les équations de manière à ce que
chaque attribut ne soit calculé qu'après ceux dont il dépend.

## II - 2 - Application à la métacompilation

Nous nous placerons ici dans le contexte du métacompilateur DELTA (Description de Langages et Traducteurs par Attributs) [3] [4] réalisé à l'IRIA. Le principe de la métacompilation est de produire le compilateur d'un langage donné par sa grammaire, suivant le schéma :

<figure><img src="image_9.png" /></figure>
Soit LG le langage engendré par G. On dispose d'un programme standard appelé "constructeur syntaxique et sémantique" a qui l'on fournit G (en BNF par exemple) contenant des actions exprimées en langage sémantique SL. Le constructeur a pour tâche de créer en fonction de G, les tables syntaxiques et sémantiques de LG.

Un "analyseur" standard analyse le texte source en LG et consulte ces tables pour établir un programme en SL. L'exécution de ce programme génère le code objet correspondant au texte source.

Le compilateur produit est donc formé de l'analyseur (partie fixe), des tables (qui varient suivant LG) et du compilateur du langage sémantique SL utilisé.

## II - 2 - 1 Possibilités

La métacompilation par attributs consiste à décrire les actions sémantiques pour chaque non-terminal d'une règle de production de G, au moyen d'attributs. Pour bien comprendre la notion d'attributs, nous pouvons considérer l'arbre syntaxique d'un texte source. A chacun de ses noeuds est rattaché un lot d'attributs qui portent la signification sémantique du non-terminal représenté par ce noeud. Cette signification n'est autre qu'une séquence d'instructions en langage sémantique. La valeur d'un attribut pour un noeud donné peut dépendre des attributs des noeuds ascendant ou descendants. On dit que l'attribut est respectivement hérité (↓) ou synthétisé (↑). Ceci établit des liens sémantiques entre les non-terminaux et le seul fait de suivre ces liens revient à propager l'information sémantique dans l'arbre syntaxique.

Le code objet est produit (en métacompilation) par l'exécution du programme sémantique construit à partir des diverses séquences d'instructions que portent les attributs. Pour obtenir un programme cohérent, il faut ranger ces séquences dans un ordre évaluable. C'est pourquoi un tri des attributs est nécessaire car ils dépendent les uns des autres et il faut déterminer quels sont ceux qu'il est possible d'évaluer avant les autres. Ce tri permet d'établir une liste d'implication des attributs
qui donnera l'ordre d'activation des instructions sémantiques dans le programme d'évaluation. On conçoit qu'il puisse exister des listes disjointes d'attributs enchainés pour un même texte source. Seules les chaînes qui aboutissent à l'évaluation du code objet du programme source, i.e. celles qui fournissent le calcul des attributs de la racine de l'arbre syntaxique, interviendront dans la constitution du programme sémantique. Cette élimination de calculs inutiles, dûe à la méthode propre de compilation par attributs, réalise une première optimisation systématique.

## II - 2 - 2 - Limites

Les limites de la métacompilation par attributs sont encore mal connues. Le stade actuel de la recherche permet de décrire très aisément la sémantique statique des langages de programmation. Mais quand il s'agit de décrire avec ces attributs "statiques" l'aspect sémantique lié au graphe du programme, comme c'est le cas en optimisation globale, alors on alourdit considérablement la description sémantique : le nombre d'attributs se multiplie et leurs relations se compliquent. L'avenir dans ce domaine est probablement de créer la notion d'attributs "dynamiques" [4]. Pour l'instant nous nous engageons à ne jouer le jeu des attributs que dans la mesure où leur intervention facilite l'introduction des algorithmes d'optimisation dans la définition sémantique des langages. Dès que leur utilisation doit alourdir cette définition alors nous retournerons aux procédés classiques d'optimisation dans la compilation.

Pour la mise au point des descriptions sémantiques données dans cet article, c'est la première version du métacompilateur DELTA [3] qui nous a servi d'outil. La version actuelle [4] est beaucoup plus rapide mais pour satisfaire à cette rapidité, il a fallu écourter la durée de vie des attributs pendant le travail de compilation. Ceci nous a conduit à créer des tables pour conserver plus longtemps encore l'information
d'optimisation qui nous était nécessaire. La raison pour laquelle nous
avons introduit l'optimisation dans le cadre de la métacompilation est
motivée par le fait que : la production automatique de compilateurs, de
par son souci de généralité engendre fatalement des compilateurs beaucoup
moins performants que ceux écrits directement par une équipe de programmeurs.
Ce projet de métacompilateur n'est donc valable que dans la mesure où s'y
greffe l'optimisation pour produire des compilateurs optimiseurs.

## II - 2 - 3 - Principe

Le code objet d'un programme source est donné par la détermination
des modèles sémantiques qui décrivent l'axiome P, racine de l'arbre.

Reprenons l'exemple donné page 12 pour numéroter les instructions d'un
programme. Sur l'arbre de la page 15 on peut suivre grâce aux flèches,
l'ordre d'évaluation des modèles développés qui permet d'aboutir au
résultat : calcul des attributs de la racine. Cet ordre provient des
implications que nécessitent les attributs :

PI(P) est connu
DI(P) > DI(L)          i.e. DI(P) implique DI(L)
PI(L) > PI(P)
DI(L) > DI(I1)
PI(L1) > PI(L)
DI(L1) > DI(I2)
PI(I1) > DI(L1)
DI(I1) > PI(I1)
PI(L2) > PI(L1)
DI(L2) > DI(I1)
PI(I2) > DI(L2)
DI(I2) > PI(I2)
PI(I) > PI(L2)
DI(I) > PI(I)
Un programme de tri range ces attributs dans un ordre de calcul possible
en établissant une liste d'implication :

$$
DI(P) \rightarrow DI(L) \rightarrow DI(I1) \rightarrow PI(I1) \rightarrow DI(L1) \rightarrow DI(I2) \rightarrow PI(I2) \rightarrow
$$

$$
DI(L2) \rightarrow DI(I) \rightarrow PI(I) \rightarrow PI(L2) \rightarrow PI(I1) \rightarrow PI(L) \rightarrow PI(P) = 1
$$

En fonction de cette liste on réalise un programme d'évaluation
composé des différents modèles sémantiques développés, ce qui donne :

<table>
  <thead>
    <tr>
      <th>Programme</th>
      <th></th>
      <th>Exécution pas à pas</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>PI(P) = 1</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>PI(L) = PI(P)</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>PI(L1) = PI(L)</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>PI(L2) = PI(L1)</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>PI(I) = PI(L2)</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(I) = PI(T)</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(L2) = DI(I)</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>PI(I2) = DI(L2)+1</td>
      <td>2</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(I2) = PI(I2)</td>
      <td>2</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(L1) = DI(I2)</td>
      <td>2</td>
      <td></td>
    </tr>
    <tr>
      <td>PI(I1) = DI(L1)+1</td>
      <td>3</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(I1) = PI(I1)</td>
      <td>3</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(L) = DI(I1)</td>
      <td>3</td>
      <td></td>
    </tr>
    <tr>
      <td>DI(P) = DI(L)</td>
      <td>3</td>
      <td>résultat.</td>
    </tr>
  </tbody>
</table>
Les attributs qui ne participent pas à cette évaluation sont automatiquement éliminés au niveau du tri car ils ne figurent pas dans la liste d'implication des attributs de la racine.

Ceci dote la méthode d'une optimisation naturelle en ce qui concerne les calculs sémantiques inutiles. Le chapitre suivant en traite un exemple.

Si la méthode des attributs offre plus de possibilités que les méthodes classiques et si elle simplifie beaucoup la réalisation de compilateurs, il faut noter toutefois que plus le texte source est important plus le nombre d'attributs employés sera grand. Ceci met en jeu un travail énorme de gestion de données qui a été résolu dans le système DELTA [4] en conservant la même variable pour représenter deux attributs égaux. En général, le nombre d'attributs peut être réduit de 95%.

### III - DESCRIPTION PAR ATTRIBUTS DE QUELQUES ALGORITHMES D'OPTIMISATION

Nous avons déjà soulevé la nécessité de décrire rigoureusement non seulement la sémantique des langages, mais aussi celle des optimisations. Les exemples ambigus que nous avons notés concernaient d'une part le traitement des invariants qui peut aboutir à un programme optimisé juste ou faux selon les finesses sémantiques du langage source (cf. page 7 et d'autrepart le degré d'optimisation des expressions qui peut fausser le calcul de leur résultat (cf. III - 1).
Dans ce dernier chapitre nous tenterons de mettre en évidence le
procédé à suivre pour décrire sémantiquement par attributs les algorithmes
d'optimisation. Nous commencerons par traiter l'optimisation sur une expression
logique puis nous montrerons comment déterminer les blocs de base d'un
programme, notion fondamentale en optimisation. Ensuite nous nous attacherons
à l'élimination des sous-expressions communes redondantes et nous montrerons
qu'un seul attribut optimiseur suffit pour traiter ce problème. Enfin nous verrons
déplacer hors des boucles les instructions invariantes, en simulant deux
passes de compilation, quel que soit le niveau d'imbrication des boucles.
La simplicité de la solution obtenue dans un cas comme dans l'autre est un
encouragement au traitement par attributs des autres optimisations de code.

### III - I - Optimisation des expressions logiques

Soit l'expression $X = (O \cup A) \cup I$

Le calcul de l'expression entre parenthèses ne doit pas intervenir dans
le code objet puisque X est toujours vrai.

Considérons les règles de production utiles pour l'analyse
syntaxique de cette expression :

*   `<I>` ::= `<V>` = `<E>`
*   `<V>` ::= identificateur
*   `<E>` ::= `<E>` u `<T>` (T : 'lerme')
*   `<E>` ::= <T>
*   <T> ::= ( <E> )
*   <T> ::= <V>
*   <T> ::= constante

L'arbre syntaxique de cette instruction est donné page 23. Notre but est de transformer le texte donné en un texte écrit dans le même langage où l'expression est simplifiée. Dans l'exemple présent il s'agit d'obtenir : X=1.
<figure><img src="image_10.png" /></figure>

Identificateur

Constante

Constante

Identificateur

X

=

(

0

U

A

)

U

I
Definissons deux attributs synthétisés :

VL qui est la Valeur Logique d'un non-terminal : 0 ou 1, et sera -1 pour
toute valeur non définie.

TS qui représente le texte objet de chaque non-terminal.

Par exemple :

VL(T3) = 0

VL(T) = 1

VL(V1) et VL(V) sont à -1

TS(V) = X

TS(V1) = A

TS(T3) = 0

TS(T) = 1

## Description sémantique :

<I> ::= <V> = <E>

TS(I) est l'instruction TS(V) = TS(E)

<E> ::= <T>

VL(E) = VL(T)

TS(E) = TS(T)

<V> ::= identificateur

TS(V) = identificateur

VL(V) = -1

<T> ::= ( <E> )

TS(T) = '(' || TS(E) || ')' ( || : Concaténation)

VL(T) = VL(E)

<T> ::= <V>

TS(T) = TS(V)

VL(T) = VL(V)

<T> ::= constante

TS(T) = constante

VL(T) = constante
Pour plus de clarté nous schématisons la sémantique de la règle :

`<E> ::= <E> u <T>` dans le tableau suivant :

<table><thead><tr><th>Cas n°</th><th>VL(E')</th><th>VL(T)</th><th>VL(E)</th><th>TS(E)</th></tr></thead><tbody><tr><td>1</td><td>-1</td><td>-1</td><td>-1</td><td>TS(E') || 'u' || TS(T)</td></tr><tr><td>2</td><td>-1</td><td>0</td><td>-1</td><td>TS(E')</td></tr><tr><td>3</td><td>-1</td><td>1</td><td>1</td><td>TS(T)</td></tr><tr><td>4</td><td>0</td><td>-1</td><td>-1</td><td>TS(T)</td></tr><tr><td>5</td><td>1</td><td>-1</td><td>1</td><td>TS(E')</td></tr><tr><td>6</td><td>0</td><td>0</td><td>0</td><td>TS(E') = TS(T)</td></tr><tr><td>7</td><td>1</td><td>0</td><td>1</td><td>TS(E')</td></tr><tr><td>8</td><td>0</td><td>1</td><td>1</td><td>TS(T)</td></tr><tr><td>9</td><td>1</td><td>1</td><td>1</td><td>TS(E') = TS(T)</td></tr></tbody></table>

Notre exemple fait apparaître deux occurrences de cette règle :

- La première est `<E> = 0 u A`, c'est-à-dire que `<E'> = 0` tandisque `<T> = A`. Elle fait appel au cas 4 où l'on a `VL(E) = -1` et `TS(E) = TS(T) = A`.

- La seconde est `<E> = (0 u A) u 1`, c'est-à-dire que `<E'> = (0 u A) tandisque `<T> = 1`. Elle fait appel au cas 3 pour lequel `VL(E) = 1` et `TS(E) = TS(T) = 1`.

L'arbre sémantique de l'instruction I est donné page 26, on peut suivre en traits fins l'évaluation des résultats. Nous avons barré tout ce qui n'intervient pas dans le calcul des attributs de I racine de l'arbre.

`TS(I)` est l'instruction `TS(V) = TS(E)`, le texte objet de l'instruction I est donc `X = 1`, on pourra le vérifier sur l'arbre. Bien entendu, cette optimisation ne peut pas être effectuée si A est une fonction ayant des effets annexés.

De la même façon, dans le cas du réarrangement de l'ordre des calculs, pour minimiser le nombre des opérations, il suffit que les opérations soient des fonctions qui agissent les unes sur les autres pour bouleverser l'ordre de leur exécution et rendre un résultat erroné [19].

Ceci montre bien la nécessité de définir sémantiquement de façon très rigoureuse les optimisations effectuées sur les langages de programmation.
<figure><img src="image_11.png" /></figure>

X = ( 0 U A ) U 1
### III - 2 - Détermination des blocs de base

Une notion fondamentale est celle de "bloc de base". Le mot séquence serait mieux approprié car il y a un risque de confusion avec les blocs au sens d'ALGOL ou de PL/1.

**Définition :**

Un bloc de base défini sur un programme en langage intermédiaire, est une suite maximale d'instructions qui s'exécutent séquentiellement et dans laquelle on ne peut entrer que par la première et on ne peut en sortir que par la dernière.

L'aspect dynamique d'un programme se représente par un graphe dont les noeuds sont les blocs de base. Les arcs traduisent alors les différentes possibilités de branchement, à l'exécution, entre les blocs.

- Le bloc i est **prédécesseur** (resp. successeur) du bloc j s'il existe un chemin allant de i à j (resp. j à i).

- Le bloc i est **prédécesseur** (resp. successeur) **immédiat** du bloc j s'il existe l'arc $\overrightarrow{ij}$ (resp. $\overrightarrow{ji}$).

On entre dans le graphe par un seul arc et on en sort par un ou plusieurs arcs, chacun d'eux doit traverser un bloc, s'il n'existe pas on l'ajoute.

- Le bloc d'entrée d'un programme est celui qui n'a aucun bloc prédécesseur.

- Les blocs de sortie d'un programme sont ceux qui n'ont pas de successeur.

Dans la mesure où l'on veut traiter l'optimisation algorithmique par attributs, la première question que l'on se pose est : est-il possible d'exprimer sémantiquement le concept de bloc de base et comment déterminer ces blocs par attributs ? En accord avec la définition, nous proposons de limiter chaque bloc par son entrée et sa sortie. Le problème revient
donc d'abord à repérer pour chaque instruction, d'une part si elle peut
débuter un bloc, on cherchera pour cela les instructions étiquetées,
d'autrepart si elle peut terminer un bloc, on s'intéressera alors à
toutes les ruptures de séquence.

Nous allons définir 4 attributs :

ET↑ =1 ou 0 selon que l'instruction est ETiquetée ou non.

B↑ =1 ou 0 selon que la dernière instruction du non terminal est une rupture de séquence ou non.

PB↓- DB↑ : Couple d'attributs qui numérote le Premier et le Dernier Bloc de base d'un même non-terminal.

Les relations entre ces attributs seront établies en fonction du principe
suivant :

- La lère instruction du programme est dans le bloc n° 1.

- Soit I l'instruction courante, elle se trouve dans le bloc PB(I).
  Soit J l'instruction suivante, si ET(J)=1 ou B(I)=1 alors J débute un
  nouveau bloc, donc PB(J)=PB(I)+1 sinon PB(J) =PB(I).

A ce stade on remarque qu'il est possible d'introduire une
certaine amélioration dans ces définitions sémantiques. En effet,
considérons l'attribut ET↑, nous pouvons nuancer sa définition ainsi :

ET↑ = 1 si l'instruction est non seulement ETiquetée mais encore référencée.

En effet, toute étiquette non référencée est une fausse entrée de bloc, il
est donc inutile de changer de numéro de bloc sur cette instruction. De plus
nous pouvons nous servir de cet attribut pour compter les étiquettes du
programme. Dans ces conditions, on aura :

ET : nombre d'étiquettes référencées contenues dans le non-terminal.

Considérons le langage donné par les règles de production suivantes :

<P> ::= <L> ;

<L> ::= <I>

<L> ::= <L> ; <I>

<I> ::= Etiquette : <INE>

<I> ::= <INE>

<INE> ::= <V> = <E>

<INE> ::= GOTO Etiquette

<INE> ::= <ID> ; <L> ; END

(INE : Instruction Non Exécutée)

(ID : Instruction DO)
Nous utiliserons ce langage dans les exemples qui suivent.

La sémantique des attributs ET et B est :

<P> ::= <L> ;

• ET(P)=ET(L)

<L> ::= <I>

ET(L)=ET(I)

B(L)=B(I)

<L> ::= <L'> ; <I>

ET(L)=ET(L')+ET(I)

B(L)=B(I)

<I> ::= Etiquette : <INE>

ET(I)=I+ET(INE)

B(I)=B(INE)

<I> ::= <INE>

ET(I)=ET(INE)

B(I)=B(INE)

<INE> ::= <V> = <E>

ET(INE)=0

B(INE)=0

<INE> ::= GOTO Etiquette

ET(INE)=0

B(INE)=1

<INE> ::= <ID> ; <L> ; END

ET(INE)=ET(L)

B(INE)=1

Ainsi définie, la sémantique de ET† donne toutes les informations nécessaires pour procéder à la vérification de la bonne construction du programme : il est possible de détecter les étiquettes multidéfinies et les références à des étiquettes non définies. De même, on peut préciser la
définition de B↑ en établissant une différence selon que la rupture de séquence est un branchement inconditionnel ou non. On sera alors en mesure de supprimer des instructions inaccessibles d'un programme : c'est le cas de tout branchement inconditionnel non suivi d'une étiquette [6].

Nous remarquons que, en fait, peu d'attributs sont créés spécialement pour l'optimisation (ET est nécessaire même si la compilation n'est pas optimisée). On se contente souvent d'adapter leur d' définition aux besoins de l'optimisation et de modifier les relations sémantiques qui leslient.

En ce qui concerne la détermination des blocs de base d'un programme, l'essentiel de cette sémantique est décrite dans les 3 règles de production suivantes :

<P> ::= <L> ;
PB(P)=1
PB(L)=PB(P)
DB(P)=DB(L)

<L> ::= <L'> ; <I>
PB(L'):= PB(L)
DB(L)=DB(I)
IF (ET(I)=1) ^ (B(L')=1) THEN PB(I)=DB(L')+1 ELSE PB(I)= DB(L')

<INE> ::= <ID> ; <L> ; END
PB(L)=PB(INE)+1 (car ID est considéré comme le bloc d'initialisation de la boucle)
DB(INE)=DB(L)+1 (car END est considéré comme le bloc d'incrémentation de la boucle)

Pour toute autre règle de type <INE> ::= ... on aura DB(INE)=PB(INE).

Au cours du calcul PB+DB↑, chaque instruction déjà numérotée (cf. PI+DI↑) est consultée. Et le fait d'attribuer un numéro au bloc qui la contient permet d'établir une correspondance entre ce bloc, la première et la dernière instruction qui le composent. Ceci revient à découper le programme en blocs de base. De plus les changements de blocs se jouent sur
deux instructions consécutives (de numéros PI et PI-1) et se décident en fonction de l'une ou de l'autre, selon que l'instruction PI est étiquetée ou que l'instruction PI-1 effectue un branchement. Ainsi, au moment de prendre la décision de changer de bloc, on est en mesure de déterminer l'(les) instruction(s) qui suit dynamiquement le bloc qui vient de se terminer, ce qui nous donnera indirectement le numéro du(des) bloc(s). successeur(s). De cette façon, nous disposons de toute information utile au traitement de l'optimisation globale.

### III-3 - Elimination des sous-expressions communes redondantes

Cette optimisation consiste à déterminer les calculs communs et à sauvegarder les résultats du premier d'entre eux qui sera exécuté, pour le reporter dans les autres. Elle supprime donc les calculs inutiles.

#### Localement [5]

<table><thead><tr><th>avant optimisation</th><th>après optimisation</th></tr></thead><tbody><tr><td>D = D + C * B;</td><td>T = C * B;</td></tr><tr><td>A = D + C * B;</td><td>D = D + T;</td></tr><tr><td>C = D + C * B;</td><td>A = D + T;</td></tr><tr><td></td><td>C = A;</td></tr></tbody></table>

C * B est une sous-expression commune aux calculs de D, A et C. Elle est redondante dans les deux dernières instructions.

D + C * B n'est redondante que dans le calcul de C car la valeur de D a changé dans la première instruction. Ce qui ne donne pas le même résultat pour les évaluations de D et A.

On voit que lorsque deux expressions sont identiques, la deuxième n'est redondante que si aucun de ses opérandes n'est affecté depuis l'exécution de la première jusqu'au calcul de la seconde, quel que soit le chemin suivi dans le programme.
avant optimisation

DO I = Io TO N ;

X = A + B ;

A = ......

Y = A + B ;

END ;

après optimisation

Y = A + B ;

DO I = Io TO N ;

X = Y ;

A = ...

Y = A + B ;

END ;

La sous expression A+B de X prise au pas k+1 est redondante par rapport
à celle de Y prise au pas k, il suffit de développer deux pas successifs
de la boucle pour s'en apercevoir :

X = A + B ;

A = ......

Y = A + B ;

............

X = A + B ;

A = ......

Y = A + B ;

<figure><img src="image_12.png" /></figure>

itération k

<figure><img src="image_13.png" /></figure>

itération k+1

On voit que dans une boucle, si deux expressions sont communes
sans être redondantes statiquement, il peut exister une redondance dynamique
qui se joue à un pas d'itération près.

L'élimination d'une expression redondante revient à :

- Créer (si nécessaire) une nouvelle variable pour porter le résultat de la première occurrence trouvée de cette expression.

- Supprimer toutes les autres occurrences dont la redondance est justifiée.

- Les remplacer par la variable créée (dans le cas des boucles, une initialisation du processus est nécessaire).

Remarque :

Si la seule expression commune restante est déjà affectée à une
variable, on utilisera de préférence cette variable plutôt que d'en créer
une nouvelle.
Nous nous placerons ici au niveau du langage intermédiaire de
compilation car c'est sur la décomposition élémentaire des expressions que
nous découvrirons le plus de redondances. Considérons les triplets
correspondants à un texte source, parmi eux les seuls candidats à la
redondance sont ceux qui calculent une expression. Ils sont issus de la
règle de production : <E> ::= <E'> opérateur <T>(E : Expression, T : Terme).

Soit PT↓-DT↑ (Premier Triplet-Dernier Triplet) le couple d'attributs qui
comptent les triplets engendrés par chaque non-terminal. La description
sémantique non optimisée de l'addition est la suivante :

<E> ::= <E'> + <T>

PT(E')=PT(E)

PT(T)=DT(E')+1

DT(E)=DT(T)+1

Produire le triplet : + DT(E'), DT(T) (le numéro de ce triplet est DT(E))

Pour tenir compte d'une optimisation possible, il est logique, avant de
produire un tel triplet, de chercher à savoir s'il est redondant d'une part
et par rapport à quel triplet (i) d'autrepart.

Pendant le calcul des attributs PT↓ - DT↑, au fur et à mesure
que les triplets sont produits, ils sont conservés en table et ceci, aussi
longtemps qu'ils peuvent causer une redondance avec un nouveau triplet
à produire.

- Si DT(E) n'est pas redondant alors ce triplet, qui calcule l'expression, doit être produit et DT(E)=DT(T)+1.

- Sinon ce triplet est redondant par rapport à (i), il ne doit donc pas être produit et DT(E)=DT(T). De plus, tout opérande qui fait référence à ce triplet (qui n'existe plus) est à remplacer par (i).

Il s'agit là de distinguer la notion de numéro de triplet de celle
de numéro de référence à un triplet (à utiliser comme opérande). Il n'est
plus question de conserver le même attribut pour jouer à la fois le rôle
de numéro et celui d'opérande, pour un même triplet. C'est pourquoi nous
créons un nouvel attribut R↑ (Redondance) qui portera la notion d'opérande
pour chaque non-terminal (les R(V) seront tous différents des n° de triplets).

R↑ = (i), si le triplet qui calcule l'expression <E> est redondant par
rapport au triplet (i).
= DT, son propre numéro de triplet, sinon.

L'algorithme que nous utilisons pour justifier de la redondance
d'une expression, est celui des nombres de dépendances [6] :

Définitions :

- Le nombre de dépendance initial d'une variable A est dep(A)=0.

- Si le triplet (i) affecte la valeur de A alors dep(A)=i à partir du triplet (i+1).

- Le nombre de dépendance du triplet :
(n°) opérateur opérande1, opérande2
est dep(n°) = 1 + MAX ( dep(opérande1) , dep(opérande2) ).

Théorème :

Soient deux triplets (i) et (j) identiques, avec i<j ; le triplet (j) est redondant par rapport à (i) si dep(i) = dep(j).

Soit TAB↑ - OBJ↑ le couple d'attributs qui véhicule la table
objet dans l'arbre du programme et NBR↑ - DEP↑ celui qui transporte la
table des nombres de dépendance. La description sémantique optimisée est :

<P> ::= <L> ;
PT(L) = 1
DT(P) = DT(L)
TAB(L) = 0
OBJ(P) = OBJ(L)
NBR(L) = 0
<L> ::= <I>

PT(I) = PT(L)

DT(L) = DT(I)

TAB(I) = TAB(L)

OBJ(L) = OBJ(I)

NBR(I) = NBR(L)

DEP(L) = DEP(I)

<L> ::= <L'> ; <I>

PT(L') = PT(L)

PT(I) = DT(L') + 1

DT(L) = DT(I)

TAB(L') = TAB(L)

TAB(I) = OBJ(L')

OBJ(L) = OBJ(I)

NBR(L') = NBR(L)

NBR(I) = DEP(L')

DEP(L) = DEP(I)

<I> ::= <V> = <E>

PT(E) = PT(I)

DT(I) = DT(E) + 1

TAB(E) = TAB(I)

OBJ(I) : OBJ(E) (OBJ(I) est fonction de OBJ(E))

OBJ(E)(DT(I)) = [ = R(E) , R(V)] (ce triplet est mis dans l'élément DT(I) du tableau OBJ(E))

NBR(E) = NBR(I)

DEP(I) : DEP(E)

DEP(E)(R(V)) = DT(I)

<E> ::= <O>

DT(E) = PT(E) - 1

OBJ(E) = TAB(E)

DEP(E) = NBR(E)

R(E) = R(O)
<0> ::= Constante

R(0) = adresse de la Constante

<0> ::= <V>

R(0) = R(V)

<V> ::= Identificateur

R(V) = adresse de l'Identificateur

<E> ::= <E'> + <0>

PT(E') = PT(E)

DT(E) = IF R(E) = DT(E') + 1 THEN R(E)

ELSE

DT(E')

OBJ(E) : OBJ(E')

OBJ(E')(DT(E') + 1) = [+ R(E') , R(0)]

DEP(E) : DEP(E')

DEP(E')(DT(E') + 1) = 1 + MAX (DEP(E')(R(E')) , DEP(E')(R(0)))

R(E) = IF (DEP(E)(DT(E')+1) = DEP(E)(i)) n (OBJ(E)(DT(E')+1) = OBJ(E)(i)))

THEN i

ELSE DT(E') + 1

Pour déterminer les redondances dynamiques dans les boucles, il suffit
dans la sémantique de l'instruction de boucle, de traiter tous les triplets
du corps de boucle déjà en table, en conservant les nombres de dépendance
déjà calculés pour chaque variable [41]. Ensuite, on passe le contrôle
à l'instruction qui suit syntaxiquement et on poursuit alors la
compilation.

Seul le couple d'attributs DEP-NBR est spécifique à l'optimisation,
puisqu'il porte les nombres de dépendance calculés pour les besoins de
l'optimisation. La définition de R a donc été bien choisie puisqu'en
l'adaptant seulement à l'algorithme d'optimisation, elle répond à nos
besoins tant localement que globalement. Une telle description sémantique
conserve la rigueur algorithmique. Bien que spécifique à l'optimisation,
aucun traitement particulier n'est réservé aux attributs DEP-NBR.
On a une idée maintenant de la stratégie à suivre pour exprimer sémantiquement la logique des algorithmes. Pour chaque type d'optimisation, il s'agit de bien concevoir la structure logique de la justification du traitement de l'optimisation afin de la traduire sémantiquement par le support des attributs. Ceci revient à réaliser un programme connaissant l'algorithme d'optimisation et le langage : les attributs. Nous avons réalisé quelques fonctions d'optimisation sur le même principe; le paragraphe suivant présente probablement la plus spectaculaire d'entre elles.

### III - 4 - Déplacement des instructions invariantes

La notion d'invariance dans un domaine est basée sur celle de constance dans ce domaine.

Dans une boucle de programme, toutes les instructions ne peuvent pas le même rôle, certaines d'entre elles sont exécutées à chaque pas d'itération. Or si tous les opérandes d'une telle instruction sont invariants dans la boucle, il est important de sortir cette instruction hors du corps de boucle pour ne l'exécuter qu'une seule fois pour toutes.

#### Définition :

On appelle bloc d'articulation, un bloc de base qui se trouve sur tout chemin entre l'entrée et un bloc de sortie quelconque du programme,

La méthode des invariants consiste à rechercher dans les blocs d'articulation d'une boucle, les instructions inverties dans la boucle et à les transférer en avant de cette boucle.

C'est uniquement dans ces blocs qu'il existe des instructions candidates à l'invariance, il serait faux d'extraire une instruction d'un autre bloc de la boucle.
## Localement

Une variable est invariante dans un bloc si elle ne subit aucune affectation dans ce bloc.

Une variable affectée dans un bloc est invariante si cette affectation est unique et si de plus, il n'existe aucune référence à cette variable avant son affectation dans le bloc.

Une instruction est invariante si tous ses opérandes sont invariants.

## Globalement

Une instruction `<V>=<E>` (V : Variable, E : Expression) d'un bloc d'articulation A est invariante dans la boucle qui le contient si elle réunit les quatre conditions suivantes :

E est invariante dans la boucle.

V = E est invariante localement dans le bloc d'articulation A.

V ne subit aucune autre affectation dans la boucle.

V n'est référencée dans aucun bloc prédécesseur de A dans le corps de boucle.

En effet, on entre dans la boucle avec une certaine valeur de la variable, qui est valable jusqu'à la première affectation rencontrée. S'il existe une référence quelconque à cette variable, avant son affectation, alors, la variable possède deux valeurs différentes dans la même boucle, elle n'est donc pas invariante.
Exemple : [6]

<figure><img src="image_14.png" /></figure>

Les seules instructions candidates à l'invariance sont celles qui sont
dans les blocs d'articulation.

B = S + T est invariante car non seulement l'expression S + T est invariante mais encore B ne subit que cette affectation dans la boucle et, aucune utilisation de B n'a pu avoir lieu avant cette instruction dans le corps de boucle.

E = 4 n'est pas invariante car 4 est bien une constante mais il existe une autre affectation de E (dans le bloc 4) qui est E = 5.

C = E n'est pas invariante car E n'est pas un opérateur invariant.

D = B est invariante car la variable B l'est et D n'est pas affectée ailleurs.

F = 5 n'est pas invariante car il existe A = F (bloc 3) qui est une utilisation de F placée avant son affectation dans le corps de la boucle (3 est prédécesseur de 4).
Le processus du traitement des invariants consiste à examiner d'abord les boucles les plus internes et à déplacer leurs instructions invariantes au cours d'une première passe, puis il faut recommencer pour les boucles de niveau juste supérieur en tenant compte éventuellement des nouvelles instructions déjà déplacées etc... jusqu'à la boucle la plus externe. Si le niveau maximum d'imbrication des boucles du programme est n, il y aura n passes à effectuer.

## Par attributs

La première étape consiste à définir un attribut qui différencie les boucles et en conséquence, il distingue les instructions internes aux boucles des instructions hors boucle. Pour cela nous définissons un attribut $BO+$ tel que :

$$ BO+ = 0 \text{ si l'instruction n'est pas dans une boucle,} \\ = PI, \text{ numéro de l'instruction de boucle, sinon.} $$

Sa description est la suivante :

```
<P> ::= <L> ;
     BO(P)=0      (car P n'est bien sûr pas dans une boucle)
     BO(L)=BO(P)
```

```
<L> ::= <I>
     BO(I)=BO(L)
```

```
<L> ::= <L'> ; <I>
     BO(L')=BO(L)
     BO(I)=BO(L)
```

```
<I> ::= <ID> ; <L> ; END
     BO(ID)=BO(I)
     BO(L)=PI(ID) (car L est le corps de la boucle qui commence avec ID)
```
De cette façon BO porte bien le résultat cherché et le propage dans l'arbre sémantique, depuis la liste d'instructions L du programme jusque dans les variables. Dans ce qui suit nous sous-entendrons que le traitement de l'invariance ne se fait pour un non-terminal X donné que si BO(X) ≠ 0 car X doit figurer dans le corps d'une boucle pour être candidat à l'invariance.

Nous proposons pour la seconde étape, de déterminer l'invariance locale de chaque variable et ceci pour tous les blocs des boucles du programme. Rappelons que pour chacune d'elle il faut savoir :

- si elle apparaît ou non dans le bloc,

- si elle y est référencée ou affectée,

- si elle est affectée une ou plusieurs fois,

- si elle est référencée ou non avant son unique affectation dans le bloc.

Il faut donc établir une liaison entre les différentes occurrences d'une même variable, pour pouvoir transférer l'information de l'une à l'autre au fur et à mesure de la progression d'une passe simulée de compilation. Cependant, les attributs ne permettent pas de distinguer les différentes occurrences d'un même non-terminal car cette distinction ne peut pas se faire au niveau des règles de production de la grammaire, mais seulement au niveau dynamique. C'est pourquoi nous conserverons en table l'information acquise pour chaque variable donnée et nous nous y référerons pour déterminer l'optimisation des occurrences suivantes.

Soit TI↓- TIP↑ le couple d'attributs qui porte la Table d'Invariance dans laquelle il y a une entrée par bloc et par variable.

Initialement TI(non-terminal)(n° bloc,variable) = 0. A la fin de cette
passe, on a :

TI(b,V) = 0 si la variable V n'apparaît pas dans le bloc b,

TI(,V) = -1 si V n'est pas invariante,

TI(,V) = 1 si la dernière occurrence de V rencontrée était une affectation,

TI(,V) = 2 si la dernière occurrence de V rencontrée était une référence.
La sémantique qui décrit cette optimisation va se jouer essentiellement au niveau des deux règles de production suivantes :

<I> ::= <V> = <E> (dans laquelle V est toujours affectée)

TI(E) = TI(I)

TIP(I) = TIP(E)

IF TIP(I)(PB(I),V)=0 THEN TIP(I)(PB(I),V)=1

ELSE IF TIP(I)(PB(I),V) > 0 THEN TIP(I)(PB(I),V) = -1

<T> ::= <V> (dans laquelle V est toujours référencée en tant que Terme d'une expression)

TIP(T) = TI(T)

IF TIP(T)(PB(T),V)=0 THEN TIP(T)(PB(T),V) = 2

Pour la troisième étape, nous définirons le couple d'attributs IG↓-IGP↑ qui portera l'information d'invariance globale de chaque non-terminal.

IGP↑ = BO si le non-terminal est invariant par rapport à la boucle de numéro BO,
= 0 sinon.

IG↓ transporte la table d'invariance une fois remplie, elle lui est transmise dans la sémantique de la règle suivante :

<P> ::= <L> ;

IG(P) = TIP(L)

Rappelons qu'une variable V est invariante dans une boucle :

- si elle n'est affectée qu'une seule fois dans la boucle,

- si cette affectation est dans un bloc d'articulation a,

- s'il n'existe aucune référence à V dans les blocs prédécesseurs de a dans le corps de boucle.

Soit LA la Liste des blocs d'Articulation de la boucle, LP<sub>a</sub> et LS<sub>a</sub> les Listes des Prédécesseurs et Successeurs de a dans le corps de boucle.

L'essentiel de la sémantique qui détermine l'invariance d'une instruction
se résume dans les trois règles suivantes :

<I> ::= <V> = <E>

    IG(E) = IG(I)

    IF PB(I) & LA THEN IGP(I)=0, END.
    IF IG(I)(PB(I),V) = -1 THEN IGP(I) = 0, END.

    FOR b ∈ LP< PB(I) : IF IG(I)(b,V) > 0 THEN IGP(I)=0, END.
    FOR b ∈ LS< PB(I) : IF IG(I)(b,V) = 1 THEN IGP(I)=0, END.
    IF IGP(E) = 0 THEN IGP(I) = 0 ELSE IGP(I)=MAX(IGP(E), BO(I))

<E> ::= <E'> + <T>

    IG(E')=IG(E)
    IG(T)=IG(E)

    IF (IGP(E')=0) ∪ (IGP(T)=0) THEN IGP(E)=0
    ELSE IGP(E)=MAX(IGP(E'),IGP(T))

<T> ::= <V>

    IF PB(T) & LA THEN IGP(T) = 0, END.
    IF IG(T)(PB(T),V) = -1 THEN IGP(T) = 0, END.
    AFF = 0, B = 0,

    FOR b ∈ PB(T) ∪ LP< PB(T) ∪ LS< PB(T) :
        IF IG(T)(b,V) = 1 THEN AFF=AFF+1, B=b, IF AFF > 1 THEN IGP(T)=0, END.
        IF B = 0 THEN IGP(T) = BO(T).
    FOR b ∈ LP< B : IF IG(T)(b,V) = 2 THEN IGP(T) = 0, END.
    IGP(T) = BO(T).

Ceci nous donne l'invariance de V par rapport à la plus petite boucle qui la contient. Il suffit de recommencer ce traitement pour la boucle de niveau juste supérieur, si elle existe, en modifiant seulement LA, LP et LS. S'il est encore possible de conclure à l'invariance, ce n'est plus BO(V) qu'il faut affecter à IGP(V), mais plutôt le numéro de cette nouvelle boucle. On répètera ainsi le processus jusqu'à l'examen de la plus grande boucle qui contient V.
On remarque que cette description sémantique donne directement dans IGP(I)
le numéro de la boucle pour laquelle I est invariante, qu'il s'agisse de
boucles parallèles ou imbriquées. Il ne reste plus qu'à déplacer I en avant
de la boucle IGP(I). De même que pour la justification de l'invariance, le
déplacement d'une instruction nécessitera une table pour mémoriser le code
de cette instruction avant la passe qui engendrera le code optimisé.

Soient l'attribut tableau OBJ↑ qui porte le code objet de chaque
non-terminal et DE↑ qui contient les instructions invariantes à déplacer,
il a une entrée par boucle. Leur sémantique se décrit ainsi :

<L> ::= <L> ; <I>

OBJ(L) = OBJ(L')

IE(L) = IE(L')

IF IGP(I) = 0 THEN prolonger OBJ(L) par OBJ(I)
ELSE prolonger IE(L)(BO(L)) par OBJ(I)

<I> ::= <V> = <E>

OBJ(I)(PI(I)) = OBJ(V)(PI(I)) || ' = ' || OBJ(E)(PI(I))

<I> ::= <ID> ; <L> ; END

OBJ(I)(PI(I)) se compose de IE(L)(PI(ID)), OBJ(ID), OBJ(L) et 'END'
dans l'ordre.

Nous noterons que contrairement aux méthodes classiques qui
déplacent de proche en proche les instructions invariantes par passes
successives depuis les boucles les plus internes vers leur niveau d'imbri-
cation le plus externe, dans la méthode présentée ici, l'instruction à
transferer franchit en une seule étape toutes les boucles dans lesquelles
elle est invariante.
## CONCLUSION

Tout d'abord, une remarque est à faire : les attributs tels que DELTA les traite, ne peuvent décrire que la sémantique statique. Pourtant le déplacement des invariants est une question de sémantique dynamique car cette optimisation tient compte du graphe de la dynamique du programme et nous n'avons pas eu besoin de la notion d'attributs dynamiques pour déplacer les instructions invariantes. Nous avons simplement joué sur les attributs statiques en nous aidant de tables pour conserver l'information que les attributs ne portent que temporairement et qui nous est nécessaire pendant toute la durée de la compilation. Nous avons pu exprimer ainsi l'aspect dynamique de la sémantique. Nous n'avons pas joué à fond le rôle des attributs, nous l'avions annoncé (cf. page 6) : "nous nous engageons à n'utiliser les attributs que si leur intervention ne doit pas alourdir la description sémantique." Nous ne prétendons pas avoir écrit de la sémantique dynamique avec des attributs statiques, mais nous avons réalisé de la sémantique dynamique avec des attributs statiques associés aux méthodes classiques de compilation optimisée.

Nous avons appliqué ces résultats de recherche à la métacompilation d'un texte source pour obtenir le même texte source optimisé (indépendamment du calculateur utilisé). Le langage source choisi peut être évolué (type FORTRAN, ALGOL ou PL/1 ...) ou plus proche du calculateur (type triplets, quadruplets ou autre langage intermédiaire de compilation).

Cette formalisation sémantique apportée à l'application des algorithmes d'optimisation devrait minimiser les risques d'effets de bord bien connus en optimisation de code et de ce fait encourager la production de compilateurs optimiseurs. Le traitement de l'optimisation n'était ici qu'un pretexte car la méthode reste valable, quel que soit l'algorithme proposé, nous pensons notamment aux algorithmes de transformation de programmes qui conservent l'aspect sémantique [45].

Nous avons vu que la définition sémantique d'un langage s'exprime par des relations entre attributs. De façon analogue, la preuve d'un programme se démontre par déductions successives de
prédicats à travers les instructions. Les prédicats sont donc fonction
les uns des autres. Cette similitude nous encourage à rapprocher ces
deux notions pour donner une méthode de preuve de définitions par
attributs.

En ce qui concerne la notion d'équivalence, considérons deux
descriptions sémantiques par attributs, l'une optimisée et l'autre non, si
on démontre qu'elles sont équivalentes, il nous est permis de conclure
que la transformation effectuée par attributs a conservé la signification
du langage. Lorsque cette transformation est un algorithme d'optimisation,
on peut affirmer qu'il a correctement été défini dans la description par
attributs.

Dans le but d'atteindre cette conclusion, nous nous sommes
efforcés de traduire sémantiquement l'optimisation de code. Ainsi
l'optimisation faisant corps avec la définition du langage, nous
espérons faciliter la preuve que son application est correcte et obtenir
les garanties qui manquent dans ce domaine.
[21] Symposium on Compiler Optimization, University of Illinois, Urbana-Champaign, July 1970.

"A Formal Approach to Code Optimization".

A. AHO, R. SETHI and J. ULLMAN.

[22] Sigplan Notices, July 1970.

"Effectiveness of an Optimizing Compiler for Arithmetic Expressions".

J.A. PAINTER.

[23] Sigplan Notices, July 1970.

"Global Common Subexpressions Elimination".

J. COCKE.

[24] Courant Institute of Mathematical Sciences, New York University, April 1970.

"Programming Languages and their Compilers".

J. COCKE and J.T. SCHWARTZ.

[25] Colloque sur la programmation, Paris, Avril 1974.

"Non Existent of Program Optimizers in an Abstract Setting".

D.A. ALTON and J.L. LOWTHER.

[26] IBM System Journal, 3, 1970.

"Code Generation for Large-Language Compilers".

M. ELSON and S.T. RAKE.

[27] CACM, 12, 1, 1969.

"Object Code Optimization".

E.S. LOWRY and C.W. MEDLOCK.

[28] CACM, February, 1960.

"Sequential Formula Translation".

K. SAMELSON and F.L. BAUER.

[29] Academic Press Inc., New York, 1964.

"On Writing an Optimizing Translator for ALGOL 50".

D.H.R. HUXTABLE.

[30] IFIP Congress 1971.

"An Optimizing Compiler Design".

D. HOPKINS.

[31] CACM, 7, 3, 1964.

"A Note on Some Compiling Algorithms".

J.P. ANDERSON.
REFERENCES

[1] Mathematical Systems Theory, 2, 2, 1968.
"Semantics of Context-Free Languages".
D.E. KNUTH

[2] American Mathematical Society, 1967.
Proceedings Symposium in Applied Mathematics, 19.
"Assigning Meanings to Programs".
R.W. FLOYD

[3] Rapport de Recherche LABORIA, 20, juin 1973.
"DELTA : Système de Description de Langages et Traducteurs par Attributs".
L. BLAIZOT.

[4] Séminaires Langages et Traducteurs, IRIA, Juin 1973.
"Introduction à la notion d'attributs sémantiques". L. BLAIZOT.

"DELTA : système de Description de Langages et de Traducteurs par Attributs :
Présentation du système". J.L. BOUCHENEZ.

[5] Thèse d'Etat, Université Paul Sabatier de Toulouse, novembre 1974.
"De la définition à la traduction des langages de programmation : Méthode des attributs sémantiques".
B. LORHO.

[6] John Wiley & Sons, Inc. New York, 1971.
"Compiler Constructions for Digital Computers".
D. GRIES.

[7] ACM 74, November 11-13, San Diego, California, 1974.
"Semantic Attributes and Improvement of Generated Code".
D. NEEL and M. AMIRCHAHY

[8] Courant Computer Science Symposium, 5, March 1971.
"Design and Optimization of Compilers".
R. RUSTIN editor.

[9] JACM, 13, 1, 1966.
"ALPHA - An Automatic Programming System of High Efficiency".
A.P. YERSHOV
[21] Symposium on Compiler Optimization, University of Illinois, Urbana-Champaign, July 1970.

"A Formal Approach to Code Optimization".

A. AHO, R. SETHI and J. ULLMAN.

[22] Sigplan Notices, July 1970.

"Effectiveness of an Optimizing Compiler for Arithmetic Expressions".

J.A. PAINTER.

[23] Sigplan Notices, July 1970.

"Global Common Subexpressions Elimination".

J. COCKE.

[24] Courant Institute of Mathematical Sciences, New York University, April 1970.

"Programming Languages and their Compilers".

J. COCKE and J.T. SCHWARTZ.

[25] Colloque sur la programmation, Paris, Avril 1974.

"Non Existent of Program Optimizers in an Abstract Setting".

D.A. ALTON and J.L. LOWTHER.

[26] IBM System Journal, 3, 1970.

"Code Generation for Large-Language Compilers".

M. ELSON and S.T. RAKE.

[27] CACM, 12, 1, 1969.

"Object Code Optimization".

E.S. LOWRY and C.W. MEDLOCK.

[28] CACM, February, 1960.

"Sequential Formula Translation".

K. SAMELSON and F.L. BAUER.

[29] Academic Press Inc., New York, 1964.

"On Writing an Optimizing Translator for ALGOL 50".

D.H.R. HUXTABLE.

[30] IFIP Congress 1971.

"An Optimizing Compiler Design".

D. HOPKINS.

[31] CACM, 7, 3, 1964.

"A Note on Some Compiling Algorithms".

J.P. ANDERSON.
REFERENCES

[1] Mathematical Systems Theory, 2, 2, 1968.
"Semantics of Context-Free Languages".
D.E. KNUTH

[2] American Mathematical Society, 1967.
Proceedings Symposium in Applied Mathematics, 19.
"Assigning Meanings to Programs".
R.W. FLOYD

[3] Rapport de Recherche LABORIA, 20, juin 1973.
"DELTA : Système de Description de Langages et Traducteurs par Attributs".
L. BLAIZOT.

[4] Séminaires Langages et Traducteurs, IRIA, Juin 1973.
"Introduction à la notion d'attributs sémantiques". L. BLAIZOT.

"DELTA : système de Description de Langages et de Traducteurs par Attributs :
Présentation du système". J.L. BOUCHENEZ.

[5] Thèse d'Etat, Université Paul Sabatier de Toulouse, novembre 1974.
"De la définition à la traduction des langages de programmation : Méthode des attributs sémantiques".
B. LORHO.

[6] John Wiley & Sons, Inc. New York, 1971.
"Compiler Constructions for Digital Computers".
D. GRIES.

[7] ACM 74, November 11-13, San Diego, California, 1974.
"Semantic Attributes and Improvement of Generated Code".
D. NEEL and M. AMIRCHAHY

[8] Courant Computer Science Symposium, 5, March 1971.
"Design and Optimization of Compilers".
R. RUSTIN editor.

[9] JACM, 13, 1, 1966.
"ALPHA - An Automatic Programming System of High Efficiency".
A.P. YERSHOV
[32] CACM, 10, 8, 1967.
"On compiling algorithms for arithmetic expressions".
I. NAKATA.

[33] CACM, 12, 2, 1969.
"On arithmetic expressions and trees".
R.R. REDZIEJOWSKI.

[34] JACM, 17, 4, 1970.
"The Generation of Optimal Code for Arithmetic Expressions".
R. SETHI and J.D. ULLMAN.

[35] IBM System Journal, 5, 2, 1966.
"A Study of Replacement Algorithms for a Virtual-Storage Computer".
L. BELADY.

[36] JACM, 13, 1, 1966.
"Index Register Allocation".
L.P. HORWITZ, R.M. KARP, R.E. MILLER and S. WINOGRAD.

[37] CACM, 10, 9, 1967.
"A Comment on Index Register Allocation".
F. LUCCIO.

[38] CACM, 10, 4, 1967.
"One-Pass Compiler of Arithmetic Expression for a Parallel Processor".
H.S. STONE.

[39] Design and Optimization of Compilers, Prentice Hall, 1971.
"Monitoring Program Execution in the CDC 6000 Series Machine".
S. JASIK.

[40] CACM, 8, 7, 1965.
"Peephole Optimization".
W.M. Mc KEEMAN.

[41] Thèse d'Etat, Université de Paris VI, février 1975.
"Contribution à la formalisation de l'amélioration de code par attributs sémantiques".
D. NEEL.

[42] Annual Review in Automatic Programming, 5, 13, 1969.
"Program Optimization".
F.E. ALLEN.
[10] Cours de l'école de l'IRIA, février 1974.
"L'optimisation de code généré".
D. NEEL.

[11] CACM, 8, 8, 1965.
"Some Techniques used in ALCOR ILLINOIS 7090".
D. RIES and H.R. WIEHLE

[12] American Elsevier, New York 1969.
"Compiling Techniques".
F.R.A. HOPGOOD

[13] CACM, 12, 6, 1969.
"Generation of Optimal Code for Expressions via Factorization".
M.A. BREUER.

[14] CACM, 12, 12, 1969.
"Optimal Code for Serial and Parallel Computation".
R.J. FATEMAN

[15] The Computer Journal, 16, 4, 1973.
"A FORTRAN to FORTRAN Optimizing Compiler".
P.B. SCHNECK and E. ANGEL.

[16] Department of Computer Science, Carnegie Mellon Univ., PhD., June 1969.
"Some techniques for Algorithms Optimization with Application to Matrix Arithmetic Expressions".
R. WAGNER

[17] CACM, 12, 12, 1969.
"Optimization of Expressions in FORTRAN".
V.A. BUSAM and D.E. ENGLUND

[18] Courant Computer Science Symposium, 1971.
"A Catalogue of Optimizing Transformations".
F.E. ALLEN and J. COCKE.

[19] Computer Science Group, University of Washington, Seattle, Washington, PhD. 1972.
"Global Expression Optimization during Compilation".
G.A. KILDALL.

[20] CACM, 8, 6, 1965.
"On the Automatic Simplification of Computer Programs".
J. NIEVERGELT.
[43] GI 74 Fourth Annual Meeting, October 9-12, Berlin, Germany, 1974.
"Optimization of Generated Code by Means of Attributes : Local Elimination of Common Redundant Sub-Expressions".
D. NEEL, M. AMIRCHAHY and M. MAZAUD.

[44] ACM-NASA Congress, March 18-19, New York, USA, 1975.
"Removal of Invariant Statements from Nested-loops in a Single Effective Compiler Pass".
D. NEEL and M. AMIRCHAHY.

[45] Publications de l'Institut de Programmation, Paris, 1973.
"Les langages sans étiquettes".
J. ARSAC.