Sammanhangskänsliga pekaranalysalgoritmer med full "tunga kloning" är kraftfulla men anses allmänt vara för dyra för att inkludera i produktionskompilatorer. Detta dokument visar för första gången att en kontextkänslig, fältkänslig algoritm med full högkloning (genom acykliska samtalsvägar) verkligen kan vara både skalbar och extremt snabb i praktiken. Totalt, algoritmen kan analysera program i intervallet 100K-200K linjer av C-kod i 1-3 sekunder, tar mindre än 5% av den tid det tar för GCC att sammanställa koden (som inte innehåller någon hel-programanalys), och skalar väl över fem storleksordningar av kodstorlek. Den kan också analysera Linuxkärnan (ca 355K kodrader) på 3,1 sekunder. Papperet beskriver de stora algoritmiska och tekniska designval som krävs för att uppnå dessa resultat, inklusive (a) använda flöde-okänslig och enande-baserad analys, som är nödvändiga för att undvika exponentiellt beteende i praktiken; (b) offra kontext-känslighet inom starkt anslutna komponenter i anropsgrafen; och (c) noggrant eliminera flera typer av O(N 2 ) beteenden (i stort sett utan att påverka precision). De tekniker som används för (b) och (c) eliminerade flera stora flaskhalsar för skalbarhet, och båda kan generaliseras till andra kontextkänsliga algoritmer. Vi visar att de tekniska valen tillsammans minskar analystiden med upp till 3x-21x i våra tio största program, och att besparingarna växer kraftigt med programmets storlek. Slutligen sammanfattar vi kortfattat resultaten som visar hur exakt analysen är.
DSA REF representerar en Steensgarrds enhetsbaserad pekaranalys med full högkloning.
Making context-sensitive points-to analysis with heap cloning practical for the real world
{'venue': "PLDI '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}