Forth как переносимый ассемблер

Table of Contents

Abstract

Переносимый ассемблер, как и обычный ассемблер предоставляет доступ к аппаратным возможностям компьютера, таким как:

  • адреса памяти
  • машинные слова
  • адреса кода
  • арифметика по модулю

но абстрагирует различия между архитектурами, такими как:

  • синтаксис ассемблера
  • кодирование команд
  • набор регистров и их размер
  • режимы адресации.

Forth уже удовлетворяет ряду характеристик переносимого ассемблера и, следовательно, является хорошей основой.

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

Главные инновации PAF это:

  • теги, которые указывают поток управления для косвенного ветвления и вызовов
  • два вида вызовов (call) и определений (define):
    • ABI следуют платформозависимому соглашению о вызовах и полезны для взаимодействия с внешним миром
    • PAF позволяют использовать устранение хвостовых вызовов (tail call elimination) и полезен для реализации общих управляющих структур.

Введение

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

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

Разумеется, реализация переносимого ассемблера должна быть нацелена на эти архитектуры, но эти усилия могут быть использованы повторно несколькими компиляторами/интерпретаторами. В этой статье мы представляем новый переносимый ассемблер, PAF (Portable Assembly Forth). Существуют несколько языков, которые были разработаны и/или используются в качестве портируемых ассемблеров (см. предыдущие работы), так зачем вводить новый?

Вклад

Проблема, с которой столкнулись некоторые переносимые ассемблеры, заключается в том, что они требуют, чтобы код был организован в функции, которые следуют стандартным соглашениям о вызовах (ABI) платформы и которые обычно предотвращают (или серьезно затрудняют) использование оптимизации хвостовых вызовов (Tail Call Optimization). PAF предоставляет не только ABI-вызовы и определения для взаимодействия с остальным миром, но также вызовы и определения PAF, которые (в отличие от ABI-вызовов) могут быть оптимизированы с помощью TCO и поэтому могут использоваться как универсальные примитивы управления.

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

Наиболее значительная разница между PAF и Forth заключается в том, что PAF содержит ограничения, гарантирующие, что глубина стека всегда определяется статически, поэтому элементы стека могут отображаться в регистры (см. Forth и PAF и PAF определения и PAF вызовы). Интересно, что эти ограничения относительно незначительны и не влияют на большую часть Forth-кода; также интересно посмотреть пример от Forth-кода, на который они влияют (см. PAF vs Forth).

Предыдущие работы

Си

Cи и его диалекты, такие как GNU Cи, были использованы как портируемый ассемблер во многих системах:

  • это распространенный язык для написания интерпретаторов (например, Python, Ruby, Gforth) и систем времени выполнения;
  • Си также используется в качестве целевого языка для компиляторов: (например, исходный С++ компилятор cfront и одна из опций кодогерации GHC).

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

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

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

Другая проблема Си (и возможно причина почему он не используется так часто в качестве целевого языка для интерпретаторов) - это то, что его поток управления довольно негибкий: код разделен на Си-функции, из которых управление можно вернуть; единственный способ изменить поток управления через функции - это вызов функции longjmp();

Varargs в сочетании с другими языковыми возможностями привели к вызовам подпрограмм, в которых вызывающий отвечает за удаление аргументов из стека. Это делает невозможным реализацию гарантированной оптимизации хвостовых вызовов, которая необходима для использования вызовов Cи как общего примитива потока управления [Ste77].

В результате любой поток управления, который не соответствует Cи, например, неограниченные хвостовые вызовы, backtracking, сопрограммы и даже исключения трудно реализовать на Cи эффективно.

LLVM

LLVM является промежуточным представлением для компиляции, с несколькими фронтендами, проходами оптимизации и бакендами [LA04].

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

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

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

С--

C– [JRR99] был разработан как переносимый язык ассемблера. Многие соображения вошли в его дизайн, и, похоже, он хорошо разработан, если не считать того, что он слишком сложен на мой вкус, но проект, похоже, застопорился как общий переносимый язык ассемблера и, похоже, стал внутренним компонентом GHC (так называемый Cmm).

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

Vcode and GNU Lightning

Vcode [Eng96] - это библиотека, которая обеспечивает низкоуровневый интерфейс для быстрой генерации собственного кода (10 выполненных команд для генерации одной команды) и делает это переносимо. Она была частью исследовательского проекта и не имела широкоизвестного релиза, но она вдохновила проект GNU Lightning.

Требования чрезвычайно быстрой кодогенерации означают, что GNU Lightning не может самостоятельно выполнять распределение регистров. Поэтому фронтэнд должен выполнить распределение регистров. Он также не выполняет выбор команд; каждая инструкция GNU Lightning переводится, по крайней мере, в одну нативную инструкцию.

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

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

С этими изменениями не будет ли интерфейс GNU Lightning идеальным переносимым ассемблером? Он, безусловно, удовлетворит основные требования переносимого ассемблера, но в качестве замены языка, такого как C, он пропускает такие удобства, как распределение регистров.

Portable Assembler Forth (PAF)

Цели

  • Переносимость: Работает на нескольких разных архитектурах
  • Прямое соотношение между возможностями языка и возможностями машины, то есть, если вы посмотрите на фрагмент кода PAF, вы можете предсказать, как будет выглядеть машинный код. Однако отношение между PAF и машиной не настолько прямое, как для GNU Lightning: существует регистровая аллокация и выбор команд (instruction selection), может быть планирование команд (instruction scheduling) и репликация кода (code replication). Выбор команд и планирование команд делают возможным лучший код (за счет более медленной компиляции); распределение регистров взаимодействует с этими этапами, и оставляя его для клиентов. Требуется дублирование работы в клиентах, поскольку распределение регистров на самом деле не зависит от языка.
  • Возможности (пользовательская часть) машины могут быть выражены в PAF. Однако эта цель смягчается потребностями клиентов и целью мобильности. Таким образом, PAF сначала будет иметь только те возможности языка, которые могут потребоваться компиляторам и интерпретаторам (функции могут быть добавлены, когда клиенты нуждаются в них); и машинные возможности конкретных архитектур, которые не могут быть абстрагированы на языковые функции. Возможности, которые могут быть разумно реализованы этим способом на всех целевых целевых машинах, также не будут поддерживаться в качестве машинно-ориентированных.

Целевые машины

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

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

  • AMD64
  • ARM
  • IA-32
  • IA-64
  • MIPS
  • PowerPC,
  • SPARC

Память на целевых компьютерах адресована байтами с использованием плоского адресного пространства. Так, например, DSP с отдельными адресными пространствами X и Y не являются целевыми машинами. Целевые машины используют по модулю арифметику (wrap around), а знаковые числа представлены в "дополнительном коде".

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

Forth и PAF

Низкоуровневые функции Forth довольно близки к ассемблеру; например, как на языке ассемблера, ни компилятор, ни система времени выполнения не поддерживают систему типов, а язык различает различные операции на основе имени, а не на основе типа; например, Forth имеет < для знакового сравнения и U< для беззнакового сравнения ячеек (машинных слов), так же, как MIPS имеет slt и sltu, а Alpha имеет cmplt и cmpult.

Поэтому Forth - хорошая основа для переносимого ассемблера. Тем не менее, в этом контексте есть проблемы: в частности, в Forth глубина стека не обязательно статически определена (в отличие от JVM), хотя почти во всем коде Forth глубина стека фактически статически определяется (известна программисту на этапе компиляции, но не всегда известна Forth-системе). Поэтому мы изменяем эти языковые аспекты для PAF.

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

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

Пример

В следующем примере показаны два определения, написанные в PAF

                         \  cmpl %edx,%eax
: max                    \  jle L28
    2dup >? if           \  ret
        drop exit endif  \ L28:
    nip exit ;           \  movl %edx,%eax
                         \  ret

abi:xx- printmax {: n1 n2 -- :}
  "max(%ld,%ld)=%ld\n\0" drop
  n1 n2 2dup max abi.printf.xxxx-
  exit ;

\ Call from C:
\ main() { printmax(3,5); return 0; }

Первое определение, max, выглядит почти как обычный код Forth, а соответствующий код языка ассемблера для IA-32 показан в комментариях справа.

max не имеет зафиксированного соглашения о вызове; компилятор PAF может установить соглашение о вызове, которое подходит для max и его вызывающих процедур (например, это может быть tail-called.

Поскольку max не соответствует соглашению о вызовах платформы, он не может быть вызван, например, кодом C.

Второе определение, printmax, соответствует стандарту ABI платформы (как указано с помощью слова abi:) слово определения. xx- в abi:xx- показывает, что printmax ожидает и потребляет два целочисленных значения из стека данных и 0 плавающих значений из FP и создает 0 целочисленных и 0 плавающих. Прототип Си для этого определения может быть void printmax (long, long).

Printmax вызывает max, и компилятор может выбрать вызывающий интерфейс между вызывающим и max; он вызывает printf, используя стандартное соглашение о вызове с вызовом abi.printf.xxxx-, где xxxx- указывает, что четыре ячейки передаются как параметры integer/address, а возвращаемое значение printf игнорируется.

Локальные переменные используются в printmax, но могут использоваться в каждом определении. Выход из определений является явным.

Регистры

Некоторые языковые возможности прямо соответствуют реальным машинным регистрам: элементы стека, локальные переменные и значения.

  • Элементы стека (stack items) полезны для относительно недолговечных данных и (в отличие от локальных переменных (locals) могут использоваться для передачи аргументов и возвращаемых значений. Для стека нет указателя стека и области памяти, это просто абстракция, используемая компилятором. Слова манипуляции стеками, такие как DUP или SWAP, просто изменяют поток данных, и нет соответствующего им машинного кода (косвенными последствиями могут быть, например, move-инструкции при формировании потока управления).
  • Локальные переменные (locals) живут в пределах определения и являются удобством: локальные переменные исходного языка могут быть сопоставлены непосредственно с локальными переменными PAF с отсутствием необходимости в распределении регистров или управлении стеком на фронтенде. Если источник локальной переменой должен быть распределен по нескольким определениям PAF (например, потому что структура управления исходного языка отображается на хвостовой вызов PAF), локальная переменная может быть определена в каждом из этих определений, а константы передаются в стек между вызовами; это не так удобно, как хотелось бы, но, похоже, является хорошим компромиссом.
  • Значения (values) представляют собой глобальные (локальные в пределах потока) переменные, адрес которых не может быть взят, поэтому они могут храниться в регистрах.

Если элементы стека и локальные объекты не помещаются в регистры, они сохраняются в стеке, который не отображается в PAF коде; этот стек хранит элементы из данных и стека FP, locals и адресов возврата, так что это не соответствует представлению памяти, например, стека данных.

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

Если значения не помещаются в регистры, они сохраняются в глобальной/thread-local памяти.

Память

Слова c@ uw@ ul@ ( addr -- u ) загружают беззнаковые 8/16/32-битные значения из памяти, а sc@ w@ l@ ( addr -- n ) загружают знаковые 8/16/32-битные значения; @ (addr -- w) загружают ячейку (32-битную или 64-биную, в зависимости от архитектуры) из памяти; sf@ df@ ( addr -- r ) загружают 32/64-bit значения с плавающей точкой из памяти. c! w! l! ! ( x addr -- ) и sf! df! ( r addr --) сохраняют элементы из стека в память.

Арифметика

Обычные Forth-слова + - * NEGATE AND OR INVERT LSHIFT RSHIFT соответствуют арифметическим и логическим инструкциям, присутствующим на каждой машине.

Существуют также дополнительные слова типа / m* um* um/mod sm/rem которые соответствуют инструкциям некоторых машин и их необходимо синтезировать из других инструкций на машинах, на которых нет не соответствующих команд.

Сравнение

Слова =? <? u<? f=? f<? и тому подобные сравнивают два элемента стека и возвращают 0 на стеке если false и 1 если true. Они соответствуют Forth-словам = < u< f= f< и подобным с той разницей, что Forth-слова возвращают -1 (все биты установлены) когда true.

У ряда машин есть инструкции, которые производят "0 или 1" (MIPS, Alpha, IA-32, AMD64), тогда как для других так же легко получить "0 или 1", чтобы произвести "0 или -1", поэтому "0 или 1" больше соответствует цели прямого обращения к возможностям машины. Реализация языка "0 или -1", такого как Forth, будет использовать последовательность, подобную <? negate, для которого хороший код может быть создан очень просто.

Поток управления внутри определений

Стандартные Forth-слова BEGIN AGAIN UNTIL AHEAD UNTIL AHEAD IF THEN CS-ROLL доступны в PAF и полезны для построения структурированного потока управления, такого как if ... then ... elsif ... then ... else ... end.

Хотя можно построить любой поток управления с помощью этих слов [Bad90], если вы хотите реализовать метки и переходы, проще использовать метки и переходы.

Следовательно, PAF (в отличие от Forth) также предусматривает:

  • слова L:name, которые определяет метки
  • слова goto:name, которые осуществляет переход на метку.

PAF также поддерживает непрямые переходы:

  • `name/tag выдает адрес метки name на стек
  • goto/tag переходит на метку, лежащую на вершине стека.

Тег (tag) указывает, какие переходы могут переходить на какие метки; программа PAF не должна переходить на адрес метки, сгенерированный с другим тегом. Например, C-компилятор C, предназначенный для PAF, может использовать отдельный тег для каждого оператора switch и имеющихся там меток.

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

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

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

PAF определения и PAF вызовы

Определение, в котором компилятор может свободно определять интерфейс вызова, определяется классическим способом Forth:

: name ... exit ;

Конец определения не делает неявный возврат (в отличие от Forth), поэтому вам нужно вернуться явно, написав EXIT.

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

Мы можем взять адрес определения с помощью `name:tag и вызывать его с exec.tag с оптимизацией хвостового вызова как jump.tag. Тэг указывает, какие вызовы могут вызывать определение.

Эффекты стека всех определений, адреса которых взяты с тем же тегом, должны быть совместимы. То есть, должен быть один эффект стека, который описывает все из них, например: ( x x -- x ) - это валидный эффект стека и для + и для DROP, (хотя минимальный эффект стека для DROP это ( x -- ) так что + и DROP имеют совместимые стековые эффекты).

Использование тегов здесь имеет две цели:

  • информирует компилятор PAF о потоке управления;
  • сообщает об эффекте стека косвенного вызова (в то время как компилятор обычного Forth предполагает, что EXECUTE может вызвать что угодно и иметь какой-угодно эффект стека). Или, наоборот, в связи с правилом глубины стека: теги допускают различные эффекты стека для косвенно вызываемых определений с разными тегами; без тегов, все косвенно вызываемые определения должны иметь одинаковый эффект стека.

ABI определения и ABI вызовы

Нам нужно явно указать эффект стека как сигнатуру определения или вызова ABI. Синтаксисом такой сигнатуры является [xr]*-[xr]*, где x указывает аргумент ячейки (машинное слово/integer/адрес), а r - аргумент с плавающей запятой; буквы до тире указывают параметры, а буквы после тире - результаты. Разделение на x и r отражает деление на регистры общего назначения и регистры с плавающей запятой на реальных машинах и роль, которую эти регистры играют во многих соглашениях о вызовах.

Определение, соответствующее вызывающему соглашению определяется с помощью abi:sig name. Sig указывает эффект стека и указывает соответствие между параметрами ABI и элементами стека PAF. Эта сигнатура не является достаточно избыточной, например, рассмотрим разницу между следующими определениями:

abi:x-x  id   exit ;

и

abi:-    noop exit ;

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

Вы можете вызвать ABI-совместимую функцию с помощью abi.name.sig, где name - это имя функции (которая может быть определением PAF или функцией, написанной на другом языке и динамически или статически связанной с программой PAF). Подпись определяет, сколько и какие типы элементов стека передаются вызываемым функциям, и какой тип возвращаемого значения (если есть), чтобы push-ить его на стек.

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

Вы можете взять адрес ABI функции с именем abi`name и вызвать его с помощью abi-exec.sig. Нет никаких хвостовых вызовов для функций ABI, потому что мы не можем гарантировать, что хвостовые вызовы могут быть оптимизированы во всех соглашениях о вызовах.

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

Обсуждение определений и вызовов

Почему существуют два типа определений и два вида вызовов? Определения и вызовы PAF позволяют реализовать различные структуры управления, такие как backtrackng через хвостовые вызовы [Ste77]. Они также позволяют компилятору использовать гибкие и, возможно, более эффективные интерфейсы вызовов, чем соглашение о вызове ABI.

С другой стороны, ABI позволяют взаимодействовать с другими языками и использовать динамически или статически связанные двоичные библиотеки, включая callback-и, и использовать PAF для создания таких библиотек (например, в качестве плагинов).

Исключения

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

Отсутствующие возможности

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

Сборка мусора

Ряд виртуальных машин, например Java VM, поддерживают сборку мусора. Однако эта функция значительно ограничивает то, что можно сделать. В частности, представления данных ограничены, и невозможно реализовать "неуправляемые" (unmanaged) языки или использовать другое представление данных для языка сборки мусора (например, представление Java VM значительно отличается от того, как большинство систем Prolog или Lisp представляют свои данные).

Даже C–, назначение которого - быть переносимым языком ассемблера для имеющих сборку мусора языков, не реализует сборку мусора, а оставляет ее для реализации на языке более высокого уровня, поскольку это оставляет полную свободу в том, как внедрять данные и сборку мусора в язык более высокого уровня [JRR99].

Типы

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

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

Можно задаться вопросом о "отсутствии" некоторых операций в PAF; например, таких как <? U<? , но только =? + - *. Причина в том, что на целевых для PAF машинах, эти операции являются идентичными для знаковых и беззнаковых чисел.

Отладчик

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

SIMD

Поддержка наборов инструкций SIMD, таких как SSE, AVX, AltiVec и.т.д., не планируется, главным образом потому, что даже некоторые языки более высокого уровня нуждаются в таких функциях. Они могут быть добавлены позже, если возникнет необходимость.

PAF vs Forth

Ограничения на обработку стека в PAF дают новое представление о Forth, и мы более подробно рассмотрим это в этом разделе.

Влияние на реализацию

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

В отличии от PAF, Forth должен иметь отдельную область памяти и указатель стека для каждого стека, и пока элементы стека могут храниться в регистре для большей части кода, есть несколько слов (в частности, EXECUTE) и шаблонов кода (несбалансированные эффекты стека на соединении потоков управления), которые заставляют перемещать элементы стека в память и обычно также вызывают обновление указателя стека.

Это свойство Forth исключается из PAF, требуя сбалансированных эффектов стека на объединении потоков управления (см.поток управления внутри определений) и заменяя EXECUTE на exec.tag (см. PAF определения и PAF вызовы); все адреса определения, возвращенные для определенного тега, необходимы для совместимых эффектов стека, поэтому exec.tag имеет статически определенный эффект стека.

Влияние на программы

Влияние на реальные программ относительно невелико: в большинстве случаев у кода Forth есть сбалансированные эффекты стека для потока управления, и большинство случаев ` и EXECUTE могут быть преобразованы в их тегированные варианты, поскольку программисты сохраняют глубину стека статически определяемой, чтобы сохранить код понятным.

Однако есть случаи, когда ограничения не так просто соблюдать. Например, объектно-ориентированные пакеты в Forth используют EXECUTE для слов с произвольными эффектами стека. Программы, использующие эти слова, также имеют статический эффект стека, но он присутствует только на более высоком уровне; например, если для каждого селектора методов используется отдельный тег (и отдельный exec.tag), типичное использование соответствует ограничению, но в большинстве объектно-ориентированных пакетов выполняется только одно EXECUTE.

Ниже показан код для этого примера: вариант Forth определяет определяющий селектор слов, а затем селекторы определяются этим определяющим словом; напротив, вариант PAF определяет селекторов напрямую (и имеет довольно много повторов), каждый со своим тегом.

\ Forth
: selector ( offset -- )
    create ,
  does> ( ... o -- ... )
    @ over @ + @ execute ;

1 cells selector foo
2 cells selector bar

\ PAF
: foo ( ... o -- ... )
    dup @ 1 cells + @ jump.foo ;
: bar ( ... o -- ... )
    dup @ 2 cells + @ jump.bar ;

Если вы хотите определить определяющее слово для селекторов методов, как вы обычно делаете в Forth, тег должен быть передан как параметр времени определения между участвующими определяющими словами. Эта поддержка программирования на более высоком уровне не требуется внутри PAF (там мы оставляем такое метапрограммирование на язык более высокого уровня), но если мы хотим передать идею тега обратно в Forth, нам придется добавить такие вещи.

Компиляция Forth в PAF

Перевод Forth-кода, который не является кодом PAF в код PAF, может быть поучительным. В качестве примера мы используем другой вариант кода, приведенного выше.

Этот вариант определяет селектор как определение двоеточия, а не с помощью does>; для целей презентации мы оставляем определяющий селектор слов и определяем селектор foo напрямую, а не с помощью селектора foo:

: do-selector ( .. obj m-off -- .. )
    over @ + @ execute ;

: foo ( .. obj -- .. )
    1 cells do-method ;

: bar ( -- )
    1 2 my-obj foo . ;

Это не PAF из-за EXECUTE, который может иметь произвольный эффект стека. Мы переводим этот кадр в PAF jump с тегом; мы решили что соглашение о вызове PAF для xts с этим тегом (–). То есть, любые эффекты Forth-стека должны быть переведены на обращения к явно реализованному стеку в памяти PAF. Указатель стека стека данных реализуется как значение sp.

Сам Do-selector должен хранить объект obj стека в этом явном стеке, но прямой и косвенный вызывающие вызовы do-selector обычно также должны получить доступ к этому явному стеклу. В нашем примере бар должен сделать push двух элементов в явном стеке и вытащить один элемент из явного стека:

0 value sp

: do-method
    over sp cell- tuck ! to sp
    swap @ + @ jump.forth ;

: foo
    1 cells jump:do-method ;

: bar
    sp cell- 1 over !
    cell- 2 over !
    to sp
    my-obj foo
    sp dup @ swap cell+ to sp
    jump:. ;

Аналогично нужно было бы реализовать стек с плавающей точкой. Некоторые люди хотели бы расширить стандарт Forth с помощью манипуляций с адресами возврата. Можно также сделать перевод с такого расширенного Forth на PAF, и он показывает, насколько дорога эта функция. Глядя на часть do-метода примера выше:

0 value sp

0 value rp

: thunk1
    exit ;

: do-method
    over sp cell- tuck ! to sp
    swap @ + @
    rp cell- to rp ’thunk1:forth rp !
    exec.forth rp cell+ to rp
    jump:thunk1 ;

Указатель стека возврата должен быть явным (как rp). Вместо того, чтобы переводить выполнение в косвенный хвостовой вызов (jump.forth), мы должны сначала сохранить обратный адрес `thunk1:forth в явном стеке возврата, а затем использовать косвенный не-хвостовой вызов exec.forth, а затем drop-нуть возврат адрес возврата из явного стека возвратов, а затем продолжить с остальной частью определения (thunk1), который просто возвращается в этом случае.

Связанные работы

Мы обсудили C, LLVM, C– и Vcode/GNU Lightning в разделе предыдущие работы.

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

  • Python-система PyPy использует ограниченную форму Python, называемую RPython, как промежуточный язык низкого уровня [AACM07].
  • asm.js является подмножеством JavaScript, который настолько ограничен, что он может служить переносимым языком ассемблера.
  • PreScheme является низкоуровневым подмножеством Scheme, используемым в качестве промежуточного языка для реализации Scheme48 [KR94].

Во всех этих случаях базовый язык намного более высокоуровневый, чем у Forth, и гораздо более растягивается создание низкоуровневого подмножества, чем для Forth.

Machine Forth (который превратился в colorForth) - это простой вариант Forth, созданный Чарльзом Муром, изобретателем Forth. Он тесно соответствует инструкциям его Forth-процессоров, но он также написал реализацию для IA-32, которая создает собственный код. Компилятор IA-32 очень прост, в основном просто расширяя слова до коротких машинных кодовых последовательностей.

Он не отображает элементы стека за верхний стек для регистров, но сгенерированный код относительно компактен; это отражает тот факт, что Machine Forth находится близко к машине, включая IA-32.

Вывод

PAF - это подмножество / диалект Forth, который предназначен как переносной язык ассемблера. Основным вкладом PAF являются:

  • Теги, указывающие, какие косвенные ветвления могут достигать каких меток и какие косвенные вызовы могут вызывать какие определения. По сравнению с общими непрямыми ветвями и вызовами, это дает больше свободы для использования стека фронтенда и для аллокации регистров компилятора PAF. Метки нуждаются в меньшем объеме усилий по внедрению и дают лучшие результаты, чем попытки добиться того же результата посредством анализа программ.
  • Определения и вызовы разделяющиеся на те, которые соответствуют соглашению ABI/соглашению о вызовах платформы, и другие, для которых компилятор может использовать любой вызывающий интерфейс (разные для разных наборов вызывающих и вызываемых процедур). Это позволяет оптимизировать хвостовые вызовы (в отличие от соглашений о вызове ABI), что, в свою очередь, означает, что мы можем использовать вызовы как примитив для произвольных структур управления (например, для сопрограмм).
  • Ограничения (по сравнению с Forth) на использование элементов стека позволяют иметь статическую связь между элементами стека и регистрами для всех программ и избегать необходимости отдельного указателя стека и области памяти для каждого стека. Это подчеркивает, какие возможности Forth дороги и где они используются.

Ссылки

[AACM07] Davide Ancona, Massimo Ancona, Antonio Cuni, and Nicholas D. Matsakis. RPython: a step towards reconciling dynamically and statically typed OO languages. In Pascal Costanza and Robert Hirschfeld, editors, DLS, pages 53–64. ACM, 2007.

[Bad90] Wil Baden. Virtual rheology. In FORML’90 Proceedings, 1990.

[Eng96] Dawson R. Engler. vcode: A retargetable, extensible, very fast dynamic code generation system. In SIG-PLAN ’96 Conference on Programming Language Design and Implementation, pages 160–170, 1996.

[JRR99] Simon L. Peyton Jones, Norman Ramsey, and Fermin Reig. C–: a portable assembly language that supports garbage collection. In International Conference on Principles and Practice of Declarative Programming, September 1999.

[KR94] Richard A. Kelsey and Jonathan A. Rees. A tractable Scheme implementation. Lisp and Symbolic Computation, 7(4):315–335, 1994.

[LA04] Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Code Generation and Optimization (CGO), pages 75–88. IEEE Computer Society, 2004.

[Ste77] Guy Lewis Steele Jr. Debunking the “expensive procedure call” myth or procedure call implementations considered harmful or lambda: The ultimate goto. AI Memo 443, MIT AI Lab, October 1977

Orig: http://www.complang.tuwien.ac.at/anton/euroforth/ef13/papers/ertl-paf.pdf

Яндекс.Метрика
Home