Межпроцедурный анализ указателей. Дроздов (1157404), страница 6
Текст из файла (страница 6)
Тогда чтение этих формальных именприведет к созданию по ним множества РП и соответствующих нелокальных блоков,которые, при необходимости, попадут в структуру присваиваний ЧТФ. И в случае,когда вход в рекурсивный цикл будет осуществлен через новую процедуру, пересчетЧТФ не будет осуществляться лишь на том основании, что через данные параметрыпроцедуры не приходила информация извне рекурсивного цикла.
Заметим, что видомфиктивных присваиваний можно также регулировать соотношение между скоростью иточностью анализа: если все присваивания имеют одну и ту же правую часть, то всемсоздаваемым РП будут сопоставлен один и тот же нелокальный блок; это снижаетточность, но повышается вероятность переприменения ЧТФ в новых контекстах.Ситуацией, схожей с уже описанной, является следующая. Внутри рекурсивного циклапроисходит чтение многих глобальных имен, но запись в них некоторых адресовосуществляется после выхода из рекурсивного цикла.
Если таким образоминициализируется большое количество глобальных имен, то каждый вызоврекурсивного цикла приводит к необходимости пересчета. Для того, чтобы этогоизбежать, в вызывающем контексте создаются фиктивные присваивания, которыепозволят анализу создать необходимые РП и учесть соответствующие нелокальныеимена в структурах присваиваний. Это в большинстве случаев позволит непересчитывать ЧТФ цикла.
Опять же, видом фиктивных присваиваний можнорегулировать соотношение точность-скорость, как это было описано выше.Возможна следующая редкая, но очень неприятная ситуация. Процедура f(func*) –голова рекурсивного цикла, в качестве параметра получает адрес некоторой процедурыдля вызова её по косвенности внутри цикла. Если вызов рекурсивного цикла черезпроцедуру f осуществляется часто, причём с разными значениями параметра, токаждый раз ЧТФ цикла придется пересчитывать. Возможен следующий выход: допроведения анализа, во время предварительного прохода по представлению (который итак осуществляется для служебных нужд) для каждой процедуры собираетсяинформация о значениях её параметров типа «ссылка на процедуру», в том случае,когда в качестве параметра явно фигурирует имя функции.
Если в процессе анализа,данная процедура оказалась головой рекурсивного цикла, то при первой же обработке вкачестве значения параметра процедуры рассматривается не та единственная функция,которая была подана в качестве аргумент данного вызова, а все набранные во времяпредобработки процедуры. При таком походе нет необходимости пересчитывать ЧТФцикла при остальных вызовах f с новыми значениями параметра.Наследование результатов анализаПосле того, как алгоритм завершил последнюю итерацию по главной процедурепрограммы, анализ закончен. Его результатами являются множества ЧТФ для каждойпроцедуры, причем число ЧТФ для разных процедур может быть разным. Если у какихто процедур нет ни одной ЧТФ, это значит, что они не обрабатывались а,следовательно, представляют собой мертвый код и могут быть удалены.
Для остальныхпроцедур совокупность ЧТФ представляет собой их обобщенную трансфернуюфункцию в контексте анализируемой программы.Рассматриваются только операции работы с памятью (READ и WRITE) и операциивызова (CALL). Каждой такой операций одной процедуры ставится в соответствиеупорядоченный набор, длина которого равна числу ЧТФ, созданных для этойпроцедуры в процессе анализа. Для операций работы с памятью элементом такогонабора будет множество имен, с которым операция может работать во всех техконтекстах, в которых применялась соответствующая ЧТФ. Для операции вызоваэлементом набора будет пара множеств: одно – множество имен, в которые внутривызываемой процедуры (или нескольких процедур) может осуществляться запись,другое – множество имен, которые в этой процедуре (процедурах) могут читаться.Построение таких наборов осуществляется следующим образом.
Для каждой ЧТФпроцедуры один раз производится обход представления этой процедуры, почти так, какэто делалось в процессе проведения анализе, с той лишь разницей, что теперь нетнеобходимости обрабатывать операции вызова, ибо весь вклад от них уже учтен в ЧТФ.Также нет необходимости уходить в вызывающий контекст для выяснения, можно липо некоторому имени name создать РП: если в одном из тех контекстов, в которыхиспользовалась данная ЧТФ, РП можно было создать, значит, он был создан, если нет,то результатом операции чтения name станет пустое множество. Как и в процессеанализа, в процессе обхода представления и вызывается функция EvalExpr, котораяставит в соответствие операциям READ и WRITE множества имен, с которыми ониработают.
Для того, чтобы создать пару множеств для операции CALL, обходитсямножество всех присваиваний в узле вызова. Объединение всех имен, в которые вданном узле существуют присваивания, дает множество имен, в которые можетпроисходить запись. А объединение всех правых частей этих присваиваний даетмножество имен, которые в процедуре могут читаться. Однако в случае flow-insensitiveверсии анализа нет возможности среди всех присваиваний процедуры выделить те,которые отражают изменения, вносимые конкретной операцией вызова. Поэтому впроцессе проведения такой версии анализа в каждой ЧТФ для каждой операции вызовахранится пара множеств: первое содержит имена, которые процедуры, вызываемыеэтой операцией, могут читать, второе – в которые они могут писать.
При трансляциирезультатов в вызывающий контекст эти множества пополняются.Для проверки того, что две операции рассматриваемых типов могут (при одной о тойже активации процедуры) работать с одним и тем же фрагментом памяти (иначе говоря,могут конфликтовать), следует найти пересечения всех пар множеств имен,относящихся к одной и той же ЧТФ. Если существует непустое пересечение, тосуществуют контексты, в которых операции могут конфликтовать.В процессе анализа в структуре ЧТФ можно сохранять информацию о том, в какихвызывающих контекстах процедуры она использовалась.
Тогда, если существует такойвызывающий контекст, в котором какие-то пары её операций не конфликтуют во всехтех ЧТФ, которые использовались для обработки этого контекста, целесообразносоздать копию этой процедуры (другими словами, клонировать процедуру). Воперациях этой копии наследуются только те множества имен, которые соответствуютуказанным ЧТФ, а в рассматриваемом контексте вместо вызова исходной процедурыподставляется вызов её копии.Опишем теперь, что происходит с результатами анализа при inline-подстановке однойпроцедуры в другую.
Очевидно, что оставить результаты анализа неизменными нельзя,даже если число ЧТФ у обеих процедур одинаковое, ибо результаты анализа каждой изних выражены в терминах пространства имен разных ЧТФ и уже нет функцийсвязывания, которые бы позволили перетранслировать имена вызываемой процедуры вимена вызывающей. Предлагаемое решение состоит в следующем. Во времянаследования результатов анализа, в каждой операции создается одноэлементныйсписок, в единственный элемент которого помещается набор множеств. Каждоемножество набора содержит имена, с которыми работает операция в тех контекстах, вкоторых применялась соответствующая ЧТФ. При inline-подстановке для каждойоперации-копии (READ, WRITE, CALL), которая создается в вызывающей процедурепо операции-оригиналу подставляемой процедуры, заводится список.
Этот список естьконкатенация списка результатов операции вызова, вместо которой происходитподстановка, (этот список идет сначала), и списка результатов операции-оригинала.Таким образом, каждая новая inline-подстановка удлиняет список результатовопераций. Тогда, если вопрос о конфликте возникает между операциями, одна изкоторых существовала в процедуре до подстановки, а другая появилась после неё, тоответ будет таким же, как если бы вопрос о конфликте ставился для первой из этихопераций и операции вызова, вместо которой произошла подстановка. Если же вопросставится для операций, которые обе появились после подстановки, то первые равныеэлементы списков результатов пропускаются, а вопрос о конфликте имеет такой жеответ, как для операций-оригиналов в вызываемой процедуре до подстановки.Ещё одним полезным результатом анализа, который следует сохранить, являетсямножество процедур для вызова по косвенности.
При финальном обходе представлениядля каждой операции вызова по косвенности можно получить соответствующий этомувызову РП, в котором сохранено множество процедур. Объединение таких множествдля всех ЧТФ процедуры дает требуемый результат, который и сохраняется в операции.Предложенная схема анализа позволяет получать ответ на вопрос о зависимости попамяти между операциями. Однако если множество имен, которое было сопоставленонекоторой операции, содержит нелокальное имя, нельзя определить, с какими именнофрагментами памяти имеет дело эта операция.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
