Je suis en face d’un problème louche.
Je taf sur un compilateur C qui fait des choses très louches. Et parmi ces choses louches optimise des programmes.
Je cherche un exemple de programme pas trop debil, (qui calcule un truc intéressant) qui s’optimise, mais c’est super chaud.
Les deux optimisations considérées sont :
Élimination des sous expression commune
Qui va transformer le programme suivant
a = x + y;
b = x + y;
en
a = x + y;
b = a;
Car on a déjà calculé x + y
Et propagation de constante:
qui transforme
a =3
b = a + y;
en
a = 3;
b = 3 + y;
Vu qu’on connait la valeur de a.
Voila, ces deux optimisations sont classiques, le problème c’est trouver un exemple qui puisse justifier qu’on les as dans notre complio.
On peux pas montrer un exemple avec ca:
a = x + y;
b = x + y;
En disant “Oh regarder comme notre complio il optimise votre code debil”
Donc la première idée que j’ai, c’est d’utiliser des macros comme en C, en effet si je met un bon #define SIZE 300
Ya de forte chance que le code optimise des SIZE + 1 en 301.
Vous avez d’autre idées ?
Je paie des bières si vous trouvez des idées qui poutrent
Fraie un programme qui lit la grammaire du C (ou autre). Récupère les variables et fait les optimisations.
(on a fait çà l’année dernière en sujet de master (avec Flex et Bison qui sont des analyseurs grammaticaux)).
Je vois pas de méthodes génériques (pas de bidouilles) qui pourrait le faire =/.
[Hors propos]
Sauf qu’il faut savoir que bien souvent, le compilateur C (standard) optimise de telle sorte à ce que les instructions se passent rapidement, échange de registre etc etc…
a mon avis tu ne gagnera rien, a part perdre du temps en prétraitement.
[/HS]
Edit 1 :
… Erm … Après relecture je suis HS total … je rerédige XD
Edit 2 :
Pourquoi ne pas utiliser un exemple sympa genre : Calcul de suite de fibo / factorielle.
Fib et factorielle, sont trop simple pour être optimisés par les deux optimisation décrites. A aucun moment tu vas ecrires deux fois la mêmes opérations, Et pas de propagation de constantes non plus. Je pense qu’il faut plus trouvé un genre de hack. comme les macros
Ou bien trouvé un programme qui s’optimise bien une fois compilé. Mais ça c’est chaud.
Exemple : si on compilait nos tableaux comme en C, en transformant des t[i] en t + i4, je pense qu’on ferai apparaitre plein de i4 qui s’optimiserait avec CSE dans le programme compilé.
Et le problème, vient pas du comment faire les optimisations, mais juste de trouver un exemple cool.
tu travaille sur des images bitmap en réutilisant les mêmes formules (passage en largeur et ensuite en hauteur) et les mêmes valeurs pour des pixels voisins.
Pour ce qui est de la taille du code: j’en ai codé un en assembleur DLX, donc c’est vraiment pas gros.
EDIT: de plus, le filtre de canny nécéssite un parametre souvent noté sigma qui pourrait etre un tres bon exemple pour la propagation de constante.
Yep je comprend, mais au niveau du code, ta même formule tu vas l’écrire une fois, et je suppose qu’elle va être dans une boucles. et si c’est le cas ça rentre pas dans le cadre de mes optimisations. Mais je vais quand même regarder les algo avec des matrices.
ouais mais non, en fait ^^. A prendre avec des pincettes ce que je vais dire, vu que je parle de mémoire:
pour que l’algo se traine pas trop, tu dois travailler sur plusieurs pixels en même temps. Il me semble que sur une seule boucle, on travaillait sur une sous matrice 3x3 et que plusieurs sous-expressions étaient utiles dans les deux ‘balayages’ (vertical & horizontal). Donc, a ne calculer qu’une fois pour plusieurs utilisations.
J’essayerais de retrouver mon rapport sur le sujet, et pas te dire les choses de mémoire.
Le problème c’est pas de savoir comment s’optimise le truc, si je compile les tableau avec les multiplication, je oeux avoir une autre passe plus tard, qui va la transformer en décalage de bits,
Mais ça fera toujours apparaitre, des truc qui se feront optimiser par CSE.
Bon je pense que ca va intéresser personne, mais je donne quand même la solution que j’ai trouvée.
J’ai codé la multiplication de matrice. Et codant les matrices sur un tableau à une case, donc la case i,j de la matrice m devient m[i*p+j].
Et dans le code de la multiplication:
int mult (int * a, int * b, int * c, int m, int n, int p){
int i, j, k;
i = 0;
while (i < m){
j = 0;
while (j < p){
c[i*p+j] = 0;
k = 0;
while (k < n){
c[i*p+j] = c[i*p+j] + a[i*n+k]*b[k*p+j];
k = k + 1;
}
j = j + 1;
}
i = i + 1;
}
}
Et le i*p+j s’optimise plein de fois, et la fonction calcule un truc intéressant, j’ai prouvé que chaque case de la matrice c, contient bien la bonne valeur.
C’est tout con mais ca à suffit pour écrire un papier.
