E-Path: 제어 흐름 그래프 (Control-Flow Graphs)를 위한 등가 포화 (Equality Saturation)

현대의 등가 포화 (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)으로 표현할 수 있습니다.