В статье рассматриваются основные принципы применения конечных автоматов для автоматизированного поиска возможных вариантов оптимизации программного кода.
Ключевые слова: оптимизация программного кода, конечный автомат, качество программ.
На сегодняшний день становится все более актуальным вопрос разработки качественного программного обеспечения. Создаваемый программный код должен быть не только синтаксически правильным, при разработке также следует заботиться о его оптимальности, так как наличие не оптимизированных участков кода в последствии может сказаться на различных характеристиках качества программного обеспечения, таких как эффективность, надежность и прочих.
Под оптимизацией программы понимается изменение корректного кода, направленное на повышение его эффективности. В частности, более эффективного программного кода можно добиться путем уменьшения количества выполняемых операций на основе математических и логических преобразований, например таких, как: удаление недостижимого кода; удаление бесполезных операций и избыточных вычислений, просчет заранее известных значений, смена порядка вычислений, применение арифметических преобразований, размыкание, слияние или развертывание циклов, изменение порядка вложенности циклов, снижение ценности операций.
Автоматический поиск и модификация частей кода, подлежащих оптимизации, возможны посредством инспектирования программного кода. Для проведения синтаксического и лексического анализа программ применяются конечные автоматы. В нашем случае конечные автоматы предполагается использовать для идентификации слабых мест по заранее определенным формализованным шаблонам. Исходными данными при этом должен служить синтаксически правильный программный код.
В качестве примера рассмотрим конечный автомат, позволяющий выявить случаи избыточно занимаемой памяти переменными, имеющими область видимости, превышающую минимально необходимую. Описание будем вести применительно к языку программирования С++.
В качестве входной цепочки символов используется массив, в который помещается синтаксически правильный программный код на языке С++. Конечный автомат имеет четыре состояния (см. рис. 1).
Рис. 1. Состояния конечного автомата: S — состояния автомата, t — входной текстовый символ, tb — символы '\r', '\n', '\t', ' ', e — входные символы
Начальным состоянием конечного автомата является состояние S0, в котором происходит считывание входных символов и запись в выходной массив в случае, если считано название типа, переменной или функции.
В состоянии S1 происходит считывание имени переменной. В данное состояние программа переходит из состояния S0 в случае предшествующего считывания имени типа данных. В состоянии S1 программа должна определить количество объявленных переменных и записать в массив переменных их имена.
В состояние S2 конечный автомат переходит из состояния S0, если после текстовых символов считан символ, отличный от символов табуляции. В этом случае если входная строка не пуста, значит, встретилось использование имеющейся переменной, и необходимо добавить соответствующую информацию в массивы, считать текущий текстовый символ и перейти в состояние S0 для продолжения считывания.
В состояние S3 конечный автомат переходит из состояния S0, если необходимо обработать объявление функции. Как только встречается символ «{», программа запоминает индекс этого символа во входящей строке как начало тела функции. Затем автомат копирует из выходной строки имя функции в массив functions и переходит в состояние S0. Сохранить индекс начата тела функции необходимо для того, чтобы локализовать область видимости переменных.
На выходе данный конечный автомат предоставляет информацию о наличии всех объявленных в программном коде переменных, их типах, а также о местах их объявления и использования. Полученная информация позволит сделать вывод о рациональности локализации переменных. Отметим, что здесь конечный автомат описан в упрощении, что использование переменных рассматривается на уровне функций, более мелкие блоки программы, например, циклы и условные операторы, не учитываются. Однако, выделение минимальных блоков программы, в которых происходит использование объявленных переменных, реализуется аналогично [2].
Описанный конечный автомат позволит произвести оптимизацию программного кода относительно затрат компьютерной памяти. Не используемые в программе переменные можно будет удалить, а используемым — максимально сузить область видимости.
Аналогично могут быть построены конечные автоматы для других возможных модификаций программ с целью оптимизации кода. Например, конечный автомат, реализующий поиск недостижимого кода должен отыскивать в программе условный оператор, оператор выбора вариант, циклы и операторы безусловной передачи управления и переходить в соответствующие состояния для анализа возможных исходов. Для применения арифметических преобразований, влекущих уменьшение количество производимых операций, конечный автомат должен отыскивать определенные выражения, например A*B+B*C, которое необходимо преобразовать к виду B*(A+C).
Таким образом, каждой возможной модификации кода с целью его оптимизации должен быть сопоставлен формализованный шаблон, по которому реализован конечный автомат поиска слабых мест в программе. Последовательный запуск таких конечных автоматов приводит к определению возможных вариантов улучшения кода.
Посредством создания конечных автоматов решается вопрос автоматизированного поиска в программном коде отрезков программы, подлежащих оптимизации. Конечные автоматы проводят инспектирование программного кода по заранее определенным шаблонам. Оптимизация синтаксически правильного кода способствует повышению уровня качества программного обеспечения.
Литература:
1. Коваль В. В. Современные методы трансформации программ // Компьютерное моделирование. Вычислительные технологии. Ростов-на-Дону, 2003. С. 41–58.
2. Степович-Цветкова Г. С. Автоматизированное управление качеством программ на основе метода инспектирования кода // Электронные информационные системы. 2017. № 4 (15). С. 57–68.
3. Степович-Цветкова Г. С. Модель оценки качества компьютерных программ // Прикладные задачи математики: материалы XXV международной научно-технической конференции. Севастополь, 2017. С. 213–215.
4. Штейнберг Б. Я., Штейнберг О. Б. Преобразования программ— фундаментальная основа создания оптимизирующих распараллеливающих компиляторов // Программные системы: теория и приложения. 2021. Т. 12, № 1(48). С. 21–113.
