Русский
Русский
English
Статистика
Реклама

Модификация исполняемого кода как способ реализации массивов с изменяемым границами

Введение

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

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

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

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

Далее все рассуждения приводятся на примере конкретной реализации компилятора PL/1-KT с языка PL/1 для Win64.

Подход к реализации

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

dcl x(100,100) float(53);dcl (i,j)      fixed(63);x(i,j)=12345e0;

соответствует такой исполняемый код x86-64:

48693DB838010020030000   imul rdi,I,80048A1C038010000000000     mov  rax,J488DBCC710FDFFFF         lea  rdi,X+0FFFFFCD8h[rdi+rax*8]BE30000000               mov  rsi,offset @00000030h48A5                     movsq

Видно, что при разных значениях границ-констант массива исполняемый код будет отличаться лишь разными значениями операндов-констант в некоторых командах. В данном случае это значение третьего операнда-константы операции IMUL и константа-смещение в операции LEA.

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

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

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

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

Выделение памяти для массивов с динамическими границами

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

Поэтому память для массивов с динамическими границами должен явно выделять программист из кучи оператором ALLOCATE и освобождать оператором FREE. В языке PL/1 такие объекты считаются объектами с управляемой (CONTROLLED) памятью.

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

Обработка констант

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

Компилятор PL/1-KT переводит текст программы в промежуточную обратную польскую запись, где каждая константа это отдельная операция, имеющая единственный операнд само значение константы (4 байта). Для реализации динамических массивов вводится новая операция модифицированная константа, которая имеет не значение, а операнд-ссылку на таблицу компилятора. По ссылке располагается само значение константы, а также вся необходимая информация, позволяющая определить, как получилось данное значение, и, следовательно, позволяющая рассчитать новое значение при новых границах.

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

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

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

Объекты программы, зависящие от размеров границ массивов

Таких объектов в программе на языке PL/1 оказалось восемь:

- встроенные функции языка LBOUND/HBOUND/DIMENSION, выдающие значения нижней/верхней границы или числа элементов для заданной размерности;

- оператор ALLOCATE, неявно имеющий входным параметром число выделяемых массиву байт, зависящее от его границ;

- индекс, т.е. собственно команды вычисляющие часть адреса по очередному индексу-переменной при обращении к элементу массива;

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

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

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

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

Синтаксис массивов с изменяемыми границами

В стандарте языка PL/1 изменяемые границы массивов просто задаются выражениями, например:

dcl  n      fixed(31),     x(0:n) float ctl;get list(n);allocate x;

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

dcl  n      fixed(31),     x(*)   float ctl;get list(n);?index(1,1)=0; ?index(1,2)=n; // устанавливаем новые границыcall ?ret(addr(x));           // меняем константы кода обращения к xallocate x;

Для изменения границ в компилятор PL/1-KT введены служебные элементы в виде встроенного глобального двумерного массива новых значений нижних и верхних границ:

dcl ?index(15,2) fixed(31) external;

Первая размерность этого массива 1:15, поскольку это максимально допустимое число размерностей массива в компиляторе PL/1-KT.

А также введена служебная подпрограмма перетрансляции, т.е. корректировки констант в командах, использующая текущие значения массива ?index:

dcl ?ret entry(ptr) external;

Служебный массив ?index и подпрограмма ?ret предопределены в компиляторе PL/1-KT. При запуске программы все значения границ в массиве ?index по умолчанию заданы единичными.

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

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

Компилятор PL/1-KT отмечает в своей таблице признак изменяемой границы у данного массива, а сам значок * просто заменяет на некоторые некруглые значения границ. Это сделано для того, чтобы далее в процессе компиляции создавались обычные команды для массивов с границами-константами. А некруглые значения не позволяют оптимизатору применять более короткие формы команд, поскольку тогда невозможно скорректировать их другими, например, большими значениями.

Динамические границы, обозначаемые *, могут быть только старшими размерностями и следовать подряд. При этом такие границы могут быть не только у массивов однородных элементов, но и у массивов структур, т.е. агрегатов данных разных типов. Младшие размерности при этом могут оставаться константами, например:

dcl // структура-массив с изменяемыми границами1 s(*,*)       ctl, 2 x1          char(100) var, 2 y1 (-1:25)  float, // внутри могут быть и границы-константы 2 z1 (100)    fixed(31);

Ссылка на массивы с изменяемыми границами

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

dcl x(100) float based(p1),   (p1,p2) ptr;p2=addr(x); //это эквивалентно p2=p1;

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

call умножение_матриц(addr(a),addr(b),addr(c),m,n,q);

и тогда описание параметров таких подпрограмм становится единообразным, не зависящим от самих массивов:

dcl умножение_матриц entry(ptr,ptr,ptr,fixed(31),fixed(31),fixed(31));

Этот прием позволяет передавать динамические массивы в подпрограммы, но не позволяет принимать их внутри подпрограмм, поскольку тогда опять нужно присваивать указатели-параметры служебным указателям с недоступными именами. Поэтому в компиляторе PL/1-KT дополнительно разрешено использовать и в левой части присваивания встроенную функцию ADDR:

dcl x(*) float ctl,    p1   ptr;addr(x)=p1; //эквивалентно оператору <служебный указатель на x>=p1;

Пример использования динамических массивов как параметров

В данном примере применена описанная выше технология корректировки констант для универсального умножения матриц задаваемого размера. Динамические массивы-матрицы создаются оператором ALLOCATE и передаются (неявно, указателями) в универсальную процедуру умножения матриц. Корректировка констант в исполняемом коде производится как для фактических параметров A1, B1,C1, так и для формальных A, B, C внутри подпрограммы. Кроме этого, формальным параметрам присваиваются фактические значения с помощью разрешения использовать функцию ADDR в левой части присваивания. Процедура УМНОЖЕНИЕ_МАТРИЦ может находиться в отдельном модуле и транслироваться автономно.

TEST:PROC MAIN;DCL (A1,B1,C1)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (M1,N1,Q1)      FIXED(31); // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- КОРРЕКТИРУЕМ КОНСТАНТ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----?INDEX(1,2)=M1; ?INDEX(2,2)=N1;?RET(ADDR(A1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ A1?INDEX(1,2)=N1; ?INDEX(2,2)=Q1;?RET(ADDR(B1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ B1?INDEX(1,2)=M1;?RET(ADDR(C1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ C1//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1) И C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;       // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31); // ЗАДАННЕ ГРАНИЦDCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- НОВЕ ОПЕРАТОР ПРИСВАИВАНИЯ УКАЗАТЕЛЕЙ ----ADDR(A)=P1;     // АДРЕС ДЛЯ МАССИВА AADDR(B)=P2;     // АДРЕС ДЛЯ МАССИВА BADDR(C)=P3;     // АДРЕС ДЛЯ МАССИВА C//---- КОРРЕКТИРУЕМ КОНСТАНТ МАТРИЦ A(M,N), B(N,Q), C(M,Q) ----?INDEX(1,2)=M; ?INDEX(2,2)=N;?RET(ADDR(A));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ A?INDEX(1,2)=N; ?INDEX(2,2)=Q;?RET(ADDR(B));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ B?INDEX(1,2)=M;?RET(ADDR(C));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ C//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Эта тестовая программа эквивалентна приведенной ниже программе с обычными границами-константами у матриц.

TEST:PROC MAIN;DCL (P1,P2,P3)      PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL A1(5,4)         FLOAT BASED(P1), // СТАТИЧЕСКАЯ МАТРИЦА А1    B1(4,3)         FLOAT BASED(P2), // СТАТИЧЕСКАЯ МАТРИЦА B1    C1(5,3)         FLOAT BASED(P3); // СТАТИЧЕСКАЯ МАТРИЦА C1DCL (M1,N1,Q1)      FIXED(31);       // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31);       // ЗАДАННЕ ГРАНИЦDCL A(5,4)       FLOAT BASED(P1), // СТАТИЧЕСКИЕ МАТРИЦ    B(4,3)       FLOAT BASED(P2),    C(5,3)       FLOAT BASED(P3);DCL (I,J,K)      FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Обе программы дают идентичный результат:

C1(1,1)=  2.600000E+01 C1(1,2)=  1.200000E+01 C1(1,3)= -2.000000E+00C1(2,1)=  3.200000E+01 C1(2,2)=  1.400000E+01 C1(2,3)= -4.000000E+00C1(3,1)=  3.800000E+01 C1(3,2)=  1.600000E+01 C1(3,3)= -6.000000E+00C1(4,1)=  4.400000E+01 C1(4,2)=  1.800000E+01 C1(4,3)= -8.000000E+00C1(5,1)=  5.000000E+01 C1(5,2)=  2.000000E+01 C1(5,3)= -1.000000E+01

Заключение

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

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

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

В чем-то похожие подходы применялись и ранее, например, в языке Visual Basic имеется операция reDim, задающая границы при исполнении программы. Однако в этих случаях динамически меняются все же данные в программе, а не операнды команд ее исполняемого кода.

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

Послесловие

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

Источник: habr.com
К списку статей
Опубликовано: 09.01.2021 02:10:27
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Программирование

Алгоритмы

Компиляторы

Массивы

Динамические

Pl/1

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru