Allocation de registres

Dans un compilateur, l'allocation de registres est une étape importante de la génération de code. Elle vise à choisir judicieusement dans quel registre du processeur seront enregistrées les variables durant l'exécution du programme que l'on compile. Les registres sont des mémoires internes au processeur, généralement capables de contenir un mot machine. Les opérations sur des valeurs rangées dans des registres sont plus rapides que celles sur des valeurs en mémoire vive, quand ce ne sont pas les seules possibles. Mais un processeur compte rarement plus de quelques dizaines de registres, bien trop peu pour toutes les variables d'un programme. Il est donc crucial de choisir avec pertinence les variables qui doivent résider dans les registres à chaque étape de l'exécution. Cela étant difficile dans les premières étapes de la compilation, on commence par faire comme si l'on disposait d'un nombre illimité de registres, puis l'on attribue à ces registres virtuels des registres réels ou des

À 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.

Publications associées (6)

Publications associées

Chargement

Personnes associées (2)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (23)

Concepts associés

Chargement

Cours associés (9)

Cours associés

Chargement

Séances de cours associées (19)

Afficher plus

Séances de cours associées

Chargement

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 tim

Registre de processeur

Un registre est un emplacement de mémoire interne à un processeur. Les registres se situent au sommet de la hiérarchie mémoire : il s'agit de la mémoire la plus rapide d'un ordinateur, mais dont le c

Compilateur

En informatique, un compilateur est un programme qui transforme un code source en un code objet. Généralement, le code source est écrit dans un langage de programmation (le langage source), il est de

CS-420: Advanced compiler construction

Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time system for a simple functional programming language.

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language into the new web standard for portable binaries called WebAssembly ( https://webassembly.org/ )

CS-307: Introduction to multiprocessor architecture

Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce the essential technologies required to combine multiple processing elements into a single computer.

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Philip Brisk, Paolo Ienne, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; however, converting each procedure to static single assignment (SSA) form ensures a chordal interference graph, which can be colored in O(vertical bar V vertical bar+vertical bar E vertical bar) time; the interprocedural interference graph (IIG) is not guaranteed to be chordal after this transformation. An extension to SSA form is introduced which ensures that the IIG is chordal, and the conversion process does not increase its chromatic number. The resulting IIG can then be colored in linear-time.

2010

Chargement

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

Philip Brisk, Paolo Ienne, Ajay Kumar Verma

Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is spilled to memory. Previously, an optimal polynomial-time algorithm for this problem has been presented for individual procedures represented in Static Single Assignment (SSA) Form. This result is now extended to complete programs (or sub-programs), as long as: (1) each procedure is represented in SSA Form; and (2) at every procedure call, all live variables are split at the call point. With this representation, it is possible to ensure that the interprocedural interference graph (IIG) is chordal, and can therefore be colored optimally in polynomial time. An optimal coloring of the IIG can be achieved by allocating registers for each procedure individually. Previous work has shown that optimal register allocation in SSA Form does not require an interference graph. Optimal interprocedural register allocation, therefore, is achieved without constructing an interference graph, giving the optimal algorithm a significant runtime advantage over prior sub-optimal heuristics.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2007

Chargement

Modelling Resource Dependencies

Simon Bliudze, Alena Simalatsar, Alina Zolotukhina

The major research in the resource management literature focuses primarily on two directions: 1) specification languages for formulating resource requests and 2) constraint problems modelling allocation and scheduling. Both directions assume the knowledge of the underlying platform architecture and the dependencies it induces on the usage of the various resources. In this report we bridge this gap, by introducing Constraint-Flow Nets (cfNets). A cfNet is defined by a set of resources and dependencies between them, each dependency having an associated constraint. The model is inspired by Petri Nets, with resources corresponding to places and dependencies—to transitions. Given an architecture of dependent resources, an initial resource request is propagated through the dependencies. The generated constraints are then conjuncted into the global allocation constraint. We study the notion of conflicts in cfNets and prove that for conflict-free cfNets the global allocation constraint can be constructed unambiguously. Furthermore, we provide an efficient algorithm for conflict detection.

2016

Chargement