Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

17.06.2017

Google
WWW CITForum.ru
С Новым годом!
2005 г.

Усовершенствованный алгоритм распространения констант с использованием GSA-представления

Довгалюк П.М.

Труды Института Системного Программирования РАН, 2004 г.

В данной статье представлены усовершенствования метода распространения констант, использующего GSA-представление (Gated Single Assignment), позволяющие алгоритму находить большее количество констант, чем исходный алгоритм.

Введение

Распространение констант – хорошо известная проблема глобального анализа потока данных. Цель распространения констант состоит в обнаружении величин, которые являются постоянными при любом возможном пути выполнения программы, и в распространении этих величин так далеко по тексту программы, как только это возможно. Выражения, чьи операнды являются константами, могут быть вычислены на этапе компиляции. Поэтому использование алгоритмов распространения констант позволяет компилятору выдавать более компактный и быстрый код.

Хотя в общем случае проблема распространения констант является неразрешимой, существует множество проявлений этой проблемы, для которых существуют эффективные алгоритмы.

Технологии распространения констант позволяют решить следующие задачи:

  • выражения, вычисляемые на этапе компиляции не нужно вычислять в процессе выполнения программы
  • код, который никогда не выполняется, может быть удален. Недостижимый код может появляться в тех случаях, когда значение предиката в условном выражении неизменно и известно на этапе компиляции.
  • увеличение эффективности встраивания процедур.
    Распространение констант совместно со встраиванием процедур (когда многие параметры процедур являются константами) позволяет избежать разрастания кода, которое часто является результатом встраивания процедур в места из вызовов

Алгоритм распространения констант, использующий GSA-представление

Алгоритм распространения констант, описанный в [8] использует SSA-представление (Static Single Assignment) программы. В SSA-форму программа трансформируется таким образом, что только одно присваивание может достигнуть точки использования. Так как программы имеют ветвления и точки объединения нескольких путей, то в точках объединения необходимо добавить специальную форму присваивания, названную φ-функцией. φ-функция имеет форму V ← φ(R, S, …), где V, R, S, … – переменные. Количество операндов такой функции равняется количеству предшественников данного узла. Эти предшественники перечисляются в некотором определенном порядке и j-й операнд φ-функции ассоциируется с j‑м предшественником узла. Если путь выполнения программы лежит через j‑го предка узла, то переменная V получает значение, связанное с j‑м аргументом. Каждое исполнение φ-функции использует только один из аргументов, но который именно – зависит от того, из которого узла получил управление данный узел.

В работе [8] алгоритмы распространения констант разделены на те, которые находят простые и условные константы. Алгоритм Sparse Conditional Constant Propagation находит все простые, а также некоторые условные константы. Время работы такого алгоритма пропорционально размеру SSA-графа и каждое SSA-ребро обрабатывается максимум два раза.

Когда необходимо классифицировать переменную в точке слияния, мы используем функцию meet для аргументов ее φ-функции. Но если в процессе своего выполнения программа всегда идет только по одной ветке было бы лучше использовать то значение переменной, которое порождается именно в ней. В методе, описанном в предыдущем разделе, если значение предиката будет постоянным, то выполняемое ребро будет добавлено к рабочему списку. Поэтому в точке слияния выражения будут вычисляться с использованием информации о входящих выполняемых ребрах, что может приводить к неоднократному вычислению одних и тех же выражений.

В методе, использующем GSA, если символ использует значение из точки слияния, то вычисляется значение предиката и определяется путь из которого берется значение. При использовании φ-функции мы не можем определить по какому пути шло выполнение программы. Но если снабдить φ-функцию предикатом, то, если его значение является константой, можно выбрать нужный аргумент φ-функции, а если нет, то самое лучшее, что можно получить с помощью данного метода – это взять функцию meet от φ-аргументов.

Чтобы выполнить данную задачу необходимо расширить SSA-представление до GSA (gated single assignment), введенное в работе [3], которое позволяет вычислять условные выражения, базирующие на предикатах. В данном представлении φ-функции заменяются на μ- и γ-функции. Большая часть φ-функций, расположенных в заголовках циклов переименовываются в μ-функции, тогда как остальные – преобразуются в γ-функции. γ-функция имеет вид: v = γ(P, v1, v2), что означает, что v принимает значение v1, если P=true и v2, если P=false. В такой форме γ-функция представляет собой конструкцию if-then-else, но она может быть расширена для работы с более сложными условными конструкциями. Алгоритм для преобразования φ-функций в μ- и γ-функции представлен в работе [6].

В данном алгоритме используется представление программы в виде базовых блоков, состоящих из кортежей. Базовые блоки и кортежи внутри них связаны между собой и вместе образуют граф потока данных. Кортежи имеют следующие атрибуты: op, left, right, ssa_link, lattice, где op – код операции, left и right – два операнда. ssa_link – связь, порождаемая алгоритмом преобразования программы в SSA-форму. Поля left, right, ssa_link представляют собой указатели на соответствующие кортежи. Каждая операция (кортеж) также имеет ассоциированное значение – lattice, принадлежащее множеству значений из решетки и представляющее собой результат выполнения операции, который может быть получен на этапе компиляции.

Исходный алгоритм

∀ t ∈ tuples
  lattice(t) = T
  unvisited(t) = true

Visit all basic blocks B in the program Visit all tuples t within B if unvisited(t) then propagate(t)
propagate (tuple t) unvisited(t) = false if ssa_link(t) ≠ 0 then if unvisited(ssa_link(t)) then propagate(ssa_link(t)) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if unvisited(left(t)) then propagate(left(t)) if unvisited(right(t)) then propagate(right(t)) case on type (t) constant C: lattice(t) = C arithmetic operation: if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ⊥ endif store: lattice(t) = lattice(RHS) φ-function: lattice(t) = П of φ-arguments of t γ-function: if lattice(predicate) = C then lattice(t) = lattice value of γ-argument corresponding to C else lattice(t) = П of all γ-arguments of t endif μ-function: lattice(t) = ⊥ η-function: lattice(t) = lattice(η-argument) default: lattice(t) = ⊥ end case end propagate

Недостатки и предлагаемые изменения

В работе [7] показано, что арифметические и логические выражения, включающие γ-функции, можно преобразовывать в несколько вложенных γ‑функций и арифметических выражений, что позволяет получать константные выражения даже в тех случаях, когда аргументы исходного арифметического или логического выражения не являются константами. Это видно по следующему примеру:

if P then
  a1 = 2
  b1 = 1
else
  a2 = 4
  b2 = 2
endif
a3 = γ(P, a1, a2)
b3 = γ(P, b2, b3)
if a3 > b3 then
  ...
endif

В данном случае переменные a3 и b3 будут всегда равны независимо от значения предиката P. Алгоритм, предложенный в [5] не сможет определить отношение значений переменных в данной ситуации.

Предлагаемые изменения алгоритма привели бы предикат a3 > b3 к виду: γ(P, a1 > b1, a2 > b2) = γ(P, true, true) = true.

Предлагаемые изменения алгоритма касаются обработки арифметических и логических выражений и состоят в следующем:

E1, E2 – аргументы арифметического (логического) оператора

  1. E1 и E2 не содержат γ-функций, либо обе содержат γ-функции с разными предикатами. Используется обычное правило для вычисления арифметических и логических выражений.
  2. Один из аргументов (E1 для определенности) содержит γ-функцию. Выполняется следующее преобразование:
    γ(P, V1, V2) op E2 = γ(P, V1 op E2, V2 op E2)
  3. E1 и E2 содержат в себе φ-функции с одинаковыми предикатами. Выполняется следующее преобразование:
    γ(P, V1, V2) op γ(P, V3, V4) = γ(P, V1 op V3, V2 op V4)

Новый алгоритм

∀ t ∈ tuples
  lattice(t) = T
  unvisited(t) = true

Visit all basic blocks B in the program Visit all tuples t within B propagate(t)
propagate (tuple t) if not unvisited(t) return unvisited(t) = false label restart: if ssa_link(t) ≠ 0 then ssa_link(t) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if type(t) ≠ arithmetic operation propagate(left(t)) propagate(right(t)) endif case on type (t) constant C: lattice(t) = C arithmetic or logic operation: if type(left(t)) = γ-function or (type(right(t)) = γ-function then if type(left(t)) = γ-function and (type(right(t)) = γ-function or type(ssa_link(right(t))) = γ-function) and (predicate(left(t)) = predicate(right(t)) or type(ssa_link(left(t))) = γ-function) then join_common_predicate(t) goto restart else join_gamma_with_operand(t) goto restart endif else propagate(left(t)) propagate(right(t)) endif if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ⊥ endif store: lattice(t) = lattice(RHS) φ-function: lattice(t) = lattice(left(t))П lattice(right(t)) γ-function: propagate(predicate(t)) if lattice(predicate(t)) = C then lattice(t) = lattice value of γ-argument corresponding to C else lattice(t) = lattice(left(t)) П lattice(right(t)) endif μ-function: lattice(t) = ⊥ η-function: lattice(t) = lattice η-argument) default: lattice(t) = ⊥ end case end propagate

Функция join_common_predicate – объединяет две γ-функции с одинаковыми предикатами в одну

join_common_predicate (tuple t)
   tuple new_t = new γ-function
   predicate(new_t) = predicate(left(t))

left(new_t) = new operation node, same as t ssa_link(left(new_t)) = 0 unvisited(left(new_t)) = true lattice(left(new_t)) = T left(left(new_t)) = left(left(t)) right(left(new_t)) = right(left(t))
right(new_t) = new operation node, same as t ssa_link(right(new_t)) = 0 unvisited(right(new_t)) = true lattice(right(new_t)) = T left(right(new_t)) = left(right(t)) right(right(new_t)) = right(right(t))
t = new_t ssa_link(t) = 0 lattice(t) = T end join_common_predicate

Функция join_gamma_with_operand – объединяет γ-функцию и операнд, который не является γ-функцией

join_gamma_with_operand (tuple t)
   tuple g, op
   tuple g_left = new operation node, same as t
   tuple g_right = new operation node, same as t
   if type(left(t)) = γ-function then
      g = left(t)
      op = right(t)
      left(g_left) = left(g)
      left(g_right) = right(g)
      right(g_left) = op
      right(g_right) = op
   else
      op = left(t)
      g = right(t)
      left(g_left) = op
      left(g_right) = op
      right(g_left) = left(g)
      right(g_right) = right(g)
   endif
   left(g) = g_left
   right(g) = g_right
   t = g

unvisited(g_left) = true lattice(g_left) = T ssa_link(g_left) = 0
unvisited(g_right) = true lattice(g_right) = T ssa_link(g_right) = 0 end join_gamma_with_operand

Время работы алгоритма

Т.к. в оригинальном алгоритме флаг unvisited для каждого узла не может измениться более одного раза, то это означает, что алгоритм посещает каждый узел единожды, поэтому время его работы может быть оценено как O(N), где N – количество узлов.

Модифицированный алгоритм, как и исходный, посещает каждый узел представления программы единожды. В предельном (невозможном на практике) случае, однако, тип каждого узла может быть преобразован, поэтому время, необходимое для обработки одного узла может увеличиться. Тем не менее, время работы алгоритма также представляет собой величину порядка O(N).

Таким образом, улучшенный алгоритм обладает большими возможностями по обнаружению констант, чем исходный лишь незначительно увеличивая время его работы (при том, что асимптотическая оценка времени работы остается той же).

Для сравнения предикатов можно использовать сравнения указателей на них (т.е. предикаты эквивалентны, если они указывают на один и тот же оператор ветвления) или алгоритм классификации выражений, описанный в [2]. Первый вариант позволяет выполнить сравнения без значительных затрат времени. Второй – позволяет найти одинаковые предикаты, которые не принадлежат одному оператору ветвления, но требует дополнительных затрат времени на классификацию предикатов.

Список использованной литературы

  1. А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001
  2. B. Alpern, M. N. Wegman, F. K. Zadeck. Detecting equality of variables in programs, 1988
  3. R. A. Balance, A. B. Maccabe, and K. J. Ottenstein. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages. In Proc. ACM SIGPLAN’90 Conf. on Programming Language Design and Implementation, June 1990
  4. S. Muchnick. Advanced compiler design and implementation, 1997
  5. E. Stoltz, M. Wolfe, M. P. Gerlek. Constant propagation: a fresh, demand-driven look, 1994
  6. E. Stoltz, M. Wolfe, and M. P. Gerlek. Demand-driven constant propagation. Technical Report 93-023, Oregon Graduate Institute, 1993
  7. P. Tu, D. Padua. Gated SSA-based demand-driven symbolic analysis for parallelizing compilers. ACM International Conference on Supercomputing, 1995
  8. M. N. Wegman, F. K. Zadeck. Constant propagation with conditional branches. ACM Trans. on Programming Languages and Systems, 13(2):181-210, July 1991

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 This Web server launched on February 24, 1997
    Copyright © 1997-2017 CIT, © 2001-2017 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...