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

Первая публикация 19.07.2019

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

Тэги: dynamic array, resizable array, run-time reflection

Введение

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

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

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

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

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

x(i,j)=12345e0;

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

48693DB838010020030000…….imul…..q rdi,I,800
48A1C038010000000000…………mov…..q rax,J
488DBCC710FDFFFF………………..lea……..rdi,X+0FFFFFCD8h[rdi+rax*8]
BE30000000……………………………mov……q rsi,offset @00000030h
48A5………………………………………..movsq

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

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

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

Если границы массивов, а, значит, и объем занимаемой памяти, меняются во время исполнения программы, то в общем случае такие массивы не могут размещаться в «статической» памяти. Конечно, там можно заранее разместить массив с заведомо наибольшими значениями границ, а затем в процессе исполнения только «динамически» уменьшать их, но такой подход ограничен и неудобен. Поэтому память для массивов с «динамическими» границами должен явно выделять программист из «кучи» оператором ALLOCATE и освобождать оператором FREE. В языке PL/1 такие объекты считаются объектами с «управляемой» (CONTROLLED) памятью [2].

Следовательно, новые значения границ должны быть определены до собственно создания массива, т.е. до выполнения соответствующего оператора 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;

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

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

В данном примере применена описанная выше технология корректировки констант для выполнения универсального умножения матриц заданного размера. «Динамические» массивы-матрицы создаются оператором 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, задающая границы при исполнении программы. Однако в этих случаях «динамически» меняются все же данные в программе, а не операнды команд ее исполняемого кода.

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

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

Список литературы

  1. Д.Ю.Караваев «К вопросу о совершенствовании языка программирования» RSDN Magazine #4 2011, с. 15-21.
  2. Д.Ю.Караваев «О размещении переменных в стеке», 2019, ссылка в Интернете https://pl1.su/o-razmeshhenii-peremennyh-v-steke/
0

Автор публикации

не в сети 16 часов

admin

1
Комментарии: 24Публикации: 149Регистрация: 13-06-2019
Авторизация
*
*

три × 4 =

или используйте социальную сеть:
Регистрация
*
*
*

20 − один =

Генерация пароля

18 + шестнадцать =

Перевести »
Пролистать наверх