superoptimization - 모음

https://llvm.org/devmtg/2019-10/slides/Hsu-Souper-ChargingPeepholes.pdf

https://users.cs.utah.edu/~regehr/dataflow-pruning.pdf

https://arxiv.org/pdf/1711.04422.pdf

A Synthesizing Superoptimizer

 

 

https://llvm.org/devmtg/2011-11/Sands_Super-optimizingLLVMIR.pdf

2011년 superoptimization 의 컨셉에 대해 이해하기 좋은 자료

 

Synthesis without Syntactic Templates

https://polgreen.github.io/polgreen_thesis.pdf

 

Sound and Automated Synthesis of Digital Stabilizing Controllers for Continuous Plants

https://www.researchgate.net/publication/309207296_Sound_and_Automated_Synthesis_of_Digital_Stabilizing_Controllers_for_Continuous_Plants

 

Counterexample Guided Inductive Synthesis Modulo Theories

https://link.springer.com/chapter/10.1007/978-3-319-96145-3_15

 

 

Evaluating Souper: A Synthesizing Superoptimizer - SOUPER 스터디성격

https://repository.tudelft.nl/islandora/object/uuid%3Aba4ce2af-cca7-4890-b1ec-69683f627a42

 

QSynth - A Program Synthesis based Approach for
Binary Code Deobfuscation

https://www.ndss-symposium.org/wp-content/uploads/bar2020-23009.pdf

 

Faster sorting algorithms discovered using deep reinforcement learning

https://www.nature.com/articles/s41586-023-06004-9

 

 

superoptimization 에 대한 단상

llvm opt pass 에도 여러가지 정형화된 연산에 대한 최적화를 하는 과정이 존재한다. 

InstCombine - InstSimplify 같은 패스가 그렇다.

 

LLVM이 처음 등장했을 때는 GCC에 대한 절망적인 진입장벽 때문에 크게 선호되었다.
특히 front-middle-back 의 구조 분리 및 개발에 필요한 다수의 유용한 소스코드가 제공되는 것 때문에

LLVM을 기반으로 한 연구가 많이 이루어질 수 밖에 없었다.

 

하지만 LLVM 도 이제는 거대 오픈 소스 프로젝트가 되었고
어떤 Code를 병합할 때는 그에 대한 가치 평가가 엄격하게 이뤄질 수 밖에 없다 .

때문에 InstCombine - InstSimplify 같은 peephole 최적화에서는 보편적이고 범용적인 대수적인 측면의 접근 방식이 된다.

 

superoptimization이라고 해서 이런 접근 방식에 차이가 있는 것은 아니다.

1. 기존에 LLVM에 반영되어 있지 않은 peephole 최적화를 대수적으로 구현하고
2. 1을 증명하고, 3. 적용 및 검증을 하는 방식으로 기존에는 최적화에 대한 연구가 이루어졌다.

 

최근 regehr 가 연구한 논문들을 살펴보면, 특이할만한 사항이 있는데 regehr 가 기존에 alive - alive2 등 SMT SAT solver 관련된 검증 관련된 연구를 했었고 또한 이를 통해 peephole 최적화를 검증한다는 것이다.

 

여기서 파생되는 발상이 많다. 예를 들어,
-. 범용적으로는 적용할 수 없는 최적화지만? 여기서는 되나? 라는 최적화적용?

-. 빠른 최적화 프로토타이핑 (-__??)및 테스트 & 검증 프레임워크 로의 활용

-. Brute-forcing 방식의 최적화 개발. 이것은 또한 AI 를 통해서 가능할 것

 

뭐랄까. 그냥 그렇다.

 

한편 보안 측면에서 보자면, SUPEROPTIMIZATION 이란 결국 기존 LLVM PASS 와 비교해 봤을 때 빠르고 검증 가능한 코드 최적화이고, 이와 정확히 반대방향인 난독화에서는 SUPER-OBFUSCATION 이 가능해진다는 뜻도 된다.

 

매우 재미있고 흥미로운 주제이다.