SSA
SSA (англ. Static single assignment form) — промежуточное представление, используемое компиляторами, в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной. В SSA-представлении DU-цепи (англ. def-use) заданы явно и содержат единственный элемент.
SSA-представление было разработано исследователями IBM Роном Ситроном (Ron Cytron), Жаном Феррантом (Jeanne Ferrante), Барри Розеном (Barry Rosen), Марком Уэгменом (англ. Mark N. Wegman) и Кеном Задеком (Ken Zadeck) в 1980-е годы.
В компиляторах функциональных языков программирования, таких как Scheme, ML и Haskell, вместо SSA обычно используется CPS-представление (англ. Continuation-passing style). Формально эти представления эквивалентны, поэтому оптимизации и трансформации, сформулированные в одном из представлений, могут быть применены и для другого.
Преимущества SSA
Для кода в SSA-форме проще и эффективнее проводить многие виды компиляторной оптимизации. Например, в следующем коде:
y := 1 y := 2 x := y
для человека очевидно, что первое присваивание не нужно, так как значение y, использованное в третьей строчке, соответствует второму присваиванию. Однако для того, чтобы выяснить это, компилятору пришлось бы прибегнуть к анализу достигающих определений. Но с использованием SSA-представления это становится гораздо проще:
y1 := 1 y2 := 2 x1 := y2
SSA делает возможными или существенно упрощает следующие оптимизационные алгоритмы:
- свёртка констант
- удаление мёртвого кода
- нумерация глобальных значений
- частичное устранение избыточности
- снижение стоимости операций
- распределение регистров
Перевод в SSA
Перевод обычного программного кода в SSA-представление достигается путём замены в каждой операции присваивания переменной из левой части на новую переменную. Для каждого использования значения переменной исходное имя заменяется на имя «версии», соответствующей нужному базовому блоку. Рассмотрим следующий граф потока управления:
В соответствии с определением SSA создадим вместо переменной x две новые переменные x1 и x2. Каждой из них значение будет присвоено ровно один раз. Аналогичным образом заменим остальные переменные, после чего получим следующий граф:
Пока остаётся неясным, какое значение y будет использоваться в нижнем блоке. Там имя y может означать как y1, так и y2. Для того, чтобы разрешить неоднозначности такого рода, в SSA введена специальная Φ-функция. Эта функция создаёт новую версию переменной y, которой будет присвоено значение либо из y1, либо из y2, в зависимости от того, из какой ветви перешло управление.
При этом использовать Φ-функцию для переменной x не нужно, так как лишь одна версия x (а именно, x2) «достигает» последнего блока.
Φ-функция в действительности не реализована; она представляет собой лишь указание компилятору хранить все переменные, перечисленные в списке её аргументов, в одном и том же месте в памяти (или регистре).
Более общий вопрос состоит в том, можно ли по заданному графу потока управления понять, где и для каких переменных в SSA-представление нужно вставить Φ-функции? Ответ на этот вопрос можно получить с помощью доминаторов.
Компиляторы, использующие SSA
- Oberon-2
- LLVM
- Open64
- GCC
- Jikes RVM[англ.]
- HotSpot
- jackcc
- Portable.NET
- libFirm
- COINS compiler
- V8
- PyPy
- Dalvik virtual machine
- MLton
- LuaJIT
- Go [1]
- Excelsior JET
Литература
- Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
- Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: Вильямс, 2002. — С. 256. — ISBN 0-13-727835-7.
- R. Allen, K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, 2002.
- A. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998.
- S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.
Примечания
- ↑ New SSA Backend for the Go Compiler. Дата обращения: 16 августа 2016. Архивировано 2 октября 2016 года.
Ссылки
- Steven Bosscher и Diego Novillo. GCC gets a new Optimizer Framework. Статья об использовании SSA-представления в GCC.
- The SSA Bibliography. Каталог исследовательских статей по SSA-представлению.
- F. K. Zadeck. «The Development of Static Single Assignment Form», рассказ о корнях SSA-представления в декабре 2007.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.