I detta dokument redovisas ett nytt tillvägagångssätt för att lösa en delmängdsbaserad points-to analys för Java med hjälp av Binary Decision Diagrams (BDDs). I modellkontrollgemenskapen har BDD visat sig vara mycket effektiva för att representera stora uppsättningar och lösa mycket stora kontrollproblem. Vårt arbete visar att BDDs också kan vara mycket effektivt för att utveckla en poäng-till-analys som är enkel att genomföra och som skalar väl, i både rum och tid, till stora program. I dokumentet introduceras först BDD och verksamhet på BDD med hjälp av några enkla poäng-till-exempel. Därefter presenteras en komplett delmängdsbaserad poäng-till-algoritm, uttryckt helt med hjälp av BDD och BDD-operationer. Denna algoritm förfinas sedan genom att hitta lämpliga variabla order och genom att göra algoritmen propagera uppsättningar stegvis, för att komma fram till en mycket effektiv algoritm. Experimentella resultat ges för att motivera valet av variabel beställning, för att visa förbättringen på grund av inkrementalisering, och för att jämföra prestanda BDD-baserade lösare med en effektiv handkodad graf-baserad lösare. Slutligen, baserat på resultaten från den BDD-baserade lösaren, presenteras en mängd BDD-baserade frågor, inklusive poäng-till-fråga.
Det BDD-baserade genomförandet av de delmängdsbaserade algoritmerna förbättrar ytterligare verksamhetens effektivitet på punkter-att sätta REF.
Points-to analysis using BDDs
{'venue': "PLDI '03", 'journal': None, 'mag_field_of_study': ['Computer Science']}