Program Analysis

1. Введение
2. Использование сторонних результатов анализа
3. Индексные обращения в границах измерений
4. Математические функции стандартной библиотеки
5. Внешние вызовы анализируемых функций
6. Подстановка функций
7. Неиспользуемая память
8. Безопасное приведение типов
9. Небезопасный анализ
10. Функции стандартной библиотеки
11. Результаты Анализа

1 Introduction

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

2 External Analysis Results

--fanalysis-use=<filenames> - Use external analysis results to clarify analysis

В дополнение к статическому анализу программы может быть использован динамический анализ, а также некоторые свойства программы могут быть указаны вручную. Независимо от способа получения (динамический анализ и/или указания пользователя), чтобы передать соответствующую информацию инструменту TSAR используется опций -fanalysis-use, которая позволяет указать пути до файлов в формате JSON. Допускается указание файлов через запятую и/или многократное указание рассматриваемой опции. Указываемые файлы должны содержать описание дополнительных свойств программы.

Описание свойств программы должно быть представлено в следующем в виде:

{
  "name" : "RawInfo",
  "Functions" : [
    {
      "File": <path-to-file>,
      "Line": <number>,
      "Column": <number>,
      "Name": <name>,
      "Pure": <bool>
    },
    ...
  ],
  "Vars": [
    {
      "File": <path-to-file>,
      "Line": <number>,
      "Column": <number>,
      "Name": <name>
    },
    ...
   ],
  "Loops": [
    {
      "File": <path-to-file>,
      "Line": <number>,
      "Column": <number>,

      "WriteOccured": [<var-list>],
      "ReadOccured": [<var-list>],

      "Private": [<var-list>],
      "UseAfterLoop": [<var-list>],
      "DefBeforeLoop": [<var-list>],

      "Reduction": [{<var-id> : <reduction-kind>,...}],
      "Induction": [{<var-id> : {"Start": <integer>, "End": <integer>, "Step": <integer>},...],

      "Flow": [{<var-id> : {"Min": <distance>, "Max": <distance>},...}],
      "Anti": [{<var-id> : {"Min": <distance>, "Max": <distance>},...}],
      "Output": [{<var-id> : {"Min": <distance>, "Max": <distance>},...}]
    },
    ...
  ]
}

Свойство Pure для функций указывает на отсутствие побочного эффекта у любого вызова функции. Считается, что побочный эффект могут порождать не только обращения по некоторому адресу, но и сам факт использование этого адреса (например, сохранение его по адресу, соответствующему некоторому параметру вызова). Источником побочного эффекта считается любой участок памяти (или адрес участка памяти), используемый внутри какого-либо вызова функции, если данные участок памяти не может быть представлен, как результат однократного разыменования некоторого параметра-указателя данного вызова (т.е. для функции void foo(int *X) { *X = 1; } свойство Pure может быть указано, в то время как для функции void foo(int **X) { **X = 1;} уже нет).

Свойства переменных указываются для циклов, в которых к ним есть обращения:

• WriteOccured/ReadOccured - указывают на присутствие операций записи в/чтения из переменной в цикле;
• Private - указывает на факт записи в переменную значения на итерации цикла перед чтением значения этой же переменной на этой же итерации цикла; важно иметь в виду, что данное свойство ничего не говорит о том, используется ли переменная после выхода из цикла;
• UseAfterLoop - указывает, используется ли переменная на чтение после выхода из цикла; совместно со свойством Private данное свойство позволяет использовать спецификации private доступные в директивных моделях параллелизма, таких как DVMH или OpenMP;
• DefBeforeLoop - указывает, используется ли переменная на чтение в цикле до присваивания ей некоторого значения на итерации данного цикла; совместно со свойством Private данное свойство позволяет указать переменные, которым соответствует спецификация firstprivate в директивных моделях параллелизма, таких как OpenMP;
• Reduction - указывает на наличие редукционной операции по данной переменной в цикле, рассматривается как указание на возможность использования спецификации параллелизма reduction;
• Induction - указывает, что переменная является индуктивной переменной цикла;
• Flow/Anti/Output - указывает на наличие зависимостей в цикле по данной переменной: прямой/обратной/по выходу с указание расстояния зависимости; указание данных свойств не зависит от указания свойства Private, факт отсутствия всех данных свойств зависимостей означает отсутствие зависимости по данным в рассматриваемом цикле и наличие свойства Private может не требовать использования дополнительных спецификаций параллелизма (private и аналогичных, примером может быть инициализация массива внутри цикла, когда на всех итерациях цикла перезаписываются разные элементы массива, в этом случае может быть указано свойство Private, но для параллельного выполнения данного цикла дополнительных спецификаций параллелизма не требуется).

Идентификатором переменной <var-id> служит индекс переменной в массиве Vars. Список переменных <var-list> состоит из набора идентификаторов переменных <var-id>. Расстояние зависимости <distance> - целая неотрицательная константа. Для задания границ изменения индуктивной переменный, а также шага ее изменения используются целочисленные константы <integer>, если они не могут быть вычислены, то указывается ключевое слово null. Для задания типа редукционной операции используется <reduction-kind> в виде строковой константы (Add - сумма, Mult - умножение, Or - дизъюнкция, Add - конъюнкция, Xor - исключающее или, Max - максимум, Min - минимум), если тип редукционной операции не известен, то указывается ключевое слово null. Флаг <bool> принимает значения true или false. Свойства могут быть заданы не только для переменной, но и для более сложных выражений, например, в случае переменной-указателя X можно задавать свойства для адресуемой памяти *X. При описании свойств вместо символов * для обозначения операции разыменования указателя, должен быть использован символ ^ (т.е. в случае переменной X свойство должно быть задано для выражения ^X).

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

tsar Jacobi.c -instr-llvm
clang Jacobi.ll -lda -L<path-to-sapfor>/lib -o Jacobi.out

./Jacobi.out
DEBUG: ### Construct dynamic analyzer ###
DEBUG: DYNA_OUTPUT_JSON=
DEBUG: DYNA_OUTPUT=
DEBUG: DYNA_OUTPUT_FILENAME=
It=   1   Eps=1.500000e+01
It=   2   Eps=8.000000e+00
It=   3   Eps=2.875000e+00
It=   4   Eps=1.875000e+00
It=   5   Eps=1.242188e+00
It=   6   Eps=1.156250e+00
It=   7   Eps=9.086914e-01
It=   8   Eps=8.059082e-01
It=   9   Eps=7.261047e-01
It=  10   Eps=6.763306e-01
DEBUG: ### finalize ###
DEBUG: peak memory used = 3MB

tsar Jacobi.c --fanalysis-use=dyna-output.json

Первые две команды добавляют вызовы функций динамического анализа в исходную программу (результат будет сохранен в формате LLVM IR в файле Jacobi.ll) и компиляцию полученного файла совместно с библиотекой динамического анализа, являющейся частью SAPFOR. Затем полученный исполняемый файл может быть запущен на выполнение, при этом контролировать поведение динамического анализа можно используя следующие переменные окружения:

• DYNA_OUTPUT_JSON - указывает должен ли быть использован JSON формат для сохранения результатов анализа (1 - JSON формат (по умолчанию), 0 - текстовый формат); текстовый формат позволяет посмотреть результаты динамического анализа, но не может быть использован для передачи полученных результатов инструменту TSAR;
• DYNA_OUTPUT - указывает тип потока вывода, в который должны быть сохранены результаты динамического анализа (file - результаты будут записаны в файл (по умолчанию), stdout - результаты будут записаны в стандартный поток вывода, stderr - результаты будут записаны в стандартный поток ошибок);
• DYNA_OUTPUT_FILENAME - задает имя файла, в который будут записаны результаты динамического анализа (по умолчанию dyna-output.json|txt в зависимости от значения переменной DYNA_OUTPUT_JSON).

Последняя команда передает результаты динамического анализа инструменту TSAR.

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

Результаты статического анализа также можно получить в JSON-формате, воспользовавшись опцией инструмента TSAR -print-analysis. В результате будет сгенерирован файл analysis.json.

3 Inbounds Subscripts

--finbounds-subscripts - Assume that subscript expression is in bounds value of an array dimension

--fno-inbounds-subscripts - Check that subscript expression is in bounds value of an array dimension (default)

Рассмотрим следующий пример, в котором границы циклов в гнезде заданы переменными. В цикле используется двумерный массив, при этом стандартом языка С допускается выход за границы измерения массива при вычислении адреса используемого элемента. Например, обращение U[0][101] является корректным и фактически приведет к использованию элемента U[1][1]. В сочетании с тем, что границы измерения индуктивных переменных цикла не известно во время компиляции, становится сложно доказать отсутствие зависимости по данным в цикле.

double U[100][100];
int IStart, IEnd, JStart, JEnd;

void foo() {
  for (int I = IStart; I < IEnd; ++I)
    for (int J = JStart; J < JEnd; ++J)
      U[I][J] = U[I][J] + 1;
}

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

4 Math Library Functions

--fmath-errno - Require math functions to indicate errors by setting errno

--fno-math-errno - Prevent math functions to indicate errors by setting errno

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

#include <math.h>

void foo(int N, float *A) {
   for (int I = 0; I < N; ++I)
     A[I] = sqrt(A[I]);
}

Если пользователю не требуется сохранение кода ошибок системных функций, то он может явно указать об этом, воспользовавшись опцией -fno-math-errno.

5 External Calls

--fexternal-calls - Check whether a function could be called outside the analyzed module (default)

--fno-external-calls - Assume that functions are never called outside the analyzed module

Рассмотрим следующий фрагмент кода, в котором определены две функции с внешним связыванием, то есть они могут быть вызваны из других единиц трансляции. Так как в процессе анализа не известно, в каком контексте вызывается функция bar и возможны ли другие вызовы функции foo, то TSAR будет считать, что внешняя память, записанная во время выполнения данных функций, может быть использована после их вызова. В данном случае это приведет к тому, что значение переменной X должно быть сохранено после выхода из цикла и в случае параллельного выполнения данного цикла потребуются дополнительные действия по сохранению данного значения (в случае OpenMP необходимо использовать спецификацию last private).

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

В этом случае, TSAR сможет определить, что при распараллеливании данного фрагмент кода достаточно использовать спецификацию private.

double X;

void foo(int N, float * restrict A) {
   for (int I = 0; I < N; ++I) {
     X = I;
     A[I] = X;
   }
}

void bar(int N, float * restrict A) {
  foo(N, A);
}

6 Function Inlining

--finline - Allow to inline function calls to improve analysis accuracy (default)

--fno-inline - Do not inline function calls to decrease analysis time

--inline-memory-access-count=<uint> - A function is only inlined if the number of memory accesses in the caller does not exceed this value

По умолчанию в процессе исследование программы может быть выполнена инлайн подстановка некоторых вызовов функций. Это повышает точность анализа, но может сказаться на времени обработки программы. Если время анализа слишком велико, то можно полностью запретить инлайн подстановку, воспользовавшись опцией -fno-inline. Чтобы управлять тем, какие функции будут подставлены, можно использовать опцию -inline-memory-access-count, задающую границу количества обращений к памяти в вызываемой функции, при которой в тело данной функции могут быть подставлены вызываемые из нее функции.

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

void bar(float *A) { *A = *A + 1; }

void foo(int N, float *A) {
   for (int I = 0; I < N; ++I)
     bar(A + I);
}

7 Redundant Memory

--fignore-redundant-memory=<value> - Try to discard influence of redundant memory on the analysis results

=disable - Always analyze redundant memory (default)

=strict - Analyze redundant memory before source-to-source program transformation

=bounded - Source-to-source transform passes ignore unused tails of redundant memory locations

=partial - Source-to-source transform passes ignore unused parts of redundant memory locations

=weak - Source-to-source transform passes ignore the whole redundant memory locations

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

Чтобы управлять влиянием таких избыточных объектов на конечный результат анализа можно использовать опцию -fignore-redundant-memory. Доступно пять режимов анализа программы.

По умолчанию учитываются все объекты программы (disable) и найденные для них свойства будут присутствовать в выдаче результатов анализа. Второй режим (strict) учитывает избыточные объекты при определении возможности преобразования и/или распараллеливания исходной программы, но ограничивает их влияние на другие объекты программы. Первые два режима безопасны с точки зрения консервативности анализа, так как не возлагают на пользователя ответственность за корректность проводимого анализа при преобразовании/распараллеливании программ. Оставшиеся режимы требуют более аккуратного использования.

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

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

В самом небезопасном режим (weak) TSAR пытается игнорировать все объекты, которые не удалось проанализировать, предполагая, что данные объекты относятся к избыточным.

Для следующего примера достаточно использовать режим strict, чтобы ограничить влияние неиспользуемой переменной Nx1 и недостижимого вызова функции bar() и точно определить расстояние зависимости по массиву B и отсутствие зависимости по массиву A.

int A[10], B[11];
int * bar();
int Nx;

void foo() {
  for (int I = 0; I < 10; ++I) {
    int Nx1 = Nx + 1;
    if (I > 10)
      bar()[4] = 6;
    A[I] = A[I] + Nx + 1;
    B[I+1] = B[I] + Nx + 1;
  }
}

8 Safe Type Cast

--fsafe-type-cast - Disallow unsafe integer type cast in analysis passes

--fno-safe-type-cast - Allow unsafe integer type cast in analysis passes(default)

Во время исследования программы в инструменте TSAR выполняются операции над выражениями, представленными в символьном виде. Например, выражения могут быть приведены к более простому виду, могут выполняться арифметические операции, затрагивающие несколько выражений. В общем случае в программе используются переменные разных типов и для строгости вычисления выражений, в которых они участвуют, выполняется приведение переменных и выражений к единому типу. Наличие такого рода приведения типов, в том числе и неявного, препятствуют выполнению символьных операций над выражениями. Поэтому в TSAR данные приведения типов игнорируются и в некотором роде можно считать, что всегда используется самый общий тип. Так как выполняемые операции над выражениями не приводят к генерации исполняемого кода, а необходимы только в процессе анализа, то данное упрощение является допустимым. Если по каким-то причинам необходимо, чтобы и в процессе анализа сохранялась строгое соответствие между типами операндов в выражении, то можно воспользоваться опцией -fsafe-type-cast.

9 Unsafe Analysis

--funsafe-tfm-analysis - Perform analysis after unsafe transformations

--fno-unsafe-tfm-analysis - Disable analysis after unsafe transformations(default)

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

10 Library Functions

--fanalyze-library-functions - Perform analysis of library functions (default)

--fno-analyze-library-functions - Do not perform analysis of library functions

По умолчанию анализ выполняется для всех функций, реализация которых доступна в программе. Так как преобразование и распараллеливание внутри функций стандартной библиотеки не допускается, то выполнение некоторых видов анализа может быть излишним. В случае необходимости, чтобы повысить производительность выполняемого анализа, можно отключить несущественный анализ библиотечных функций используя опцию -fno-analyze-library-functions. Данная опция не влияет на полноту анализа пользовательских функций и необходимый для их полного исследования анализ библиотечных функций будет в любом случае выполнен.

11 Analysis Results

Анализ программы выполняется над ее представлением в виде LLVM IR, затем полученные результаты отображаются на объекты исходного кода программы. Статический анализ консервативен в том смысле, что выявляемые им свойства должны гарантировать корректность последующего преобразования и распараллеливания программы. При этом выявленные свойства могут быть не точны, например, может быть диагностировано наличие зависимости по данным, даже в случае отсутствия такой зависимости. В результате может не получиться выполнить полное распараллеливание программы, но построенная TSAR программа останется корректной.

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

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

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

Чтобы получить обобщенные результаты анализа программы в текстовом виде можно воспользоваться опцией -print-only=da-di: в результате будут выданы результаты анализа программы после каждого этапа. При распараллеливании и преобразовании программ используются результаты последнего этапа анализа. Чтобы получить результаты только после какого-то конкретного этапа анализа можно воспользоваться опцией -print-step=<number>, где <number> - порядковый номер запрашиваемого этапа.

Найденные свойства будут связаны с участками памяти программы, которые характеризуются переменной, с которой они связаны, и размером. Отдельный участок памяти задается в виде <<reference>:<position-list>, <size>>, где <reference> - выражение задающее, результат разыменования указателя, ссылающегося на начало участка памяти; <position-list> - позиция в исходном коде программы, которая является источником данного участка памяти; <size> - размер участка памяти в байтах.

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

• no access - к участку памяти нет обращений на чтение/запись в цикле, но есть, например, операции взятия адреса (если участок памяти, никак не используется в цикле, то для него свойства указаны не будут);

• address access – выполнение цикла потенциально зависит от адреса участка памяти (например, он используется как ключ в контейнере), в этом случае не может быть создана локальная копия соответствующей переменной в рамках каждого потока выполнения цикла (например, переменная не может быть указана в спецификации private), так как у каждой копии будет свой независимый адрес;

• свойства, связанные с приватизацией данных в рамках каждой итерации цикла:

  • private – приватизируемые данные, не используются после выхода из цикла, не требуется знать значение до входа в цикл;

  • last private (second-to-last private) – значение используется после цикла и было посчитано на последней (предпоследней) итерации (знание предпоследней итерации актуально для for-циклов, так как последней итерацией считается последняя проверка условия);

  • dynamic private – значение используется после выхода из цикла, не известна итерация на которой оно было посчитано;

  • first private – в цикле используется значение, полученное до входа в цикл (структура из двух элементов, один из которых приватный, а второй используется только на чтение);

• read only – участок памяти, доступ к которому происходит только на чтение;

• shared – участок памяти, который не порождает зависимость (данное свойство может быть использовано совместно с private, например, если разные итерации цикла обращаются к разным элементам массива (инициализация массива)).

• induction – индуктивная переменная цикла, дополнительно может быть указаны начало:конец:шаг, если они могут быть вычислены;

• reduction – редукционная скалярная переменная, с указанием типа редукционной операции, если он известен add, mult, or, and, xor, max, min;

• flow, anti, output – зависимости по данным: прямая, обратная и по выходу соответственно, с указанием границ изменения расстояния зависимостей (min:max) для гнезда циклов (данного цикла и объемлющих);

• header access - участок памяти, используемые в заголовке цикла;

• lock access – участок памяти, анализ по которому (а также по пересекающимся с ним) не удалось уточнить, начиная с некоторого этапа анализа (например, из-за преобразований отменяющих консервативность анализа),

• redundant – участок памяти, который потенциально может быть удален из исходной программы после ряда преобразований на уровне исходного кода, отсутствие такого участка памяти потенциально улучшит качество проводимого анализа. Оценить влияние такого преобразования можно с помощью опции –fignore-redundant-memory.

• no promoted scalar – участок памяти, который не был размещен на регистре: с определенного момента результаты анализа для таких участков памяти не уточняются (опция -funsafe-tfm-analyis отменяет данное поведение, ответственность за корректность анализа ложится на пользователя).

• indirect access – участок памяти используется неявно, например, за счет указателя, при этом TSAR известно какие именно участки памяти были использованы и какие указатели на него ссылаются;

• direct access - участки памяти, к которым был явный доступ в теле анализируемого цикла (в данном случае доступ мог быть осуществлен к некоторой части участка памяти);

• explicit access - участки памяти, которые явно присутствуют в некоторых операторах в теле цикла программы.

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

В качестве примера рассмотрим следующий фрагмент кода.

for (I = 1; I < NX - 1; I++)
  for (J = 1; J < NY - 1; J++)
    for (K = 1; K < NZ - 1; K++)
      A[I][J][K] = (A[I][J - 1][K] + A[I][J + 1][K]) / 2;

Ниже приведен пример отображения свойств, найденных для второго цикла гнезда после выполнения всех этапов анализ. В данном случае участки памяти, обозначаемые выражением A, обозначают адрес массива A, в то время как участки, обозначаемые *A обозначают непосредственно данные хранящиеся в массиве. Тот факт, что размер участка памяти задан как ? или +? указывает, что реальный размер массива вычислить не удалось. При этом если указывается +?, то в качестве участка памяти рассматривается вся выделенная память по адресу A, которая может быть получена через добавление неотрицательного смещения к указанному адресу. Указание ? означает, что в процессе анализа не удалось гарантировать неотрицательность используемых в программе смещений относительно указанного адреса.

В цикле была найдена прямая и обратная зависимость расстояния 1, так как элемент массива, используемый на итерации (I,J) был также использован на итерации (I,J-1).

loop at depth 2 Adi.func.c:67:5
private:
 <K:60, 4>
anti:
 <*A:59, +?>:[1:1,0:0]
flow:
 <*A:59, +?>:[1:1,0:0]
induction:
 <J:60, 4>:[Int,1,383,1]
read only:
 <A:59, 8> | <I:60, 4>
lock:
 <J:60, 4>
header access:
 <J:60, 4>
explicit access:
 <A:59, 8> | <I:60, 4> | <J:60, 4> | <K:60, 4>
explicit access (separate):
 <A:59, 8> <I:60, 4> <J:60, 4> <K:60, 4>
lock (separate):
 <J:60, 4>
direct access (separate):
 <*A:59, +?> <A:59, 8> <I:60, 4> <J:60, 4> <K:60, 4>