Ανάλυση διαθέσιμων εκφράσεων

Στο πεδίο των βελτιστοποιήσεων μεταγλωττιστών, η ανάλυση διαθέσιμων εκφράσεων (available expressions analysis) είναι ένας αλγόριθμος που εντοπίζει το σύνολο των εκφράσεων που δε χρειάζεται να υπολογιστούν ξανά σε κάθε σημείο ενός προγράμματος. Αυτές οι εκφράσεις τότε λέγεται ότι είναι διαθέσιμες σε αυτό το σημείο. Για να είναι διαθέσιμη μια συνάρτηση σε ένα σημείο του προγράμματος, πρέπει οι τελεστέοι της να μην αλλάζουν από κανένα μονοπάτι μεταξύ της παρουσίας της και του σημείου στο πρόγραμμα.

Η ανάλυση αυτή είναι ένα παράδειγμα προβλήματος ανάλυσης ροής δεδομένων προς τα εμπρός. Διατηρείται ένα σύνολο από διαθέσιμες εκφράσεις και κάθε εντολή αναλύεται για να βρεθεί αν αλλάζει τους τελεστέους μιας ή περισσότερων διαθέσιμων εκφράσεων. Από αυτό προκύπτουν σύνολα διαθέσιμων εκφράσεων στο τέλος κάθε βασικής ενότητας, γνωστής και σαν αρχή (outset) με όρους ανάλυσης ροής δεδομένων. Μια έκφραση είναι διαθέσιμη στην αρχή μιας βασικής ενότητας αν είναι διαθέσιμη στο τέλος κάθε μιας από τις προηγούμενες ενότητες αυτής. Αυτό δίνει κάποιες εξισώσεις στις οποίες συμμετέχουν τα διαθέσιμα σύνολα, οι οποίες και λύνονται με έναν επαναλητπικό αλγόριθμο.

Αναφορές

• Aho, Sethi & Ullman: Compilers - Principles, Techniques, and Tools Addison-Wesley Publishing Company 1986 (Αγγλικά)