Fiche CCMP2 3
Liveness
Control Flow Graph
Control Flow Graph: un graphe de flot de contrôle est une représentation sous forme de graphe de tous les chemins qui peuvent être suivis par un programme durant son exécution.
On se rend compte via les slides que si l’on réalise les Control Flow Graph naivement et sans contraintes, on se retrouve avec des graphs gigantestes pour des opérations très simple.
→ Il va donc falloir optimiser notre graph en retirant des choses inutiles.
Liveness
Liveness: Durée de vie d’une variable.
Sur la slide 12/39, on se rend bien compte que certaines variables ne sont plus du tout utilisé à un certain moment du code. Comment déterminer la durée de vie d’une variable ?
Soit in[n] les variables vivantes en entrée et out[n] les variables mort en sorties.
Alors on a:
in[n] = use[n] ⋃ (out[n] \ def[n])
out[n] = ⋃s∈succ[n]in[s]
En outre:
- pour avoir le in[n] il s’agit des variables utilisés à cette étape ainsi que les variables vivantes à n mais qui ont défini auparavant. (
Pas celle qui ont été défini à la ligne n)
- Pour avoir les out[n] on regarde les successeurs de l’étape n, et les variables encore vivantes à cette étape.
Question
Pas vraiment une question mais je suis pas trop sûr de mes explications. J’ai peut être mal compris les formules. Pouvez-vous me confirmer si cela est correct ? (Notamment la partie “en outre”) svp.
Voir slides 14/39 pour comprendre liveness forward et 15/39 pour liveness backward
Reaching definition
Question
Je n’ai pas bien compris que sont gen et kills et à quoi cela sert.
Je pourrais ensuite comprendre l’algorithme par moi même si besoin.
Autres optimisations
Constant Propagation
Si on voit qu’une variable est assigné et qu’elle utilisé uniquement en lecture après, alors on peut la remplacer par une constante.
Copy Propagation
Question
Je n’ai pas compris ce que c’était.
Graph d’interference
Question
J’ai compris ce que cela était mais pas comment on le construit. Est-il possible d’avoir une explication avec l’exemple des slides (avec a, b et c) svp.
Question
Pas vraiment une question, mais si vous êtes arrivé jusque là, MERCI beaucoup d’avoir prit le temps de répondre. J’espere que cela ne vous a pas prit beaucoup de temps libre.
Fiche CCMP2 3
Liveness
Control Flow Graph
Control Flow Graph: un graphe de flot de contrôle est une représentation sous forme de graphe de tous les chemins qui peuvent être suivis par un programme durant son exécution.
On se rend compte via les slides que si l’on réalise les Control Flow Graph naivement et sans contraintes, on se retrouve avec des graphs gigantestes pour des opérations très simple.
→ Il va donc falloir optimiser notre graph en retirant des choses inutiles.
Liveness
Liveness: Durée de vie d’une variable.
Sur la slide 12/39, on se rend bien compte que certaines variables ne sont plus du tout utilisé à un certain moment du code. Comment déterminer la durée de vie d’une variable ?
Soit in[n] les variables vivantes en entrée et out[n] les variables mort en sorties.
Alors on a:
in[n] = use[n] ⋃ (out[n] \ def[n])
out[n] = ⋃s∈succ[n]in[s]
En outre:
Pas vraiment une question mais je suis pas trop sûr de mes explications. J’ai peut être mal compris les formules. Pouvez-vous me confirmer si cela est correct ? (Notamment la partie “en outre”) svp.
Voir slides 14/39 pour comprendre liveness forward et 15/39 pour liveness backward
Reaching definition
Je n’ai pas bien compris que sont gen et kills et à quoi cela sert.
Je pourrais ensuite comprendre l’algorithme par moi même si besoin.
Autres optimisations
Constant Propagation
Si on voit qu’une variable est assigné et qu’elle utilisé uniquement en lecture après, alors on peut la remplacer par une constante.
Copy Propagation
Je n’ai pas compris ce que c’était.
Graph d’interference
J’ai compris ce que cela était mais pas comment on le construit. Est-il possible d’avoir une explication avec l’exemple des slides (avec a, b et c) svp.
Pas vraiment une question, mais si vous êtes arrivé jusque là, MERCI beaucoup d’avoir prit le temps de répondre. J’espere que cela ne vous a pas prit beaucoup de temps libre.