| Περίληψη |
Η ανάλυση δεικτών είναι σημαντικό συστατικό των περισσότερων στατικών αναλύσεων. Η στατική ανάλυση δεικτών χρίζει πολλών εφαρμογών, όπως η αύξηση της ακρίβειας και της αποδοτικότητας των βελτιστοποιήσεων στους μεταγλωττιστές προγραμμάτων, οι αυτόματες παραλληλοποιήσεις κώδικα, και τα εργαλεία εντοπισμού λαθών. Συνήθως οι υλοποιήσεις ανάλυσης δεικτών βασίζονται σε γλώσσα πηγαίου κώδικα κι εκμεταλλεύονται τα χαρακτηριστικά των γλωσσών για να αυξήσουν την ακρίβεια των απαντήσεων τους, όπως πχ. το σύστημα τύπων. Ωστόσο, αυτό επιτρέπει σε διαφορετικές υλοποιήσεις να δώσουν διαφορετικά αποτελέσματα βάση της ακρίβειας κι της απόδοσης τους, καθιστώντας μ' αυτόν τον τρόπο, απαραίτητη την υλοποίηση διαφορετικού αλγορίθμου για κάθε διαθέσιμο front-end ενός πολυγλωσσικού μεταγλωττιστή. Αντίθετα, η ανάλυση δεικτών για μια γλώσσα ενδιάμεσης αναπαράστασης είναι πιο ευρεία, θυσιάζοντας, όμως, την ακρίβεια που δίνει μια γλώσσα πηγαίου κώδικα. Συνεπώς, βρισκόμαστε μπροστά σ' έναν ενδιαφέρον συμβιβασμό, όπου ο βέλτιστος τρόπος επιτυγχάνει τη μέγιστη ακρίβεια για τη `χαμηλότερη' δυνατή αναπαράσταση γλώσσας. Η εργασία αυτή παρουσιάζει τη σχεδίαση κι υλοποίηση μιας ανάλυσης δεικτών για τη γλώσσα αναπαράστασης του LLVM. Υλοποιήσαμε μια επέκταση της ανάλυσης δεικτών τύπου Andersen, που χρησιμοποιείται ευρέως για τον υπολογισμό τέτοιας πληροφορίας κυρίως λόγω της κλιμακωσιμότητα (scalability) της. Η ανάλυση υπολογίζεται κατευθείαν στη γλώσσα αναπαράστασης του LLVM, καθιστώντας την εφαρμόσιμη σε όλες τις γλώσσες που μπορούν να μεταφραστούν σ'αυτή την αναπαράσταση. Σε όρους στατικής ανάλυσης, η ανάλυση είναι ένας type-based, inter-procedural, flow-insensitive, και context-insensitive αλγόριθμος, ακριβώς όπως οι περισσότερες εφαρμογές του αλγορίθμου Andersen, με την προσθήκη όμως του field-sensitivity για περισσότερη ακρίβεια σε τύπους δυναμικών δομών. Ο αλγόριθμος είναι σε θέση να ανταποκριθεί σε μια πλήρη σειρά ερωτημάτων δεικτών και να παρέχει σημαντικά μεγαλύτερη ακρίβεια απ' ότι ο κλασσικός αλγόριθμος, λόγω του field-sensitivity. Αξιολογήθηκε χρησιμοποιώντας 3 διαφορετικές σουίτες από 20 προγράμματα C ανοικτού κώδικα που κυμαίνονται από χίλιες μέχρι 230 χιλιάδες γραμμές πηγαίου κώδικα, αποδεικνύοντας την αποτελεσματικότητα της τεχνικής και παρέχοντας μια ποιοτική αξιολόγηση προς άλλες αλγοριθμικές προσεγγίσεις.
|
Static pointer analysis on intermediate representation for compilation optimizations
