График зависимостей в дизайне компилятора

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

Это помогает нам определить влияние изменения и объекты, на которые оно влияет. Ребра рисования для соединения зависимых действий можно использовать для создания графа зависимостей. Эти дуги приводят к частичному упорядочению операций, а также к предотвращению параллельного выполнения программы. Хотя цепочка использования-определения является типом анализа зависимостей, она приводит к чрезмерно осторожным оценкам достоверности данных. На общем маршруте управления может быть четыре типа зависимостей между операторами I и j.

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

Типы зависимостей:

Зависимости в целом подразделяются на следующие категории:

1. Зависимости данных:

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

2. Зависимости управления:

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

3. Зависимость от потока:

В информатике зависимость потока возникает, когда оператор программы ссылается на данные предыдущего оператора.

4. Антизависимость:

Когда инструкции требуется значение, которое позже будет изменено, это называется антизависимостью или записью после чтения (WAR). Инструкция 2 антизависима от инструкции 3 в следующем примере; порядок этих инструкций не может быть изменен, и они не могут выполняться параллельно (потенциально изменяя порядок инструкций), потому что это изменит конечное значение A.

5. Выходная зависимость:

Выходная зависимость, также известная как запись после записи (WAW), возникает, когда последовательность, в которой выполняются инструкции, влияет на конечное выходное значение переменной. В приведенном ниже примере существует выходная зависимость между инструкциями 3 и 1; изменение порядка инструкций повлияет на конечное значение A, поэтому эти инструкции не могут выполняться параллельно.

6. Контроль-зависимость:

Если результат A определяет, следует ли выполнять B или нет, инструкция B имеет управляющую зависимость от предыдущей инструкции A. Инструкция стиля отображения S 2S 2 имеет управляющую зависимость от инструкции стиля отображения S 1S 1 в следующем примере. . Однако стиль отображения S 3S 3 не зависит от стиля отображения S 1S 1, поскольку стиль отображения S 3S 3 всегда выполняется независимо от результата стиля отображения S 1S 1.

Пример графика зависимостей:

Спроектируйте граф зависимостей для следующей грамматики:

E -> E1 + E2
E -> E1 * E2 

Требуемый граф зависимостей для приведенной выше грамматики представлен как –

1. Синтезированные атрибуты представлены .val .
2. Следовательно, E.val , E1.val и E2.val имеют синтезированные атрибуты.
3. Зависимости показаны черными стрелками.
4. Стрелки от E1 и E2 показывают, что значение E зависит от E1 и E2.

Разрешение зависимости:

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

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

При разрешении зависимостей Gradle (инструмент автоматизации) обрабатывает два типа конфликтов:

Конфликты версий:

Конфликт версий — это конфликт, который возникает, когда два компонента зависят от одного и того же модуля, но имеют разные версии.

Например:

Предположим, что проект зависит от библиотеки реагирования Facebook, то есть «com.google.react: react:18.7.0». здесь версия 18.7.0. Теперь мы можем ясно видеть, что это также зависит от какой-то другой библиотеки, которая сама зависит от реакции, но версия 19.0.2 совсем другая.

Gradle решает эту проблему, выбирая самую высокую версию. В этом случае будет выбран 19.0.2.

Но это не конец магазина. В Gradle есть понятие расширенного объявления версии, и существует множество способов выбрать версию из множества вариантов.

Конфликты реализации:

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

1. Попытка выбрать несовместимые варианты,
2. Объявите ту же возможность

Использование графика зависимостей:

1. Основная идея графов зависимостей состоит в том, чтобы компилятор проверял различные типы зависимостей между операторами, чтобы предотвратить их выполнение в неправильной последовательности, то есть таким образом, который влияет на смысл программы.
2. Это помогает идентифицировать многочисленные параллелизуемые компоненты программы.
3. Автоматические установщики программного обеспечения: они обходят график в поисках пакетов программного обеспечения, которые необходимы, но еще не установлены. Сцепление пакетов определяет надежность.
4. Планирование инструкций использует зависимость более широко.
5. Графы зависимостей широко используются при устранении мертвого кода.