Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
E-Path는 제어 흐름 그래프(CFG) 상에서 등가 포화(Equality Saturation)를 수행하기 위한 새로운 데이터 구조를 제안합니다. 기존 시스템의 정규화 한계를 극복하여, 명령어 시퀀스 간의 등가성을 기록함으로써 루프와 같은 제어 구조를 비파괴적으로 최적화합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.PL (Programming Languages)의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기현대의 등가 포화 (Equality Saturation) 시스템은 위상 순서 문제 (Phase-ordering problem)를 겪지 않으면서 방대한 양의 동등한 프로그램 공간을 탐색함으로써 표현 수준 (Expression-level)의 재작성 (Rewrites)에서 탁월한 성능을 발휘합니다. 그러나 이러한 시스템은 임의의 제어 흐름 그래프 (Control-flow graphs, CFG) 상에서 등가성을 직접 표현하는 데 어려움을 겪으며, 최적화가 수행되기 전에 구조화된 형태나 트리 형태 (Tree-like forms)로 정규화 (Normalization)하는 과정을 요구하는 경우가 많습니다. 본 논문에서는 제어 흐름 그래프 (Control-flow graphs) 상에서 등가 포화 (Equality-saturation) 스타일의 최적화를 수행하기 위한 프로토타입 프레임워크인 E-Path 데이터 구조를 제시합니다. E-Path는 개별 표현 (Expressions) 사이의 합동 (Congruence)을 표현하는 대신, 컴파일러 중간 표현 (Intermediate Representation, IR) 내에 임베딩된 명령어 시퀀스 (Instruction sequences) 간의 등가성을 기록합니다. 이 프로토타입에서 E-Path는 컴파일러 백엔드 (Backend)에서 사용되는 제한된 ANF 기반 제어 흐름 그래프 (Control-flow graph) 상에 인스턴스화되었으나, 모델 자체는 IR에 구애받지 않도록 (IR-agnostic) 설계되었습니다. 명령어 시퀀스를 합동 (Congruence)의 기본 단위로 취급함으로써, E-Path는 여러 개의 동등한 프로그램 변형 (Program variants)을 동시에 보존하면서 루프 (Loops) 및 기타 제어 흐름 구조 (Control-flow structures)의 비파괴적 최적화 (Non-destructive optimization)를 가능하게 합니다. 이를 통해 전통적인 CFG 최적화들을 기저 그래프 (Underlying graph)의 파괴적인 변형 (Destructive mutation) 없이 재작성 주도형 변환 (Rewrite-driven transformations)으로 표현할 수 있습니다.