Abstrakt. Vi beskriver en ny teknik för beräkning av procedursammanfattningar för att utföra en interprocedural analys på program. Processsammanfattningar beräknas genom att göra en bakåtanalys av förfaranden, men det finns två viktiga nya inslag: (i) information sprids med hjälp av "generiska" påståenden (i stället för regelbundna påståenden som används i intraprocedural analys); och (ii) enande används för att förenkla dessa generiska påståenden (därmed generalisera vår senaste teknik att använda enande för att förenkla regelbundna påståenden i intraprocedural analys [6] ). Vi beskriver under vilka förhållanden denna teknik ger effektiva interprocedurala analyser. Vi illustrerar denna teknik genom att tillämpa den på två abstraktioner: unary otolkade funktioner och linjär aritmetik. I det första fallet får vi en PTIME-algoritm för ett specialfall av det långvariga öppna problemet med interprocedural global värdenumrering (det speciella fallet är att vi anser att unary otolkade funktioner istället för binära). Detta kräver också att man utvecklar effektiva algoritmer för att manipulera singleton sammanhangsfri grammatik, och bygger vidare på ett tidigare arbete av Plandowski [13]. I linjärt aritmetiskt fall får vi nya algoritmer för exakt interprocedural analys av linjära aritmetiska program med komplexitet som matchar den av den mest kända deterministiska algoritmen [11].
En allmän teknik för att konstruera procedursammanfattningar REF har tillämpats på unary otolkade funktioner och linjär aritmetik.
Computing procedure summaries for interprocedural analysis
{'venue': 'ESOP', 'journal': None, 'mag_field_of_study': ['Computer Science']}