Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Введение
В свете все возрастающего потока англоязычных околонаучных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо некрасивого «модификация исполняемого кода» написать что-нибудь вроде «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,800
48A1C038010000000000 mov rax,J
488DBCC710FDFFFF lea rdi,X+0FFFFFCD8h[rdi+rax*8]
BE30000000 mov rsi,offset @00000030h
48A5 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)); // меняем константы кода обращения к x
allocate 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; // АДРЕС ДЛЯ МАССИВА A
ADDR(B)=P2; // АДРЕС ДЛЯ МАССИВА B
ADDR(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); // СТАТИЧЕСКАЯ МАТРИЦА C1
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) ----
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+00
C1(2,1)= 3.200000E+01 C1(2,2)= 1.400000E+01 C1(2,3)= -4.000000E+00
C1(3,1)= 3.800000E+01 C1(3,2)= 1.600000E+01 C1(3,3)= -6.000000E+00
C1(4,1)= 4.400000E+01 C1(4,2)= 1.800000E+01 C1(4,3)= -8.000000E+00
C1(5,1)= 5.000000E+01 C1(5,2)= 2.000000E+01 C1(5,3)= -1.000000E+01Заключение
Массивы с «динамически» меняющимися границами являются мощным и гибким инструментом и допустимы в ряде языков программирования. Однако этот инструмент требует и более сложного вычисления адресов элементов, в отличие от «статических» границ, когда часть вычислений можно выполнить уже на этапе компиляции.
Предлагаемые способ реализации оставляет исполняемый код таким же быстрым, как для массивов с границами-константами, изменяя лишь некоторые операнды-константы в командах с помощью вызова специальной служебной подпрограммы.
Это требует времени для подготовки выполняемого кода перед созданием очередного массива. Однако после такой корректировки констант в коде программы, ее выполнение идет так, словно границы массивов были изначально заданы нужными значениями, что позволяет сократить операции вычисления адресов элементов массивов и в целом ускорить программу, поскольку обычно требуется корректировка лишь нескольких команд, которые затем будут выполняться многократно.
В чем-то похожие подходы применялись и ранее, например, в языке Visual Basic имеется операция reDim, задающая границы при исполнении программы. Однако в этих случаях «динамически» меняются все же данные в программе, а не операнды команд ее исполняемого кода.
Кроме этого, данный способ является вообще простой возможностью ввода «динамических» массивов в компилятор, где их раньше не было, так как не требуется самого трудоемкого – изменения генерации выполняемого кода. Код остается прежним, лишь дополняется данными, содержащими адреса команд, требующих корректировки своего операнда-константы.
Послесловие
Обращаю внимание гг. комментаторов, что утверждение: «это никому не нужно, поскольку наш компилятор создает прекрасные динамические массивы» некорректно. Корректно оно в виде «мне и моим коллегам по проекту это не нужно». В этом случае я рад за вас, но считаю, что радовать остальных читателей такими комментариями необязательно.
