compilation

compilation

[Jean-Christophe Filliatre]

[-- Attachment #1: Type: text, Size: 1586 bytes --]

Re: compilation

[David Monniaux]

[ENGLISH FURTHER IN THE TEXT]

On Thu, 13 Feb 1997, Jean-Christophe Filliatre wrote:

> 1. J'aimerai savoir si :
> 
> 	let b = true
> 	let f = if b then f1 else f2
> 
>    est compilé en f1, c'est-à-dire si la branche d'un "if" est
>    directement sélectionnée lorsque le booléen est "true" ou "false"
>    (sans l'évaluer, bien sûr ; simplement directement égal à "true" ou
>    "false" au moment de la compilation)
>    La raison de ma question est que cela permettrait d'avoir des options
>    de compilation directement en Caml sans perdre d'efficacité.

A ma connaissance, le compilateur ne fait pas de réductions même
triviales... Par exemple
let f=5;;
let g () = 3 * f;;
compile g vers une fonction qui est sémantiquement une constante, mais qui
en pratique prend f (lié =3), le multiplie par 3...

Un bon compilateur C, par contre, simplifierait les expressions...
Cela dit, les systèmes d'analyse de flot et d'optimizations des
compilateurs C réellement utilisés sont énormes...

> =english=====================================================================
> 
> 1. I would like to know if
> 
> 	let b = true
> 	let f = if b then f1 else f2
> 
> is compiled as f1, that is if the branch of an "if" expression is
> directly selected when the boolean expression is "true" or "false"
> (without performing any computation on it, of course; just directly
> equal to the constructor "true" or "false").
> The reason of this question is that it would allow compile options in
> Caml without any loss of efficiency.

To my knowledge, the Ocaml compiler doesn't perform any kind of reduction,
even trivial. For instance,

let f=3;;
let g () = f*4;;
compiles g to a function that is semantically a constant, but that in
effect takes f (lié =3) and multiplies it by 4.

A good C compiler, nevertheless, would simplify those expressions... But
the flow analysis and optimization part of a "real" C compiler is huge...

"Si l'informatique marchait, cela se saurait."
http://www.ens-lyon.fr/~dmonniau

Re: compilation

[Xavier Leroy]

> [english summary at the end of this mail]

> 1. J'aimerai savoir si :
>
> 	let b = true
> 	let f = if b then f1 else f2
>
>    est compilé en f1, c'est-à-dire si la branche d'un "if" est
>    directement sélectionnée lorsque le booléen est "true" ou "false"
>    (sans l'évaluer, bien sûr ; simplement directement égal à "true" ou
>    "false" au moment de la compilation)

Non, il n'y a pas de propagation des constantes dans le compilateur
Objective Caml. Cependant, b n'est teste qu'une seule fois, et non pas
a chaque appel de f, qui se branche directement sur le code de f1
(voir question suivante).

>    La raison de ma question est que cela permettrait d'avoir des options
>    de compilation directement en Caml sans perdre d'efficacité.

C'est possible, a condition de bien sortir les tests des
fonctions. P.ex. ne pas ecrire

        let f x           if debug then ...;
          ...

(test a chaque appel de f), mais plutot

        let f           if debug then fun x -> ...; ...
                   else fun x -> ...

> 2. de la même manière, est-ce que
>
> 	let f = fun x -> e
> 	let f1 = f
> 	
>    est compilé en remplaçant tout appel à f1 par un appel à f ?

Oui. En fait, les identificateurs f et f1 ont la meme valeur
fonctionnelle, qui est une fermeture du code de fun x -> e.

>    Ma question est, là encore, de savoir si on ne perd pas
>    d'efficacité en renommant des fonctions.

Il n'y a pas de surcout a l'appel de fonction.

- Xavier Leroy

> =english====================================================================>
> 1. I would like to know if
>
> 	let b = true
> 	let f = if b then f1 else f2
>
> is compiled as f1, that is if the branch of an "if" expression is
> directly selected when the boolean expression is "true" or "false"
> (without performing any computation on it, of course; just directly
> equal to the constructor "true" or "false").

No, there's no constant folding in the compiler. However, b will be
tested only once, not at each call to f, so that's still fairly efficient.

> 2. the same way, is
>
> 	let f = fun x -> e
> 	let f1 = f
>
> compiled by replacing any call to f1 by a call to f ?

No, f and f1 have the same functional value: a closure of the code for
fun x -> e.

> The question is still to known if we don't loose efficiency by
> renaming functions.

We don't.

Re: compilation

[Franck Cassez]

Bonjour Jean-Christophe,

	concernant les evaluations a la compilation,
j'avais pose une question similaire a Pierre Weis 
l'annee derniere (mon but etait
d'``accelerer'' un programme): je pense que l'exemple suivant
peut t'interesser.

A+

Franck.

- Franck.Cassez@univ-brest.fr - Departement d'Informatique  - 
-- Universite de Bretagne Occidentale  6, Avenue Le Gorgeu --
----   BP 809  ----   29285 Brest Cedex  ----   FRANCE   ----
-- tel: (+33) 02 98 01 69 59 -- fax: (+33) 02 98 01 69 56  --

dixit Pierre :
Je m'explique soit la fonction f:

let f a x = if a then (x + 1) else (x - 1);;

alors f true est la fonction x -> if true then (x + 1) else (x - 1) et non
pas la fonction x -> x + 1

On obtient une petite acce'le'ration en e'crivant:

let f a = if a then (fun x -> x + 1) else (fun x -> x - 1);;

car alors f true est (fun x -> x + 1). Cependant cette propagation des
constantes par le compilateur du (me'ta)-langage n'est pas de bonne
me'thodologie (elle n'est pas efficace). Pour beaucoup gagner il faut
re'aliser un ve'ritable compilateur qui analyse les programmes sources
du langage a` compiler et les optimise lui-me^me.