Показать меню

Нумерация значений

15.12.2020
11

Нумерация значений (англ. Value Numbering) — один из видов анализа потока данных, применяемый оптимизирующим компилятором с целью обнаружения избыточных вычислений в коде (промежуточном представлении) программы. Результатами анализа могут воспользоваться оптимизации: распространение копий, удаление частичных избыточностей, удаление общих подвыражений, оптимизация условий (англ. If Optimization), inline-подстановка. Анализ разбивает множество всех рассматриваемых операций, вырабатывающих какой-либо результат (число или предикат), на подмножества операций, в каждом из которых все операции вырабатывают одинаковый результат не зависимо от ввода. Такие подмножества (а так же, иногда, номера этих подмножеств) называют классами конгруэнтности или классами эквивалентности. Классы конгруэнтности пронумерованы, номер класса конгруэнтности называют номером значения. Таким образом, задачу нумерации значений можно сформулировать следующим образом: присвоить уникальный номер каждому значению, вырабатываемому внутри рассматриваемого участка программы. Для осуществления нумерации значений может потребоваться построенный Def-Use-граф или SSA-форма. Нумерация значений может быть локальной (в пределах одного базового блока), глобальной (в пределах CFG-графа одной процедуры) и межпроцедурной.

Примеры

Алгоритмы

Применение

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

Удаление общих подвыражений

Оптимизация условий

Inline-подстановка

Inlining — оптимизация, выполняющая подстановку тела функции вместо операции её вызова (CALL). Целью преобразование является уменьшение количества передач управления, то есть уменьшение количества операций CALL и RETURN, а также более эффективная работа оптимизаций, анализирующих только одну единицу трансляции (а таких большинство). Inline нельзя применять ко всем функциям в программе. Например, если подставить вместо вызова слишком большую функцию, то размер кода может существенно возрасти. В процессе выполнения оптимизации важно найти компромисс между увеличением кода и скоростью его исполнения. Межпроцедурная нумерация значений позволяет уточнить этот анализ, так как, даже если размер подставляемой функции слишком велик, в ней могут содержаться избыточные вычисления, которые, после подстановки и дальнейшего удаления избыточностей, исчезнут. Таким образом, межпроцедурная нумерация значений позволяет нам оперировать не размером подставляемой функции, а увеличением размера кода после подстановки этой функции. Частным случаем этой оптимизации является частичный inline, при котором подставляется только часть вызываемой функции, например, содержащая самые часто выполняемые пути.

Еще по этой теме:
Операция (психология)
19:49, 13 декабрь
Операция (психология)
Операция (англ. oрeration) - составляющая деятельности человека, соотносимая с задачей (объективно-предметными условиями достижения целей). А. Н. Леонтьев считал операцию способом осуществления
Теория квантовой сложности
14:36, 13 декабрь
Теория квантовой сложности
Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а
stdio.h
11:18, 12 декабрь
stdio.h
stdio.h (от англ. standard input/output header — стандартный заголовочный файл ввода-вывода) заголовочный файл стандартной библиотеки языка Си, содержащий определения макросов, константы и объявления
Класс (математика)
06:30, 06 декабрь
Класс (математика)
Класс — термин, употребляемый в теории множеств для обозначения произвольных совокупностей множеств, обладающих каким-либо определённым свойством или признаком. Более строгое определение класса
Сигнальное созвездие
15:55, 05 декабрь
Сигнальное созвездие
Сигнальное созвездие (англ. constellation diagram) — представление всевозможных значений комплексной амплитуды манипулированных радиосигналов на комплексной плоскости. Описание Всевозможные
Методы построения педотрансферных функций
14:34, 13 март
Методы построения педотрансферных функций
Статистический регрессионный анализ был традиционным инструментом развития ПТФ в течение многих десятилетий. Преимущество регрессионной техники - возможность получить строгие статистические оценки
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent