En informatique, la recherche de sous-expressions communes est une technique d'optimisation de code qui cherche des instances d'expressions communes (c'est-à-dire renvoyant toutes la même valeur) et qui détermine si cela vaut la peine de les remplacer par une variable unique contenant la valeur calculée. Dans le code suivant : a = b * c + g; d = b * c * d; il peut être intéressant de transformer le code compilé comme si on avait écrit : tmp = b * c; a = tmp + g; d = tmp * d; « intéressant » signifie que le programme transformé s'exécutera plus vite que l'original. La possibilité d'effectuer une telle optimisation s'appuie sur une analyse des expressions disponibles (une analyse de flux de données). Une expression bc est disponible à un point p d'un programme si : chaque chemin depuis un nœud initial vers p évalue bc avant d'atteindre p ; il n'y a pas d'affectation de nouvelle valeur dans b ou c après leur évaluation, mais avant p. L'optimiseur comparera le coût au gain pour savoir si le coût du stockage en mémoire de la valeur tmp est inférieur au coût d'une multiplication ; en pratique, d'autres facteurs, comme le fait de disposer des valeurs dans tel ou tel registre intervient aussi. Ceux qui écrivent des compilateurs distinguent deux sortes de recherche de sous-expressions communes : la recherche locale de sous-expressions communes qui fonctionne au sein d'un même bloc de base et qui est donc une optimisation simple à implanter. la recherche globale de sous-expressions communes qui agit sur l'ensemble d'une procédure. Les deux sortes s'appuient sur l'analyser le flux de données pour savoir quelles expressions sont disponibles à tel ou tel endroit d'une procédure. Les avantages de la recherche de sous-expressions communes sont en général suffisants et c'est donc un type courant d'optimisation. Dans des cas simples comme celui de l'exemple qui précède, les programmeurs peuvent éliminer manuellement les expressions en double lorsqu'ils écrivent leur code.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Séances de cours associées (3)
Conversion de fermeture et analyse de flux de données
Explore la conversion de fermeture, le levage de fonction et l'analyse de flux de données pour l'optimisation de programme.
Optimisation de code : analyses accélérées
Explore les techniques pour accélérer les analyses de flux de données et discute de l'importance de l'ordonnancement des nœuds et de la traversée post-commande.
Optimisation des requêtes : heuristique et approche basée sur les coûts
Explore les principes d'optimisation des requêtes, les défis liés à l'estimation de la cardinalité et l'impact des erreurs sur la sélection des plans.
Publications associées (4)
Concepts associés (3)
Use-define chain
Within computer science, a Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain generally means the assignment of some value to a variable. A counterpart of a UD Chain is a Definition-Use Chain (DU Chain), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions.
Constant folding
Constant folding and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code. Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time.
Optimizing compiler
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption (the last three being popular for portable computers). Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.