Skip to content

Latest commit

 

History

History
31 lines (24 loc) · 3.59 KB

sea_of_nodes.md

File metadata and controls

31 lines (24 loc) · 3.59 KB
Raw

Sea of Nodes (SoN)

SoN является графовым IR. Для понимания идей, лежащих в основе SoN, нужно иметь представление об SSA [1] и PDG [2].

IR SoN предложено Клиффом Кликом. Для начального введения полезно посмотреть его работы [3], [4] и [5]. Основные результаты имеются в диссертации Клика [6]. Результаты диссертации обсуждаются здесь.

SoN используется в:

  • Java HotSpot (первый коммерческий компилятор с использованием SoN, описан в [7])
  • V8 TurboFan
  • Graal [8]
  • Scala LMS [9]
  • LibFirm [13]

Среди академических работ следует отметить анализ формальной семантики SoN [10], IR Thorin [11], использование SoN на этапе порождения кода [12].

Источники

  1. Braun M. et al. Simple and efficient construction of static single assignment form //International Conference on Compiler Construction. – Springer, Berlin, Heidelberg, 2013. – С. 102-122.
  2. Ferrante J., Ottenstein K. J., Warren J. D. The program dependence graph and its use in optimization //ACM Transactions on Programming Languages and Systems (TOPLAS). – 1987. – Т. 9. – №. 3. – С. 319-349.
  3. Click C. From quads to graphs: An intermediate representation's journey. – Technical Report CRPC-TR93366-S, Center for Resesearch on Parallel Computation, Rice University, 1993.
  4. Click C., Paleczny M. A simple graph-based intermediate representation //ACM Sigplan Notices. – 1995. – Т. 30. – №. 3. – С. 35-49.
  5. Click C. Global code motion/global value numbering //ACM Sigplan Notices. – 1995. – Т. 30. – №. 6. – С. 246-257.
  6. Click C., Cooper K. D. Combining analyses, combining optimizations //ACM Transactions on Programming Languages and Systems (TOPLAS). – 1995. – Т. 17. – №. 2. – С. 181-196.
  7. Paleczny M., Vick C., Click C. The java hotspot TM server compiler //Proceedings of the 2001 Symposium on Java TM Virtual Machine Research and Technology Symposium. – 2001. – Т. 1. – №. S 1.
  8. Duboscq G. et al. An intermediate representation for speculative optimizations in a dynamic compiler //Proceedings of the 7th ACM workshop on Virtual machines and intermediate languages. – ACM, 2013. – С. 1-10.
  9. Rompf T., Odersky M. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs //Communications of the ACM. – 2012. – Т. 55. – №. 6. – С. 121-130.
  10. Demange D., Fernández de Retana Y., Pichardie D. Semantic reasoning about the sea of nodes //Proceedings of the 27th International Conference on Compiler Construction. – ACM, 2018. – С. 163-173.
  11. Leißa R., Köster M., Hack S. A graph-based higher-order intermediate representation //Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization. – IEEE Computer Society, 2015. – С. 202-212.
  12. Hjort Blindell G. Universal Instruction Selection : дис. – KTH Royal Institute of Technology, 2018.
  13. Braun M., Buchwald S., Zwinkau A. Firm-a graph-based intermediate representation. – KIT, Fakultät für Informatik, 2011.