Работа с представлением GENERIC в gcc - часть 2

Вступление

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

Создание main

Немного теории

Представление GENERIC по сути является направленным ациклическим графом. В этом представлении всё является узлом дерева заданного типа с определённым значением. Узлом дерева будут являться константы, идентификаторы, типы, выражения и т.п. Схематично граф можно было бы представить следующим образом: 

                   -----------------
                  /| Тип выражения |
-----------------/ -----------------
|  Выражение_1  |
-----------------\ -----------------
       |          \| Идентификатор |
       |           -----------------
       |
-----------------  -----------------
|  Выражение_2  |--|    Аргумент   |
-----------------  -----------------
       |         
       |           -----------------
       |          /|   Операнд_1   |
-----------------/ -----------------
|  Выражение_3  |
-----------------\ -----------------
                  \|   Операнд_2   |
                   -----------------

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

Узлом дерева является структура tree, каждый объект которой обладает своим типом. Типом может быть объявление, определённая языковая конструкция, служебные узлы для поддержания структуры представления. Полный список всех типов можно посмотреть только в каталоге с объектными файлами, т.к. он создаётся на основе большого количества макросов. При желании можно найти тип данных enum tree_code в файле tree-core.h, а оттуда уже продолжить увлекательный поиск списка возможных типов узла.

Основной функцией для создания узлов служит функция build<N>, где <N> - количество аргументов у узла. При работе с основными конструкциями эта цифра не будет превышать значение 3. Первым аргументом функций build<N> всегда будет идти тип узла, вторым - тип выражения. Тип выражения - это тип в терминах внутреннего представления gcc, близкий к языковому типу. Например, таким типом может быть integer_type_node или void_type_node. На основе этих типов будет проверяться корректность построения графа. Все последующие аргументы являются операндами создаваемого выражения, количество которых будет соответствовать числу <N>.

Существует вариант функции построения вида build<N>_loc. В этой функции первым аргументом будет идти положение узла в исходном коде. В нашем случае у нас исходного кода не существует, поэтому положением всегда будет указываться UNKNOWN_LOCATION. Хотя мы не будем использовать этот тип функций напрямую, существуют другие функции создания узлов, которые требуют указывать положение в исходном коде явным образом.

Объявление функции int main (void)

Перейдём непосредственно к практике создания программы. Весь код мы будем добавлять в функцию x_langhook_parse_file, на текущий момент эта функция должна быть пустой. Первым шагом будет являться создание объявления функции main. Объявление функции состоит из типа возвращаемого значения, типов аргументов и её символьного имени. Посмотрим как выполнить создание объявления функции в терминах GENERIC:

Код в gcc Аналог на Си GENERIC
//--------------------- Пример 1

tree * main_params = new tree[1]; // Массив, содержащий параметры
// У нас всего один параметр типа void
main_params[0] = void_type_node;

// Создаём тип функции "int (void)"
tree main_fndecl_type = build_function_type_array (
    integer_type_node, // Тип возврата
    1,                 // Количество аргументов
    main_params);      // Массив с типами аргументов
delete[] main_params;

// Создаём объявление функции "int main(void);"
tree main_fndecl = build_fn_decl(
    "main",            // Символьное имя функции
    main_fndecl_type); // Тип функции

// Говорим что это объявление используется и его нельзя удалять
DECL_PRESERVE_P (main_fndecl) = 1;
// Функция main не должна иметь признака external
DECL_EXTERNAL (main_fndecl)   = 0;

// <-------------- Сюда будем добавлять код
 		int main(void);
 
                   --------------
                   |   "main"   |
                  /--------------
-----------------/
| FUNCTION_DECL |\ --------------
----------------- \| int (void) |
                   --------------

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

Далее при помощи функции build_function_type_array создаётся непосредственно тип функции с указанием возвращаемого значения. Само объявление функции создаётся вызовом build_fn_decl.

Для доступа к полям узла дерева tree используются макросы. Применимость макросов зависит от типа узла и не всегда контролируется на этапе компиляции. Если макрос имеет постфикс _P, то обычно он ведёт себя как предикат. Но разработчики гарантируют что его всегда можно сравнивать с 0. В нашем случае мы при помощи макросов задали два поля - запретили удаление узла (если компилятор посчитает что узел бесполезен, то автоматом его удалит) и убрали признак внешней функции, который выставляется по умолчанию.

Определение функции main

Просто создать объявление функции недостаточно для получения минимально рабочего исполняемого файла - для функции нужно тело. Посмотрим как оно создаётся:

Код в gcc Аналог на Си GENERIC
//--------------------- Пример 2

// Создаём блок кода
tree body                  = make_node(BLOCK);
// Указываем охватывающее определение
BLOCK_SUPERCONTEXT (body)  = main_fndecl;
// Помечаем что попадаем в этот блок при входе в функцию
DECL_INITIAL (main_fndecl) = body;

// Создаём узел, в котором объявляется результат возврата функции
tree resdecl = build_decl (
  UNKNOWN_LOCATION,   // Положение в исходном коде
  RESULT_DECL,        // Тип узла
  NULL_TREE,          // Узел с именем переменной
  integer_type_node); // Тип выражения

// Наше объявление находится в контексте функции
DECL_CONTEXT (resdecl)    = main_fndecl;
// Помечаем объявленную переменную результатом
DECL_RESULT (main_fndecl) = resdecl;

// <-------------- Сюда будем добавлять код
 		int main()
{
}
 
                   --------------
                   |   "main"   |
                  /--------------
-----------------/
| FUNCTION_DECL |\ --------------
----------------- \| int (void) |
        |       \  --------------
        |        \ ---------------
----------------- \| RESULT_DECL |
|     BLOCK     |  |    int      |
-----------------  ---------------

Тело функции должно содержать в себе несколько элементов. Во-первых ему необходим лексический блок. Это специальный узел типа BLOCK, к которому привязывается список выражений и цепочка определений. У каждого лексического блока есть ссылка на охватывающий блок, задающийся через макрос BLOCK_SUPERCONTEXT. В нашем случае охватывающим блоком будет непосредственно определение функции. Самой функции тоже надо указать лексический блок, с которого начинается её работа. Делается это через макрос DECL_INITIAL.

Ещё одним узлом, который необходим функции для работы является узел объявления возвращаемого значения. Этот узел имеет специальный тип RESULT_DECL и записывается отдельным полем в объявление самой функции при помощи макроса DECL_RESULT. Самому узлу также необходимо указать контекст, в котором он работает при помощи макроса DECL_CONTEXT.

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

// <-------------- Сюда будем добавлять код

//--------------------- Пример 2 (окончание)

// Преобразуем из GENERIC в GIMPLE
gimplify_function_tree (main_fndecl);

// Добавляем это в граф (видимо граф вызовов)
cgraph_node::finalize_function (main_fndecl, true);

При помощи этих двух функций мы запускаем дальнейшую компиляцию функции и подвязываем её к внутренним структурам gcc. Далее нужно просто пересобрать компилятор и запустить получившийся исполняемый файл:

$ ${GCC_PATH}/bin/bin/gccx t.x -fdump-tree-all

$ ./a.out

$ echo $?
0

До тех пор пока мы не научимся создавать вызовы функций, проверять работоспособность кода будем по возвращаемому значению (можно заметить что пока что мы не научились его менять). Видно что программа вернула 0, как и планировалось. Также можно заметить добавление интересной опции компиляции -fdump-tree-all. Если мы посмотрим в рабочий каталог, то увидим много созданных файлов с текстовым видом промежуточного представления на различных фазах. Сейчас нас интересует только содержимое с первой сброшенной фазы:

$ cat t.x.005t.gimple
main ()
{
  GIMPLE_NOP
}

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

Выражение возврата

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

Для начала создадим простой код для конструкции return 0;:

Код в gcc Аналог на Си GENERIC
//--------------------- Пример 3

// Список выражений
tree stm_list = alloc_stmt_list ();

// Создаём константу
tree ret_const_decl = build_int_cst_type (integer_type_node, 0);
// Присваиваем значение константы переменной возврата
tree ret_assign     = fold_build2 (
    MODIFY_EXPR,     // Тип узла
    void_type_node,  // Тип выражения
    resdecl,         // Цель присваивания
    ret_const_decl); // Присваиваемое значение

// Здесь создаём узел return
tree return_stm = build1 (
    RETURN_EXPR,    // Тип узла
    void_type_node, // Тип выражения
    ret_assign);    // Возвращаемое выражение

// Добавляем выражение возврата в список
append_to_statement_list (
    return_stm, // Добавляемое выражение
    &stm_list); // Список выражений

// Теперь соединяем блок кода со списком выражений
tree bind = build3 (
    BIND_EXPR,      // Тип узла
    void_type_node, // Тип выражения
    NULL_TREE,      // Список объявлений
    stm_list,       // Список выражений
    body);          // Охватывающий лексический блок

// Задаём ссылку на выражение привязки к представлению
DECL_SAVED_TREE (main_fndecl) = bind;

// <-------------- Сюда будем добавлять код
 		int main(void)
{
  int ret_val;
  return (ret_val = 0);
}
 
                   ---------------
                   | RESULT_DECL |------------------
                   |    int      |                  \
                  /---------------   ---------------/
-----------------/                   | MODIFY_EXPR |
| FUNCTION_DECL |                    ---------------\ ---------------
|    "main"     |                     /              \|      0      |
|  int (void)   |                    /                ---------------
-----------------  -----------------/ 
       |          /|  RETURN_EXPR  |
-----------------/ -----------------
|     BIND      |
-----------------\ -----------------
                  \|     BLOCK     |
                   -----------------

Пока что мы получили довольно объёмный код, который по сути создаёт выражение return (ret_val = 0);. Сама по себе конструкция return будет рассмотрена в следующей части, нас здесь интересует работа со списком выражений.

В gcc есть собственные контейнеры для хранения узлов дерева, одним из них является список (также являющийся узлом дерева). Список создаётся вызовом функции alloc_stmt_list, а добавление элементов производится при помощи функции append_to_statement_list. Интерфейсы работы с контейнерами можно посмотреть в файле tree-iterator.h. Также стоит отметить что частой практикой является отсутствие явного вызова alloc_stmt_list и подача в append_to_statement_list адреса нулевого указателя. В этом случае список будет создан автоматически.

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

Теперь посмотрим на текстовое представление программы, которую создали:

$ cat t.x.005t.gimple
main ()
{
  signed int D.51;

  D.51 = 0;
  return D.51;
}

Вложенные лексические блоки

Теперь мы можем экспериментировать со значением константы и кодом возврата. Далее посмотрим как создавать вложенные лексические блоки:

Код в gcc Аналог на Си GENERIC
//--------------------- Пример 4

// Создаём ещё один блок кода
tree block_1 = make_node (BLOCK);

// Указываем отношение охвата/вложенности
BLOCK_SUPERCONTEXT (block_1) = body;
BLOCK_SUBBLOCKS (body)       = block_1;
// Выставляем признак использования
// чтобы блок кода не удалялся
TREE_USED (block_1) = 1;

// Теперь соединяем блок кода со списком выражений
tree bind_1 = build3 (
    BIND_EXPR,      // Тип узла
    void_type_node, // Тип выражения
    NULL_TREE,      // Узел цепочки объявлений
    NULL_TREE,      // Список выражений
    block_1);       // Блок, к которому привязываемся

// Указываем наличие побочных эффектов
// иначе компилятор удалит выражение
TREE_SIDE_EFFECTS (bind_1) = 1;

// Добавляем выражение возврата в список
append_to_statement_list (bind_1, &stm_list);

// Создаём ещё один блок кода
tree block_2   = make_node (BLOCK);

// Указываем отношение охвата/вложенности
BLOCK_SUPERCONTEXT (block_2) = body;
BLOCK_SUBBLOCKS (body)       = block_2;
// Выставляем признак использования чтобы блок кода не удалялся
TREE_USED (block_2)   = 1;
// Задаём цепочку следования блоков кода
BLOCK_CHAIN (block_1) = block_2;

// Теперь соединяем блок кода со списком выражений
tree bind_2 = build3 (
    BIND_EXPR,      // Тип узла
    void_type_node, // Тип выражения
    NULL_TREE,      // Узел цепочки объявлений
    NULL_TREE,      // Список выражений
    block_2);       // Блок, к которому привязываемся

// Указываем наличие побочных эффектов
// иначе компилятор удалит выражение
TREE_SIDE_EFFECTS (bind_2) = 1;

// Добавляем выражение возврата в список
append_to_statement_list (bind_2, &stm_list);

// <-------------- Сюда будем добавлять код
 		int main(void)
{
  int ret_val;
  ret_val = 0;
  return ret_val;
  {
  }
  {
  }
}
 
                   ---------------
                   | RESULT_DECL |------------------
                   |    int      |                  \
                  /---------------   ---------------/
-----------------/                   | MODIFY_EXPR |
| FUNCTION_DECL |                    ---------------\ ---------------
|    "main"     |                     /              \|      0      |
|  int (void)   |                    /                ---------------
-----------------   ----------------- 
       |          --|  RETURN_EXPR  |
-----------------/  -----------------
|     BIND      |          |         
-----------------   -----------------
       |           /|     BIND      |
----------------- | -----------------                
|     BLOCK     | |        |         
----------------- | -----------------
       |          | |     BIND      |
-----------------/ /-----------------
|     BLOCK     | |
----------------- |
       |          |
-----------------/ 
|     BLOCK     |
-----------------

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

Далее мы уже привычным движением создали узел с типом BIND, к которому привязали вновь созданный блок кода. Для этого узла мы выставили признак TREE_SIDE_EFFECTS, который также не даёт компилятору удалить этот узел (можно его удалить и убедиться что лексический блок пропадёт).

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

$ cat t.x.005t.gimple 
main ()
{
  signed int D.51;

  D.51 = 0;
  return D.51;
  {

  }
  {

  }
}

Цепочка объявлений локальных переменных

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

Код в gcc Аналог на Си GENERIC
//--------------------- Пример 5

// Создаём узел объявления первой переменной
tree tmp_decl_1 = build_decl (
    UNKNOWN_LOCATION,        // Положение в исходном коде
    VAR_DECL,                // Тип узла
    get_identifier("tmp1"),  // Имя переменной
    integer_type_node);      // Тип переменной

// Помечаем выражение как используемое
// чтобы оно не удалялось
TREE_USED (tmp_decl_1) = 1;

// Создаём узел объявления первой переменной
tree tmp_decl_2 = build_decl (
    UNKNOWN_LOCATION,        // Положение в исходном коде
    VAR_DECL,                // Тип узла
    get_identifier("tmp2"),  // Имя переменной
    integer_type_node);      // Тип переменной

// Помечаем выражение как используемое
// чтобы оно не удалялось
TREE_USED (tmp_decl_2)  = 1;

// Указываем что за первым узлом объявления
// следует второй
DECL_CHAIN (tmp_decl_1) = tmp_decl_2;

// Для выражения привязывания указываем
// начало цепочки узлов объявлений
BIND_EXPR_VARS (bind_1) = tmp_decl_1;
 		int main(void)
{
  int ret_val;
  ret_val = 0;
  return ret_val;
  {
    int tmp1;
    int tmp2;
  }
  {
  }
}
 
                   ---------------
                   | RESULT_DECL |------------------
                   |    int      |                  \
                  /---------------   ---------------/
-----------------/                   | MODIFY_EXPR |
| FUNCTION_DECL |                    ---------------\ ---------------
|    "main"     |                     /              \|      0      |
|  int (void)   |                    /                ---------------
-----------------   ----------------- 
       |          --|  RETURN_EXPR  |
-----------------/  -----------------
|     BIND      |          |         
-----------------   -----------------
       |           /|     BIND      |
----------------- | -----------------\ ---------------
|     BLOCK     | |        |          \|  VAR_DECL   | 
----------------- | -----------------  |    tmp1     | 
       |          | |     BIND      |  |    int      | 
-----------------/ /-----------------  --------------- 
|     BLOCK     | |                          |         
----------------- |                    ---------------
       |          |                    |  VAR_DECL   | 
-----------------/                     |    tmp2     | 
|     BLOCK     |                      |    int      | 
-----------------                      ---------------

Объявление локальных переменных задаётся при помощи узла с типом VAR_DECL. Его операндами будут узел с именем переменной и узел с её типом. Интересно заметить что символьное имя переменной задаётся именно узлом дерева, создаваемым функцией get_identifier.

Мы можем заметить ещё один новый макрос DECL_CHAIN. Этот макрос задаёт ссылку на следующий элемент цепочки, т.е. по сути узлы становятся односвязным списком.

Привязать этот односвязный список к блоку кода можно было бы при создании узла BIND, но в нашем случае этот узел уже создан. Поэтому мы сделаем это воспользовавшись макросом BIND_EXPR_VARS.

Пересоберём компилятор и посмотрим на результат:

$ cat t.x.005t.gimple
main ()
{
  signed int D.53;

  D.53 = 0;
  return D.53;
  {
    signed int tmp1;
    signed int tmp2;


  }
  {

  }
}

Заключение

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