Регистрация

[Программирование, Алгоритмы, Компиляторы] Модификация исполняемого кода как способ реализации массивов с изменяемым границами

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
09-Янв-2021 06:30
Цитировать


ВведениеВ свете все возрастающего потока англоязычных околонаучных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо некрасивого «модификация исполняемого кода» написать что-нибудь вроде «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, задающая границы при исполнении программы. Однако в этих случаях «динамически» меняются все же данные в программе, а не операнды команд ее исполняемого кода.Кроме этого, данный способ является вообще простой возможностью ввода «динамических» массивов в компилятор, где их раньше не было, так как не требуется самого трудоемкого – изменения генерации выполняемого кода. Код остается прежним, лишь дополняется данными, содержащими адреса команд, требующих корректировки своего операнда-константы.ПослесловиеОбращаю внимание гг. комментаторов, что утверждение: «это никому не нужно, поскольку наш компилятор создает прекрасные динамические массивы» некорректно. Корректно оно в виде «мне и моим коллегам по проекту это не нужно». В этом случае я рад за вас, но считаю, что радовать остальных читателей такими комментариями необязательно.
 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_programmirovanie (Программирование), #_algoritmy (Алгоритмы), #_kompiljatory (Компиляторы), #_massivy (массивы), #_dinamicheskie (динамические), #_pl/1, #_programmirovanie (
Программирование
), #_algoritmy (
Алгоритмы
), #_kompiljatory (
Компиляторы
)
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 25-Ноя 12:23
Часовой пояс: UTC + 5