Трансляторы Си в Форт

Total Vacuum

Total Vacuum писал(а):

Hishnik писал(а):

Я пробовал inline, правда, давно было, с соответствующим эффектом относительно процессоров. Выигрыш 1-3 процента, если специально делать тесты с множеством итераций. Простые слова действительно удобно разворачивать прямо в коде. Как сейчас это решается современными ядрами с предсказанием переходов и спекулятивным исполнением - интересный вопрос. Есть соображение, что эффект от разворачивания будет съеден.

Точно сейчас не помню (завтра постараюсь прогнать в ПЛИС в двух вариантах), но в Форт-процессорах прирост был раза в 2, если не больше. Возможно, из-за специфики системы команд, когда при коротком машинном слове вызов каждого незаинлайненного слова съедает несколько тактов на call, плюс такт на ret, плюс стек возвратов не резиновый. И почти всегда прошивка с инлайнами не только быстрее, но и меньше. Для широкого машинного слова, вероятно, эффект от инлайна будет небольшим. Более того, под ARM и Thumb у меня иногда даже медленнее прошивка с инлайнами получалась. Под x86 всегда прирост скорости получался от инлайна.

Для некоторых моих подопытных время выполнения 16384 итераций Dhrystone (в секундах) и размер прошивки (в нибблах) без инлайнов/с инлайнами:

Код:

f41   9.396 / 6.226 = 1.51   29519 / 29241 = 1.01
f42   8.889 / 5.571 = 1.60   29498 / 29209 = 1.01
f43   7.560 / 4.987 = 1.52   21535 / 20678 = 1.04
f44   7.021 / 4.471 = 1.57   21216 / 20358 = 1.04
f45   9.897 / 5.976 = 1.66   30116 / 29516 = 1.02
f61   3.717 / 1.858 = 2.00   14436 / 14671 = 0.98

Т.е. прирост скорости раза в 1.5-2, а вот размер прошивки плюс/минус примерно тот же самый.

Total Vacuum

Параметры/результаты типа struct тоже заработали.
Придумалась такая небольшая хитрость. Транклюкатор незаметно для программиста (пока никто не видит) превращает код

Код:

typedef struct {int x; int y; int color;} point;
point getpoint (int x, int y, int color) {...}

в

Код:

void getpoint (point *result, int x, int y, int color) {...}

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

Hishnik

Не будет ли тут путаницы с ситуациями, когда от функции будет явно требоваться:
1. Вернуть указатель на буфер со структурой.
2. Принять адрес буфера для результата в явном виде.
3. ... ? ...
Возвращать структуру "по значению", конечно, выглядит громоздко, это да.

Total Vacuum

Должно работать правильно, но, в любом случае, еще проверять. Если возвращаем указатель на структуру, то это по своей сути обычное целое число, там вопросов нет. Когда явный адрес буфера в качестве параметра, там тоже никогда не было проблем. А вот если возвращаем struct в качестве результата, там компилятор резервирует память под выходной буфер и добавляет адрес этого буфера (скрытый параметр) в прологе перед вызовом такой функции, а в самой вызываемой функции перед ret чистит стек от всех параметров (кроме скрытого) и дописывает n memcpy

Код:

#include "printf.h"

typedef struct {int x; int y;} point;

point p, pts[10], *ptr;

point getpoint () {
   point p;
   p.x = 1;
   p.y = 2;
   return p;
}

point * getptr () {
   return &pts[1];
}

void setpoint (point * p) {
   p->x = 3;
   p->y = 4;
}

void print (point p) {printf("(%X,%X)", p.x, p.y);}

void main () {
   pts[1].x = 5;
   pts[1].y = 6;
   p = getpoint(); print(p);
   ptr = getptr(); print(*ptr);
   setpoint(&p);   print(p);
                   print(0?p:pts[1]);
                   print(1?p:pts[1]);
   p = pts[1];     print(p);
}

дает выхлоп

Код:

(0001,0002)(0005,0006)(0003,0004)(0005,0006)(0003,0004)(0005,0006)

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

Total Vacuum

В природе есть так называемые соглашения о вызовах (calling conventions), которые определяют порядок вызова подпрограмм в части передачи аргументов (стек/регистры/..., слева направо/справа налево), очистки стека (чистит вызывающая/вызываемая подпрограмма), передачи результата (стек/регистры/...) и т.д. Их тьма, в разных ОС/компиляторах/процессорах/языках программирования могут быть свои варианты: cdecl, stdcall, pascal, fastcall и т.д. Я как бы знал, что эти варианты есть, но особо вопросом не интересовался, а делал как удобнее и проще.
Например, fastcall по максимуму задействует регистры при передаче аргументов. В win используется stdcall, агрументы передаются через стек в обратном порядке (справа налево), а стек чистит вызываемая подпрограмма. Компиляторы Си (в т.ч. GCC) чаще всего рожают cdecl, в стеке прибирает уже вызывающая подпрограмма, ну а порядок аргументов такой же (обратный).
И в педивикии пишут, что обратный порядок аргументов как нельзя лучше подходит для функций с переменным числом параметров, т.к. на вершине стека оказывается первый аргумент. В англоязычной не так категорично, но тоже смысл в том, что для функций с переменным числом параметров без вариантов: либо первый аргумент в качестве опорного на вершине стека, либо все необязательные параметры через массив. И у невозможности(?) очистки стека вызывающей подпрограммой (а это, между прочим, лишние команды при каждом вызове подпрограммы), подозреваю, отсюда же ноги растут. Ну вот не знает вызываемая подпрограмма с переменным числом параметров, сколько аргументов в нее запихано при каждом вызове, поэтому и стек за собой почистить не может.
А если я не хочу обязательный первый аргумент? И что мне мешает сообщить в такую функцию фактическое количество необязательных параметров при каждом вызове, чтобы дать ей возможность самостоятельно почистить стек от аргументов?
Собственно, сейчас сделано не как в cdecl, а с точностью до наоборот: параметры передаются в прямом порядке (слева направо), стек чистит вызываемая подпрограмма, а в прологе к вызовам функций с переменным числом параметров автоматически добавляется еще один аргумент (фактическое число необязательных параметров). И никаких проблем с очисткой стека в вызываемой подпрограмме и реализацией функций с переменным числом параметров: прекрасно работает не только printf (char * fmt, ...), но даже такое, которое в других компиляторах просто не скомпилируется, ибо в sum нет "обязательного" первого параметра:

Код:

extern void printn (int n);
extern int va_count ();
extern int va_arg (int n);
int sum (...) {
   int s = 0, i = va_count();
   while (i--) s += va_arg(i);
   return s;
}
void main () {
   printn(sum(1,2,3));
   printn(sum(1,1,1,1));
   printn(sum());
}

Код:

000600040000

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

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

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

tsdima

Total Vacuum писал(а):

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

Ну и все-таки хотелось было бы понять историю вопроса с соглашениями о вызовах.

Если складывать аргументы в стек в обратном порядке, то первый аргумент будет на стеке первым. Да и в памяти они будут лежать в "прямом" порядке. Вот и вся история.

Total Vacuum

tsdima писал(а):

Если складывать аргументы в стек в обратном порядке, то первый аргумент будет на стеке первым.

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

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

tsdima писал(а):

Да и в памяти они будут лежать в "прямом" порядке.

Это да, но при условии, что стек растет вниз. Соглашусь, что в этом может быть какой-то тайный смысл, но пока не вижу сценариев использования такого прямого порядка аргументов в памяти. А если говорить про форт-процессоры (и не только про них), то там вообще стек данных может быть аппаратный (например, на регистрах), либо лежать в отдельной памяти, которая не имеет ничего общего с сегментом данных. Плюс иногда стек доступен для чтения/записи только на уровне push/pop.

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

Именно из-за того, что с добавлением каждого нового аргумента стек сползает. Даже для примитивного случая

Код:

void test2 (int x) {test (x,x,x);}

получим

Код:

: test2 <enter>
   dup ( arg0 )
   over ( arg1 )
   2 pick ( arg2 )
   test
drop <leave> ;

В идеале тут, конечно, должно быть что-то вроде

Код:

: test2 <enter> dup dup dup test drop <leave> ;

или даже

Код:

: test2 dup dup test ;

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

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

tsdima

Total Vacuum писал(а):

зачем нужно, чтобы первый аргумент всенепременно лежал на вершине стека.

printf и иже с ним. Первый аргумент (или второй в sprintf/fprintf), т.е. тот самый формат, описывает количество и тип остальных аргументов. Если бы он лежал глубоко в стеке, то как понять, сколько там аргументов и какой он сам по счёту? А так он первый, остальные используются в процессе обработки формата в том же порядке, как и в строке формата.

Total Vacuum

tsdima писал(а):

Первый аргумент (или второй в sprintf/fprintf), т.е. тот самый формат, описывает количество и тип остальных аргументов. Если бы он лежал глубоко в стеке, то как понять, сколько там аргументов и какой он сам по счёту?

Ну хорошо, вот мини-printf просто для иллюстрации:

Код:

extern void printc (char c);
extern void printn (int n);
extern void prints (char * s);

extern int va_count ();
extern int va_arg (int n);

void printf (char * fmt, ...) {
   char * p = fmt;
   int n = 0;
   char c;
   while (c = *p++) {
      if (c == '%') {
         switch (c = *p++) {
            case 'c': printc(va_arg(n++)); break;
            case 'X': printn(va_arg(n++)); break;
            case 's': prints(va_arg(n++)); break;
            default:  printc(c) ;
         }
      }
      else printc(c);
   }
}

void main () {
   printf("%c%X, %s%c",'H',0xE110,"WORLD",'!');
   printf("hello, world!");
}

выводит

Код:

HE110, WORLD!
hello, world!

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

Код:

"%c%X, %s%c" 'H' 0xE110 "WORLD" '!' 4 printf
"hello, world!" 0 printf

Здесь 4 и 0 в прологе - это как раз фактическое число необязательных параметров.

tsdima писал(а):

А так он первый, остальные используются в процессе обработки формата в том же порядке, как и в строке формата.

Именно! Т.е. при таком подходе мы обязаны перебирать все параметры строго в определенном порядке. И обязаны иметь либо строку-формат, либо явно записанное руками количество (а если ошиблись при ручном подсчете?) необязательных параметров (см. int add(int n,...) на прошлой странице). Опять же, фактическое количество необязательных параметров может быть заранее неизвестно (придется всю форматирующую строку просканировать, чтобы узнать). Такое вот закостенелое и не очень удобное, на мой взгляд, решение, а у меня чуть гибче. Имею возможность обращаться (причем, неоднократно) к каждому из необязательных параметров в абсолютно произвольном порядке. И формат или количество указывать не обязан, если, например, все параметры однотипные (см. int sum(...) на этой странице). Да и фактическое число необязательных параметрова всегда известно (int va_count()).

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

Hishnik

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

Total Vacuum

Hishnik писал(а):

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

Как ни странно, не приспособлены стековые Форт-процессоры и не менее стековые Форты для работы с кадром стека от слова совсем. Ну не умеют Форты/Форт-процессоры писать в стек на произвольную глубину, да и сам стек данных может быть аппаратным, а посему ограниченным по размеру и возможности произвольного доступа. Потому-то и нет стекового кадра в чистом виде, хотя аргументы/результаты (в стеке) и локальные переменные (в буфере) по отдельности есть.
В общем случае для неразрушающего чтения произвольного элемента стека есть всего 3 варианта: dup, over и n pick. Поэтому какое-то преимущество (в теории) может быть у двух верхних элементов. Но как только начинает выполняться новый оператор или вычисляться выражение, стек сразу же начинает наполняться результатами вычисления промежуточных выражений, поэтому оба верхних элемента тут же перестают быть верхними и теперь видны только через pick. И какая тогда разница, насколько глубоко аргументы сидят в стеке при входе в функцию, если они почти никогда не будут наверху во время выполнения кода этой функции?
Поэтому от "постоянной корректировки" положения аргументов в стеке никуда не деться, если мы говорим про стековые процессоры. Это в x86 есть bp/sp для для работы с кадрами стека: выставили и пляшем от них в любую сторону на величину нужного нам смещения. А в Форт-процессорах, увы, ничего похожего нет даже близко.
Опять же, количество необязательных аргументов передается только для функций с переменным числом параметров. Эти функции нужны достаточно редко, ну разве что printf. При этом, если и будет какой-то проигрыш в скорости для таких функций из-за необходимости добавить к смещению какого-то аргумента еще одну константу, то он будет пренебрежимо мелким в масштабах, например, временного интервала между отправками символов в uart. Ну а если нужен быстрый код, для этого есть функции с фиксированным числом параметров, inline-вставки Форт-кода в сишных функциях или функции, которые реализованы на Форте (и/или ассемблере) целиком.

Hishnik

Если рассматривать "чистый стек", то да, есть ограничение по доступным значениям. При эмуляции такого нет.... но и в схемотехнике тоже вобщем-то нет ограничения на доступ. Другое дело - как это адресовать. В "чистом" форт-процессоре достаточно иметь регистр глубины стека, который однозначно определяет физические адреса регистров. Но если уж надо поработать с кадром параметров, то можно задавать и абсолютные адреса, и смещения относительно текущей вершины стека (и даже относительно вершины, запомненной на момент входа в подпрограмму). Тут есть две толстенькие тонкости - смещения нужно записывать в команде, а значит, она будет расширяться. Вторая тонкость - операнды нельзя читать одновременно с командой, потому что они уже не на вершине стека (без вариантов), а, возможно, на каком-то смещении, которое мы узнаем после фронта, переводящего pc -> cmd. Правда, при реализации стека на FF или LUTRAM остается вариант комбинационного чтения. Так что в целом есть варианты совмещения стека и регистров (со стековым кадром для параметров).

Total Vacuum

Да, безусловно, аппаратно стековый кадр (или кадровый стек

) можно поддержать, предусмотрев нужный функционал в архитектуре и системе команд. Но когда начинал делать компилятор, исходил из того, что нужно не только максимально простое, но и в каком-то смысле универсальное решение, которое должно работать в т.ч. и в самых запущенных случаях, а именно:
- небольшой стек (для локальных переменных в нем просто не хватит места);
- запись в стек только через вершину, прочие ячейки недоступны для записи (если локальные переменные разместить в стеке, не сможем менять их значение);
- примитивная система команд (отдельным командам для работы с кадром стека и сложным режимам адресации здесь не место).
Все написанное выше относится не только к моим Форт-процессорам, но и к разномастным Фортам: если не лезть в ~~бутылку~~ ассемблер и кишки каждой конкретной Форт-системы, то в арсенале у нас лишь небольшое количество милых сердцу каждого фортера слов (dup/drop/...), а стек в общем случае непригоден для хранения локальных переменных.
Да, можно было бы программно реализовать стек данных, чтобы в нем было место и для локальных переменных. Но зачем эти гири на ногах Форт-процессору? Через аппаратный стек ему считать быстрее. Да и какой смысл в точности повторять реализацию стекового кадра из условного x86? Главное, что есть агрументы/результаты/локальные переменные, а как оно там под капотом сделано - не принципиально.

Hishnik

В целом да, тут две крайности. Можно последовательно воспроизводить все, "как у всех", постоянно натыкаясь на особенности стека. Можно принципиально не делать ничего "как у всех". Истина где-то посередине, как обычно. Удобство стековой модели для ПЛИС в компактном коде, и можно просто учитывать эту особенность, не создавая много параметров специально. А оно часто так и оказывается в простых приложениях, в ПЛИС в основном нужно манипулировать регистрами IP-ядер, и выжимать максимум из процессора совершенно ни к чему.

Total Vacuum

Минутка юмора

Когда начинал делать транслятор, за основу взял грамматику из стандарта C89.
Но при этом что-то сразу исключил:
- триграфы;
- определения функций в старом стиле K&R;
А что-то сделал не совсем стандартно:
- возможность объявления функций с переменным числом параметров в т.ч. и без обязательного первого (первых) параметра, т.е. вида void f (...);
- поддержка в т.ч. двоичных чисел с префиксом 0b;
- функции вида f() считаются функциями без параметров, а не функциями с неопределенным числом параметров;
- переменные могут объявляться в любом месте блока, а не только в его начале;
Ну и сразу заложил по мелочи что-то из того, что может пригодиться в будущем (например, inline).

Решил глянуть, что там сейчас стандартописатели напридумывали. После стандарта C89 были C99, C11, C17, ну и вроде как самый свежий на сегодня C23.
Понятное дело, что в следующих стандартах добавились inline и возможность объявления переменных в любом месте блока.
И будете смеяться, но в C23:
- убрали функции в стиле K&R и триграфы;
- обязательные параметры в вариадических функциях теперь не требуются, а в макросе va_start второй параметр (как раз тот самый обязательный параметр, про который ломали копья не так давно в этой ветке) не является обязательным, а если даже и указан, то игнорируется;
- добавили поддержку двоичных чисел с префиксом 0b (наконец-то!);
- и да, функции f() - это теперь официально функции без параметров.

Вот и выходит, что пишешь вроде как C89, а получается почему-то C23

Трансляторы Си в Форт

Кто сейчас на конференции