Анализ определенного назначения

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

Мотивация

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

Существует два распространенных способа решения этой проблемы. Один из них — гарантировать, что все местоположения записаны до того, как они будут прочитаны. Теорема Райса устанавливает, что эта проблема не может быть решена в общем случае для всех программ; однако можно создать консервативный (неточный) анализ, который будет принимать только программы, удовлетворяющие этому ограничению, отклоняя некоторые правильные программы, и анализ определенного присваивания является таким анализом. Спецификации языков программирования Java ^[1] и C# ^[2] требуют, чтобы компилятор сообщал об ошибке времени компиляции, если анализ не удается. Оба языка требуют определенной формы анализа, которая подробно изложена. В Java этот анализ был формализован Штарком и др. ^[3] , и некоторые правильные программы отклоняются и должны быть изменены для введения явных ненужных присваиваний. В C# этот анализ был формализован Фруджей и является точным и обоснованным в том смысле, что все переменные, назначенные вдоль всех путей потока управления, будут считаться определенно назначенными. ^[4] Язык Cyclone также требует, чтобы программы проходили определенный анализ присваивания, но только для переменных с типами указателей, чтобы облегчить портирование программ на языке C. ^[5]

Второй способ решения проблемы — автоматически инициализировать все местоположения некоторым фиксированным, предсказуемым значением в точке, в которой они определены, но это вводит новые назначения, которые могут помешать производительности. В этом случае анализ определенного назначения позволяет оптимизировать компилятор , где избыточные назначения — назначения, за которыми следуют только другие назначения без возможных промежуточных чтений — могут быть устранены. В этом случае никакие программы не отклоняются, но программы, для которых анализ не может распознать определенное назначение, могут содержать избыточную инициализацию. Common Language Infrastructure опирается на этот подход. ^[6]

Терминология

Можно сказать, что переменная или местоположение находится в одном из трех состояний в любой момент программы:

• Определенно назначено : Переменная определенно назначена.
• Определенно не присвоено : Переменная, как известно, определенно не присвоена.
• Неизвестно : переменная может быть назначена или не назначена; анализ недостаточно точен, чтобы определить, что именно.

Анализ

Нижеследующее основано на формализации Фруджа внутрипроцедурного (один метод) анализа определенного присваивания C#, который отвечает за обеспечение того, чтобы все локальные переменные были назначены до их использования. ^[4] Он одновременно выполняет анализ определенного присваивания и постоянное распространение булевых значений. Мы определяем пять статических функций:

Мы предоставляем уравнения потока данных, которые определяют значения этих функций в различных выражениях и операторах, в терминах значений функций в их синтаксических подвыражениях. Предположим на мгновение, что нет goto , break , continue , return или операторов обработки исключений . Ниже приведены несколько примеров этих уравнений:

• Любое выражение или оператор e , который не влияет на набор определенно назначенных переменных: после ( e ) = до ( e )
• Пусть e будет выражением присваивания loc = v . Тогда before ( v ) = before ( e ), а after ( e ) = after ( v ) U {loc}.
• Пусть e будет выражением true . Тогда true ( e ) = before ( e ) и false ( e ) = vars ( e ). Другими словами, если e оценивается как false , все переменные ( пусто ) определенно назначены, потому что e не оценивается как false.
• Поскольку аргументы метода оцениваются слева направо, before( arg _{i  + 1} ) = after( arg _i ). После завершения метода параметры out определенно назначаются.
• Пусть s будет условным оператором if ( e ) s ₁ else s ₂ . Тогда before ( e ) = before ( s ), before (s ₁ ) = true ( e ), before ( s ₂ ) = false ( e ), и after( s ) = after( s ₁ ) пересекаются after( s ₂ ).
• Пусть s будет оператором цикла while while ( e ) s ₁ . Тогда before( e ) = before( s ), before( s ₁ ) = true( e ) и after( s ) = false( e ).
• И так далее.

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

Алгоритм усложняется введением переходов потока управления, таких как goto , break , continue , return и обработка исключений. Любой оператор, который может быть целью одного из этих переходов, должен пересекать свой предыдущий набор с набором определенно назначенных переменных в источнике перехода. Когда они вводятся, результирующий поток данных может иметь несколько фиксированных точек, как в этом примере:

 целое число i = 1 ;    Л : перейти к L ; 

Поскольку метка L может быть достигнута из двух мест, уравнение потока управления для goto диктует, что before (2) = after (1) пересекаются before (3). Но before (3) = before (2), поэтому before (2) = after (1) пересекаются before (2). Это имеет две фиксированные точки для before (2), {i} и пустое множество. Однако можно показать, что из-за монотонной формы уравнений потока данных существует уникальная максимальная фиксированная точка (фиксированная точка наибольшего размера), которая предоставляет максимально возможную информацию о определенно назначенных переменных. Такая максимальная (или максимальная) фиксированная точка может быть вычислена стандартными методами; см. анализ потока данных .

Еще одной проблемой является то, что переход потока управления может сделать некоторые потоки управления невозможными; например, в этом фрагменте кода переменная i определенно назначается до ее использования:

 целое число i ;  если ( j < 0 ) вернуть ; иначе i = j ;         печать ( я );

Уравнение потока данных для if говорит, что after (2) = after( return ) пересекаются after( i = j ). Чтобы это работало правильно, мы определяем after ( e ) = vars ( e ) для всех переходов потока управления; это бессмысленно верно в том же смысле, в котором верно уравнение false ( true ) = vars ( e ), потому что управление не может достичь точки сразу после перехода потока управления.

Ссылки

1. J. Gosling; B. Joy; G. Steele; G. Bracha. «Спецификация языка Java, 3-е издание». стр. Глава 16 (стр. 527–552) . Получено 2 декабря 2008 г.
2. "Стандарт ECMA-334, Спецификация языка C#". ECMA International . стр. Раздел 12.3 (стр.122–133) . Получено 2 декабря 2008 г.
3. Старк, Роберт Ф.; Э. Боргер; Иоахим Шмид (2001). Java и виртуальная машина Java: определение, проверка, валидация . Секаукус, Нью-Джерси, США: Springer-Verlag New York, Inc., стр. Раздел 8.3. ISBN 3-540-42088-6.
4. Fruja, Nicu G. (октябрь 2004 г.). «Корректность анализа определенных присваиваний в C#». Journal of Object Technology . 3 (9): 29–52. CiteSeerX 10.1.1.165.6696 . doi :10.5381/jot.2004.3.9.a2 . Получено 2008-12-02 . На самом деле мы доказываем больше, чем корректность: мы показываем, что решение анализа является идеальным решением (а не только безопасным приближением). 
5. "Cyclone: ​​Definite Assignment". Руководство пользователя Cyclone . Получено 16 декабря 2008 г.
6. "Стандарт ECMA-335, Common Language Infrastructure (CLI)". ECMA International . стр. Раздел 1.8.1.1 (Раздел III, стр. 19) . Получено 2 декабря 2008 г. .