스틴스고르 알고리즘
Steensgaard's algorithm컴퓨터 과학에서 Steensgaard 알고리즘은 확장 가능하고 흐름에 민감하지 않은 포인터 분석 알고리즘입니다.속도(예를 들어 LLVM [1]컴파일러 프레임워크에서 구현 가능) 때문에 컴파일러에서 자주 사용됩니다.이 알고리즘은 원래 형식에서 필드, 컨텍스트 및 어레이에 민감하지 않았습니다.
Steensgaard의 알고리즘은 부분집합 제약에 기반을 둔 Andersen의 알고리즘과 달리 동등 [2]제약에 기반을 두고 있다.이를 통해 Union-Find 데이터 구조를 사용하여 포인트 투 정보를 추적할 수 있습니다.이 선택에 의해 알고리즘은 고유의 속도를 얻을 수 있습니다.유니온 찾기 데이터 구조를 사용하여 구현될 경우 입력 프로그램 크기의 선형 공간과 거의 선형 시간이 됩니다.
Bjarne Steensgaard의 알고리즘 공식은 유형 추론 및 유형 확인에 관한 것이었다.Steensgaard는 C와 같은 포인터로 다른 공통 언어의 본질적인 특성을 포착하는 명령형이지만 일반적인 포인터 언어에 대한 포인트 투 분석을 제안했다.언어 의미론 및 입력 규칙이 분석을 구성합니다.
레퍼런스
- ^ "LLVM Alias Analysis Infrastructure — LLVM 8 documentation". releases.llvm.org. Retrieved 2022-04-22.
- ^ (2015년, 14페이지)
- Steensgaard, Bjarne (1996). "Points-to analysis in almost linear time" (PDF). POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 32–41. doi:10.1145/237721.237727. ISBN 0-89791-769-3.
- Smaragdakis, Yannis; Balatsouras, George (2015). "Pointer Analysis" (PDF). Foundations and Trends in Programming Languages. 2 (1): 1–69. doi:10.1561/2500000014. Retrieved May 30, 2019.
