Анализ кода на CIL

Основные элементы графа потока управления

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

В качестве примера рассмотрим фрагмент программы на CIL:

.method private static void print(int32[] X) {
      .locals init (int32 i)
      			ldc.i4.0
      			stloc.0
      			br.s    loop_cond
loop_body: 	ldarg.0
      			ldloc.0
      			ldelem.i4
      			call    void System.Console::WriteLine(int32)
      			ldloc.0
      			ldc.i4.1
      			add
      			stloc.0
loop_cond: 	ldloc.0
      			ldarg.0
      			ldlen
      			conv.i4
      			blt.s   loop_body
      			ret
}

Граф потока управления для приведенного в примере метода изображен на рис. 4.1. Узлы графа обозначены прямоугольниками, в которых записаны инструкции CIL. Точка входа в метод обозначена специальным узлом с меткой "Метод print". Передачи управления между инструкциями показаны стрелками.

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

Количество дуг, исходящих из узла графа, зависит от записанной в нем инструкции. Это видно на примере инструкции blt.s, из которой исходит сразу две дуги. Дуга, помеченная числом 1, обозначает передачу управления в случае истинности проверяемого инструкцией blt.s условия.

В случае ложности условия передача управления осуществляется по дуге, помеченной числом 0.

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

Блоки обработки исключений в графе потока управления

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

Блоки, представленные в графе потока управления, можно разделить на четыре основные категории:

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

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

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

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

.method private static int32 checkedAdd(int32 x, int32 y) {
      .locals init (int32 result)
      .try {
      ldarg.0
      ldarg.1
      add.ovf
      stloc.0
      leave.s  exit
      }
      catch System.OverflowException {
      pop
      ldc.i4.0
      stloc.0
      leave.s  exit
      }
exit: ldloc.0
      ret
}

Граф потока управления для метода checkedAdd показан на рис. 4.3.

Дерево блоков в графе потока управления

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

Совсем другая ситуация возникает в графе потока выполнения. Чтобы определить, в какой блок входит некоторая инструкция графа (то есть узел графа), мы должны каким-то образом пройти от этой инструкции по дугам графа в обратном направлении до входа в блок. Время выполнения этой операции зависит от количества инструкций в блоке и значительно превышает время поиска блока в случае линейной последовательности инструкций.

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

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

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

Преобразование линейной последовательности инструкций в граф потока управления

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

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

Итак, пусть дан массив инструкций P размера N и массив предложений обработки исключений EH размера M. Требуется построить граф потока управления и возвратить ссылку на блок тела метода построенного графа.

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

Напомним также, что каждое предложение в массиве EH имеет следующий набор полей:

Создание массива узлов

На первом этапе работы алгоритма мы создаем узел графа для каждой инструкции и формируем из созданных узлов массив.

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

Узлы записываются в массив Nodes, состоящий из N элементов. При этом в массиве Nodes сохраняется порядок инструкций, то есть если некоторая инструкция располагается в массиве P по индексу i, то соответствующий ей узел будет размещен в i-том элементе массива Nodes.

На C#-подобном псевдоязыке первый этап работы алгоритма можно записать следующим образом:

Nodes = новый массив узлов размера N;
for (int i = 0; i < N; i++)
{
  Nodes[i] = новый узел, содержащий информацию об инструкции P[i];
}

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

Создание дерева блоков

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

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

Следует отметить, что размер массива B заранее неизвестен и зависит от информации в массиве EH. Нетрудно догадаться, что минимальное количество блоков в массиве B равно M+2 (если мы имеем один защищенный блок, M блоков обработки исключений и один блок тела метода). Аналогично, максимальное количество блоков вычисляется по формуле 2*M+1 ( M защищенных блоков, M блоков обработки исключений и один блок тела метода). Таким образом, необходимо либо сделать массив B динамическим, либо выделить для него 2*M+1 записей. В любом случае, пусть в дальнейшем BN обозначает текущее количество блоков, информация о которых хранится в массиве B.

Сначала создадим блок тела метода (назовем его MBB ). Он будет являться корнем дерева, которое мы строим. К нему в дальнейшем будут "прицеплены" все остальные узлы графа, и именно его наш алгоритм будет возвращать в результате своей работы. Для блока MBB в массив B добавляется запись, поле start которой содержит значение 0, а поле length - значение N.

Напомним, что предложения обработки исключений расположены в массиве EH в определенном порядке, гарантирующем, что более вложенный блок находится ближе к началу массива, чем объемлющий его блок. Так как нам требуется строить дерево блоков в направлении от корня к листам, то есть от менее вложенных блоков к более вложенным, то мы будем просматривать массив EH от конца до начала.

Итак, пусть переменная i пробегает значения от M-1 до 0 включительно. Тогда для каждого i-го предложения мы будем выполнять следующее:

На нашем псевдоязыке второй этап алгоритма можно записать следующим образом:

MBB = новый блок тела метода, в который записана информация о методе:
имя метода, сигнатура и данные о типах локальных переменных;

B = новый массив размера 2*M+1 для хранения информации о блоках;
B[0].block = MBB; B[0].start = 0; B[0].length = N;
BN = 1;
for (int i = M-1; i >= 0; i--)
{
  /* Поиск в массиве B блока, диапазон инструкций которого содержит защищенную областью 
i-го предложения */
  int tryOffset = EH[i].TryOffset, tryLength = EH[i].TryLength;
  for (int j = BN-1; j >= 0; j--)
    if (tryOffset >= B[j].offset 
      tryOffset+tryLength <= B[j].offset+B[j].length)
      break;

  if (tryOffset != B[j].offset || tryLength != B[j].length)
  {
    /* Создание нового защищенного блока и 
	        добавление его в дерево */
    B[BN].block = новый защищенный блок;
    Сделать блок B[j].block родителем блока B[BN].block;
    B[BN].offset = tryOffset;
    B[BN].length = tryLength;
    j = BN; BN++;
  }

  /* Создание блока обработки исключений */
  B[BN].block = новый блок обработки исключений, 
		 тип которого определяется значением EH[i].Flags;
  Сделать родителем блока B[BN].block тот же блок, 
		 который является родителем блока B[j].block;
  Добавить блок B[BN].block в конец списка 
		 обработчиков, ассоциированных с блоком B[j].block;
  B[BN].offset = EH[i].HandlerOffset;
  B[BN].length = EH[i].HandlerLength;
  BN++;

  if (EH[i].Flags обозначает блок с пользовательской фильтрацией)
  {
    /* Создание блока фильтрации */
    B[BN].block = новый блок фильтрации;
    Сделать блок B[BN-1].block родителем блока B[BN].block;
    B[BN].offset = EH[i].FilterOffset;
    B[BN].length = EH[i].HandlerOffset - EH[i].FilterOffset;
    BN++;
  }
}

Присвоение родительских блоков узлам графа

На третьем этапе узлы, соответствующие инструкциям, получают родителей. Тем самым завершается построение дерева блоков.

Можно заметить, что все блоки графа, включая блок тела метода, хранятся в массиве B. При этом порядок их следования в массиве таков, что вложенные блоки размещаются перед объемлющими их блоками. Это следует из того факта, что на втором этапе алгоритма блоки добавлялись в массив в порядке, обратном их следованию в массиве предложений обработки исключений ( EH ).

Присвоение родительских блоков узлам графа заключается в том, что мы перебираем все элементы массива B по порядку, начиная с первого элемента (в нем содержится информация о блоке тела метода). При этом для каждого i-го элемента массива B мы выполняем следующую операцию: каждый узел графа, имеющий в массиве Nodes индекс от B[i].offset до B[i].offset+B[i].length-1, получает в качестве родителя блок B[i].block.

for (int i = 0; i < BN; i++)
{
  for (int j = B[i].offset; j < B[i].offset+B[i].length; j++)
    Сделать блок B[i].block родителем узла Nodes[j];
}

Таким образом, на первой итерации цикла родителем всех узлов становится блок тела метода ( MBB ), а на последующих итерациях некоторые диапазоны инструкций меняют родителей, и это происходит до тех пор, пока не будут рассмотрены все элементы массива B. В конце концов родителями всех узлов становятся именно те блоки, в которые эти узлы непосредственно входят.

Формирование дуг

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

Определенную трудность представляет необходимость включения в граф потока управления узлов-блоков. Предварительным шагом для этого служит создание специального массива blockNodes размера N и запись в этот массив ссылок на блоки. При этом запись осуществляется следующим образом: мы перебираем все структуры в массиве B и для каждой i-ой структуры записываем в элемент массива blockNodes с индексом B[i].offset ссылку B[i].block. В результате, для того, чтобы определить, какой блок начинается с инструкции с номером k, достаточно посмотреть k-тый элемент массива blockNodes.

Формирование массива blockNodes удобно совместить с проведением дуг от узлов-блоков к узлам, соответствующим первым инструкциям этих блоков. Для этого нужно каждый блок, расположенный в массиве blockNodes по индексу i, соединить дугой с узлом Nodes[i]:

blockNodes = новый массив ссылок на узлы размера N,
	изначально заполненный нулевыми ссылками;
for (int i = 0; i < BN; i++)
{
  Провести дугу от B[i].block к Nodes[B[i].offset];
  blockNodes[B[i].offset] = B[i].block;
}

Добавление остальных дуг осуществляется путем перебора всех узлов, находящихся в массиве Nodes. Давайте рассмотрим, как это происходит для некоторого узла Nodes[i].

Прежде всего мы определяем номера инструкций, на которые может быть передано управление от инструкции, соответствующей узлу Nodes[i]. Естественно, для этого должна учитываться семантика инструкции. Полученные номера инструкций записываются в массив Flow.

Затем для каждого номера n, входящего в массив Flow, мы проводим дугу от узла Nodes[i] к соответствующему номеру n узлу графа:

На псевдоязыке это выглядит следующим образом:

for (int i = 0; i < N; i++)
{
  int[] Flow = новый массив, в который добавляются 
		 номера инструкций, на которые может быть передано
		 управление от инструкции, соответствующей узлу 
		 Nodes[i];
  for (int j = 0; j < Flow.Length; j++)
  {
    int n = Flow[j];
    if (blockNodes[n] != null  blockNodes[n] не является 
	      непосредственно или транзитивно родителем узла Nodes[i])
       Провести дугу от Nodes[i] к blockNodes[n];
    else
       Провести дугу от Nodes[i] к Nodes[n];
  }
}