Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Внутреннее устройство llst, часть 2 либо Little Smalltalk LLVM =

Anna | 24.06.2014 | нет комментариев

Каждому здравствуй! Коллективно с humbug, мы предлагаем вашему вниманию третью статью из цикла о Low Level Smalltalk (LLST). Надемся, что статья будет увлекательна не только любителямвелосипедов странных языков программирования, но и тем, кто интересуется такой восхитительной вещью, как LLVM.

Напомню, что целью нашего плана является создание собственной виртуальной машины, совместимой с Little Smalltalk на ярусе байт-кодов. Ключевым различием является гетерогенная зодчество, которая разрешает исполнять байт-коды как программно, так и компилировать их в низкоуровневые инструкции процессора посредством трансляции в IR код LLVM. Разумеется, 2-й метод разрешает достичь больше высокой продуктивности и задействовать имеющиеся в нашем распоряжении вычислительные источники оптимальным образом.

Впрочем, обо каждому по порядку…

Новое в версии 0.2

По сопоставлению с прошлой версией, описанной в предыдущей статье, изменений дюже много:

  • Подключили библиотеку readline. Сейчас дозволено комфортно редактировать командную строку; возникла история ранее введенных команд (Ctrl R) и автодополнение по клавише Tab. В всеобщем, все работает так же, как в любом типичном шелле.
  • Дописаны примитивы работы с файлами и реализована запись образа на диск. Сейчас с новой VM дозволено делать фактически то же самое, что и с подлинной.
  • Реализована примитивная многозадачность (green threads) на базе класса Scheduler. В планах — полновесная многопоточность.
  • Написаны тесты для основных операций с объектами, которые гораздо упростили последующую отладку. Тесты — это резко!
  • Переделаны указатели на объекты кучи hptr<>. Прежде они применяли внешние списки std::list<>, сейчас список поддерживается в стековом пространстве. Одно только это ускорило софтовую VM в два раза.
  • В ветке 37 сделаны очерки Native API, тот, что в грядущем дозволит комфортно писать нативные способы абсолютно без врапперов и прочих костылей. Способы реализуются «по месту», в тех же классах, что описывают конструкцию равнозначных сущностей из Smalltalk. Примеры дозволено посмотреть туттут и тут.
  • Сделана попытка реализации Generational GC на базе имеющегося Бейкера. По сути, все различие в роли половинок кучи и хранении списка ссылок между поколениями. Таким образом, при стремительной сборке нужно пробежаться только по молодому поколению и взять оттуда объекты, на которые есть ссылки из больше старших поколений. Код написан, но пока не отлажен.
  • Начата работа по переписыванию ImageBuilder с нуля с применением Flex/Bison. Доставшаяся в наследство утилита имеет уйма задач: невозможно передавать параметры, нет типичного итога ошибок, «необъяснимые» падения при изменении пары символов в коде образа; такие же «необъяснимые» оживания при удалении, скажем, комментария и т. п. Помимо того, утилита в некоторых случаях генерирует некорректный байт-код. Так жить, разумеется, невозможно, следственно мы решили ее переделать. На данный момент всецело описана грамматика Little Smalltalk; помимо самих конструкций языка еще присутствуют руководящие команды, которые применяются для построения первичного bootstrap образа.
  • Завели доменное имя и переехали на GitHub. Сейчас репозиторий доступен по адресу llst.org. Обрати==————————————————————————-=== … Statistics Collected … ===————————————————————————-=== 2 adce – Number of instructions removed 2 branchfolding – Number of block tails merged 2 branchfolding – Number of dead blocks removed 1 cgscc-passmgr – Maximum CGSCCPassMgr iterations on one SCC 31 codegen-dce – Number of dead instructions deleted 63 codegenprepare – Number of GEPs converted to casts 9 codegenprepare – Number of blocks eliminated 114 codegenprepare – Number of memory instructions whose address computations were sunk 47 codegenprepare – Number of uses of Cast expressions replaced with uses of sunken Casts 313 dagcombine – Number of dag nodes combined 0 dse – Number of other instrs removed 12 dse – Number of stores deleted 54 gvn – Number of blocks merged 2 gvn – Number of instructions PRE’d 125 gvn – Number of instructions deleted 2 gvn – Number of loads PRE’d 37 gvn – Number of loads deleted 265 inline – Number of functions inlined 271 inline-cost – Number of call sites analyzed 263 instcombine – Number of dead inst eliminated 1 instcombine – Number of dead stores eliminated 67 instcombine – Number of instructions sunk 492 instcombine – Number of insts combined 159 isel – Number of blocks selected using DAG 7667 isel – Number of times dag isel has to try another path 101 jit – Number of bytes of global vars initialized 5310 jit – Number of bytes of machine code compiled 12 jit – Number of global vars initialized 239 jit – Number of relocations applied 3 jit – Number of slabs of memory allocated by the JIT 1 loop-simplify – Number of pre-header or exit blocks inserted 3 machine-licm – Number of hoisted machine instructions CSEed 11 machine-licm – Number of machine instructions hoisted out of loops 73 machine-sink – Number of machine instructions sunk 6 memdep – Number of block queries that were completely cached 11 memdep – Number of fully cached non-local ptr responses 43 memdep – Number of uncached non-local ptr responses 784 pei – Number of bytes used for stack in all functions 1 phi-opt – Number of dead PHI cycles 15 phielim – Number of atomic phis lowered 31 pre-RA-sched – Number of loads clustered together 48 reassociate – Number of insts reassociated 29 regalloc – Number of cross class joins performed 251 regalloc – Number of identity moves eliminated after coalescing 92 regalloc – Number of identity moves eliminated after rewriting 7 regalloc – Number of instructions deleted by DCE 4 regalloc – Number of instructions re-materialized 1 regalloc – Number of interferences evicted 251 regalloc – Number of interval joins performed 11 regalloc – Number of new live ranges queued 683 regalloc – Number of original intervals 369 regalloc – Number of registers assigned 1 regalloc – Number of registers unassigned 3 regalloc – Number of rematerialized defs for spilling 4 regalloc – Number of rematerialized defs for splitting 3 regalloc – Number of spilled live ranges 2 regalloc – Number of splits finished 4 simplifycfg – Number of blocks simplified 2 twoaddrinstr – Number of instructions aggressively commuted 2 twoaddrinstr – Number of instructions commuted to coalesce 4 twoaddrinstr – Number of instructions promoted to 3-address 30 twoaddrinstr – Number of two-address instructions 14 x86-codegen – Number of floating point instructions 1414 x86-emitter – Number of machine instructions emitted ->

Главными здесь являются пять строчек:

Soft run: 60
Cold jit run: 46
Hot jit run: 28
Patched cold jit run: 12
Patched hot jit run: 9

Первая строка — выполнение способа средствами программной VM. Самый неторопливый метод: никаких фокусов, код выполняется предельно правильно, инструкция за инструкцией. Данный режим классен для отладки, от того что не вносит никаких изменений в код; также он применяется встроенным в образ компилятором при разборе командной строки.

Вторая строка — «леденящий» прогон JIT. Выполняется трансляция способа в функционально равнозначный IR код, его компиляция в инструкции процессора, которые теснее выполняются непринужденно. Теснее на этом этапе производятся кое какие оптимизации, о которых будет рассказано позднее. Видно, что даже с учетом компиляции способа, итоговое время выполнения поменьше, чем чистое исполнение. Так бывает не неизменно. Нередко, для трудных способов первое выполнение может затребовать на n: (10 sites) isEmpty (index 3, offset 7) class hits: (List 1867) add: (index 10, offset 27) class hits: (List 130) value (index 33, offset 166) class hits: (Link 10419) value:value: (index 40, offset 210) class hits: (Block 10419) next (index 48, offset 268) class hits: (Link 1481) value:next: (index 50, offset 286) class hits: (MetaLink 1481) value:next: (index 57, offset 21) class hits: (Link 1481) next (index 68, offset 8) class hits: (Link 8938) value:next: (index 81, offset 24) class hits: (MetaLink 256) next: (index 83, offset 9) class hits: (Link 256) 1481 Link>>value:next: (0 sites) 392 List>>size (0 sites) 390 MetaList>>new (2 sites) new (index 4, offset 9) class hits: (MetaCollection 390) in:at:put: (index 12, offset 34) class hits: (MetaList 390) 384 Link>>next: (0 sites) 262 Collection>>sort: (13 sites) size (index 3, offset 7) class hits: (List 262) insertSort: (index 12, offset 34) class hits: (List 132) popFirst (index 21, offset 88) class hits: (List 130) new (index 26, offset 126) class hits: (MetaList 130) new (index 31, offset 158) class hits: (MetaList 130) value:value: (index 42, offset 219) class hits: (Block 15359) add: (index 49, offset 279) class hits: (List 8207) add: (index 56, offset 12) class hits: (List 7152) do: (index 59, offset 31) class hits: (List 130) sort: (index 64, offset 64) class hits: (List 130) sort: (index 70, offset 19) class hits: (List 130) add: (index 76, offset 4) class hits: (List 130) appendList: (index 81, offset 24) class hits: (List 130) 260 Link>>do: (2 sites) value (index 18, offset 72) class hits: (Link 260) value: (index 20, offset 82) class hits: (Block 260) 260 List>>do: (1 sites) do: (index 9, offset 25) class hits: (Link 260) 132 Collection>>insertSort: (4 sites) isEmpty (index 3, offset 7) class hits: (List 132) new (index 16, offset 55) class hits: (MetaList 130) insert:onCondition: (index 27, offset 130) class hits: (List 1867) do: (index 30, offset 143) class hits: (List 130) 130 List>>popFirst (3 sites) value (index 14, offset 43) class hits: (Link 130) next (index 19, offset 76) class hits: (Link 130) – (index 25, offset 111) class hits: (SmallInt 130) 130 SmallInt>>- (0 sites) 130 List>>appendList: (7 sites) firstLink (index 8, offset 21) class hits: (List 2) size (index 13, offset 40) class hits: (List 2) next (index 36, offset 181) class hits: (Link 8207) next (index 43, offset 234) class hits: (Link 8079) firstLink (index 54, offset 3) class hits: (List 128) next: (index 56, offset 12) class hits: (Link 128) size (index 61, offset 49) class hits: (List 128) 130 List>>firstLink (0 sites) 2 Collection>>sort (1 sites) sort: (index 10, offset 27) class hits: (List 2) 2 Block>>value (0 sites) ===————————————————————————-=== … Statistics Collected … ===————————————————————————-=== 2 adce – Number of instructions removed 14 branchfolding – Number of block tails merged 6 branchfolding – Number of branches optimized 5 branchfolding – Number of dead blocks removed 1 cgscc-passmgr – Maximum CGSCCPassMgr iterations on one SCC 38 codegen-dce – Number of dead instructions deleted 220 codegenprepare – Number of GEPs converted to casts 2 codegenprepare – Number of blocks eliminated 151 codegenprepare – Number of memory instructions whose address computations were sunk 123 codegenprepare – Number of uses of Cast expressions replaced with uses of sunken Casts 854 dagcombine – Number of dag nodes combined 250 dce – Number of insts removed 194 dse – Number of other instrs removed 158 dse – Number of stores deleted 51 gvn – Number of blocks merged 353 gvn – Number of instructions deleted 6 gvn – Number of loads PRE’d 277 gvn – Number of loads deleted 862 inline – Number of functions inlined 862 inline-cost – Number of call sites analyzed 1085 instcombine – Number of dead inst eliminated 69 instcombine – Number of instructions sunk 2540 instcombine – Number of insts combined 194 isel – Number of blocks selected using DAG 18193 isel – Number of times dag isel has to try another path 461 jit – Number of bytes of global vars initialized 12042 jit – Number of bytes of machine code compiled 25 jit – Number of global vars initialized 375 jit – Number of relocations applied 2 jit – Number of slabs of memory allocated by the JIT 15 llst – Number of removed loads from gc.root protected pointers <<<<<< 222 llst – Number of removed roots <<<<<< 4 machine-cse – Number of common subexpression eliminated 1 machine-licm – Number of hoisted machine instructions CSEed 14 machine-licm – Number of machine instructions hoisted out of loops 71 machine-sink – Number of machine instructions sunk 10 memdep – Number of block queries that were completely cached 81 memdep – Number of fully cached non-local ptr responses 84 memdep – Number of uncached non-local ptr responses 2792 pei – Number of bytes used for stack in all functions 9 phielim – Number of atomic phis lowered 2 phielim – Number of critical edges split 36 pre-RA-sched – Number of loads clustered together 23 reassociate – Number of insts reassociated 21 regalloc – Number of cross class joins performed 250 regalloc – Number of identity moves eliminated after coalescing 124 regalloc – Number of identity moves eliminated after rewriting 6 regalloc – Number of instructions deleted by DCE 1 regalloc – Number of interferences evicted 248 regalloc – Number of interval joins performed 21 regalloc – Number of new live ranges queued 1240 regalloc – Number of original intervals 891 regalloc – Number of registers assigned 1 regalloc – Number of registers unassigned 6 regalloc – Number of rematerialized defs for spilling 4 regalloc – Number of rematerialized defs for splitting 6 regalloc – Number of spilled live ranges 4 regalloc – Number of splits finished 13 simplifycfg – Number of blocks simplified 3 twoaddrinstr – Number of instructions re-materialized 43 twoaddrinstr – Number of two-address instructions 40 x86-codegen – Number of floating point instructions 2697 x86-emitter – Number of machine instructions emitted Patching active methods that have hot call sites Recompiling method for patching: MetaLink>>value:next: Patching MetaLink>>value:next: …done. Verifying …done. Recompiling method for patching: List>>add: Patching List>>add: …done. Verifying …done. Recompiling method for patching: List>>isEmpty Patching List>>isEmpty …done. Verifying …done. Recompiling method for patching: List>>insert:onCondition: Patching List>>insert:onCondition: …done. Verifying …done. Recompiling method for patching: MetaList>>new Patching MetaList>>new …done. Verifying …done. Recompiling method for patching: Collection>>sort: Patching Collection>>sort: …done. Verifying …done. Recompiling method for patching: Link>>do: Patching Link>>do: …done. Verifying …done. Recompiling method for patching: List>>do: Patching List>>do: …done. Verifying …done. Recompiling method for patching: Collection>>insertSort: Patching Collection>>insertSort: …done. Verifying …done. Recompiling method for patching: List>>popFirst Patching List>>popFirst …done. Verifying …done. Recompiling method for patching: List>>appendList: Patching List>>appendList: …done. Verifying …done. Recompiling method for patching: Collection>>sort Patching Collection>>sort …done. Verifying …done. Optimizing MetaLink>>value:next: …done. Verifying …done. Optimizing List>>add: …done. Verifying …done. Optimizing List>>isEmpty …done. Verifying …done. Optimizing List>>insert:onCondition: …done. Verifying …done. Optimizing MetaList>>new …done. Verifying …done. Optimizing Collection>>sort: …done. Verifying …done. Optimizing Link>>do: …done. Verifying …done. Optimizing List>>do: …done. Verifying …done. Optimizing Collection>>insertSort: …done. Verifying …done. Optimizing List>>popFirst …done. Verifying …done. Optimizing List>>appendList: …done. Verifying …done. Optimizing Collection>>sort …done. Verifying …done. Compiling machine code for MetaLink>>value:next: …done. Compiling machine code for List>>add: …done. Compiling machine code for List>>isEmpty …done. Compiling machine code for List>>insert:onCondition: …done. Compiling machine code for MetaList>>new …done. Compiling machine code for Collection>>sort: …done. Compiling machine code for Link>>do: …done. Compiling machine code for List>>do: …done. Compiling machine code for Collection>>insertSort: …done. Compiling machine code for List>>popFirst …done. Compiling machine code for List>>appendList: …done. Compiling machine code for Collection>>sort …done. All is done. Patched cold jit run: 7 Patched hot jit run: 6

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

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

Виртуальная машина Smalltalk

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

Дабы осознать как машина это делает, нужно вначале осознать, что же такое Smalltalk объект.

Объекты

Всякий объект упрощенно может быть представлен дальнейшей конструкцией:

struct TObject {
    TSize    size;
    TClass*  klass;
    union {
        TObject* fields[0];
        uint8_t  bytes[0];
    };
};

Всякий объект имеет заголовок в котором записан размер объекта и указатель на его класс. Следом идут поля объекта, содержrmark!Массив селекторов отсортирован лексикографически;

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

В случае если способ так и не был обнаружен в иерархии классов, виртуальная машина посылает объекту сообщение #doesNotUnderstand:, которое гарантировано будет обработано (как минимум в самом Object). В некоторых случаях классы специально перехватывают это сообщение для достижения специальных целей. Скажем, так могут поступать прокси объекты, которые после этого доставляют сообщение по действительному адресу.

Для вышеописанного сообщения String>>isNilцепочка поиска будет такой:
    String rk!В всякий момент времени контекст располагает каждой информацией, касательно нынешнего состояния выполнения способа. Это дает вероятность легко прекрастить выполнение способа (скажем при истечении числа тиков, отведенных для него), а после этого позже возвратиться обратно. Есть еще экзотические варианты применения, включающие, скажем, реализацию продолжений (continuation).

Способы

Способы представлены объектами дальнейшего вида:

struct TMethod : public TObject {
    TSymbol*      name;
    TByteObject*  byteCodes;
    TSymbolArray* literals;
    TInteger      stackSize;
    TInteger      temporarySize;
    TClass*       klass;
    TString*      text;
    TObject*      package;
};

 

  • name — собственно имя способа, а вернее указатель на символ этого имени.
  • byteCodes — тут лежит указатель на объектByteArray, содержащий байт-коды способа.
  • literals — при компиляции способа сюда попадают литеральные объекты. К ним относятся: числовые константы, имена классов, селекторы сообщений. От того что эта информация не меняется от вызова к вызову, она сохраняется в самом объекте способа.
  • stackSize — тут записан размер стека значений (см. выше TContext::stack), тот, что нужно сделать при посылке сообщения.
  • temporarySize — размер массива, хранящего временные переменные способа. Тоже относится к создаваемому объекту контекста.
  • klass — ссылка на класс, которому принадлежит данный способ.
  • text — начальный текст данного способа.
  • package — категория данного способа. Предуготовлена для фильтрации списков отображаемых способов в пользовательском интерфейсе. В реальное время не применяется.

Объекты способов формируются при компиляции первичного образа из исходника imageSource.st утилитой ImageBuilder, а после этого сохраняются в получаемый файл образа. Также одноразовый способ создается при выполнении команды из командной строки. По сути, текст командной строки интерпретируется как тело способа, тот, что после этого компилируется и вызывается обыкновенным образом.

Это делается так. В теле способа Undefined>>mainесть код:

[ command <- String readline: '->'. command notNil ]
    whileTrue: [ command isEmpty ifFalse: [ command doIt printNl ] ]

Вначале с поддержкой библиотеки readline мы получаем строку команды. После этого объекту строки посылается сообщение #doIt, итог которого выводится на экран. Сам способ #doIt выглядит дальнейшим образом:

doIt | method |
	method <- Undefined parseMethod: 'doItCommand ^ '   self.
	^ method notNil
		ifTrue: [ ^ Context new
			  perform: method withArguments: (Array new: 1) ]

Каждая магия творится в способе Undefined>>parseMethod: тот, что по начальному тексту формирует объект способа #doItCommand с поддержкой компилятора, реализованного тут же, в тексте образа. Получается, что Smalltalk компилирует свои личные способы посредством компилятора, написанного на самом Smalltalk и являющимся неотделимой частью образа. Я нахожу данный момент достаточно комичным.

Позже того как объект способа был сделан, для его вызова формируется объект контекста, с поддержкой которого выполняется сделанный способ. От того что новейший способ не добавлялся в списки способов ни одного из классов, он будет существовать только на момент своего исполнения (ну и до дальнейшей сборки мусора).

Инструкции виртуальной машины

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

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

Инструкции работы со стеком значений

Существует четые push инструкции, проталкивающие на вершину стека значений один из объектов. Совместно с кодом инструкции указывается также целочисленный параметр, тот, что интерпретируется как индекс для выборки объекта из соответствующей конструкции данных:

  • pushArgument — довод из массива доводов нынешнего контекста.
  • pushInstance — поле нынешнего объекта.
  • pushTemporary — временная переменная из массива переменных нынешнего контекста.
  • pushLiteral — литерал из константного массива литералов данного способа.

Есть еще две особых push инструкции, которые работают немножко напротив:

  • pushConstant — в зависимости от параметра кладет на вершину стека одну из констант: SmallInt значение, соответствующее числам 0-9, а также константные объекты niltrue и false, являющиеся инстанциями UndefinedTrue и False соответственно.
  • pushBlock — применяется виртуальной машиной для создания и инициализации объекта Block, связанного с участком байт-кодов способа, которые относятся к данному блоку. Позже этой инструкции указатель bytePointer смещается на размер кода блока.

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

  • assignInstance — присваивает полю нынешнего объекта значение, лежащее на вершине стека.
  • assignTemporary — присваивает временной переменной значение, лежащее на вершине стека.

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

Инструкции перехода

Имеются, безусловно же, и инструкции переходов:

  • branchIfTrue — устанавливает bytePointer в указанное параметром значение, если на стеке лежит true.
  • branchIfFalse — то же, но только если на стеке лежит false.
  • branch — абсолютный переход на указанное смещение.

 

Инструкции посылки сообщения

Правда процедура посылки сообщения универсальна и может использоваться всюду, в некоторых случаях применяются специализированные ее реализации для убыстрения обработки. Такими специальными случаями являются операции посылки унарного и бинарного сообщений. Для них предусмотрены отдельные инструкции sendUnary и sendBinary. Обыкновенное сообщение посылается инструкцией sendMessage.

При посылке сообщения доводы помещаются в стек, позже чего вызывается инструкция markArguments N. Она снимает со стека N значений и формирует из них объект Array. Дальше, указатель на данный объект возвращается на вершину стека, тот, что будет использован при инициализации поля arguments у создаваемого объекта контекста.

Инструкции возврата

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

Помимо возврата произвольного значения в Smalltalk дюже частно бывает нужно воротить self в качестве итога. Следственно для такой операции предусмотрена отдельная инструкция selfReturn.

Последней изинструкций возврата является blockReturn, объяснить которую на пальцах достаточно трудно. Основная идея заключается в том, что управление передается не в порождающий контекст, а значительно выше, в родительский контекст способа, содержащего объявление выполняющегося в данный момент блока. Сходственное поведение дозволено сравнить с механизмом выброса исключения в других языках. Только в различие от исключений, которые происходят только в специальных обстановках программы и в всеобщем случае не относятся к «типичному» ходу выполнения программы, blockReturn является абсолютно штатной операцией с точки зрения виртуальной машины и может применяться в всеобщем коде.

Проще каждого это показать на примере. Это текст способа Collection>>at:ifAbsent:

at: value ifAbsent: exceptionBlock
	self do: [ :element | element = value ifTrue: [ ^element ] ].
	^exceptionBlock value

Выражение ^element, стоящее в самом вложенном блоке, будет скомпилировано с применением инструкции blockReturn. Это нужно потому, что реально, блок будет выполняться не в нынешнем способе, а значительно глубже. Способ Collection>>at:ifAbsent: вызывает способ Collection>>do:, передавая внешний блок в качестве параметра. Способ Collection>>do: в свою очередь будет вызывать Block>>value: для всякого элемента коллекции, передавая его в качестве параметра блоку. И только внутри Block>>value: располагается примитив номер 8, тот, что теснее приведет к выполнению кода блока. Следственно, кода блок решит, что нужно исполнить возврат значения element, он сделает это с ипользованием инструкции blockReturn, которая передаст управление на самый верх, за пределы Collection>>at:ifAbsent:, вернув нужное значение в качестве итога сообщения.

Стоит подметить, что не всякий оператор ^, стоящий в теле блока, будет преобразован в инструкцию blockReturn. Компилятор по вероятности усердствует разложить код на больше примитивные инструкции: блоки внедрить в тело выполняющегося способа и заменить вызов блоков примитивными переходами по инструкциям. В этом случае blockReturn также будет заменен на stackReturnлибо selfReturn.

Особые инструкции

Помимо вышеперечисленных инструкций есть еще некоторое число вспомогательных. К таким дозволено отнести инструкции popTop и dup. Первая легко снимает значение с вершины стека, которое было туда положено ранее с поддержкой одной из push инструкций (либо самой виртуальной машиной, как итог посылки сообщения). Традиционно popTop применяется позже инструкций assignInstance либо assignTemporary, для удаления больше не надобного значения со стека.

Инструкция dup, как дозволено додуматься из наименования, дублирует значение на стеке, размещая рядом верно такое же. Эта инструкция применяется компилятором Smalltalk при разборе трудных выражений с условиями.

Исполнение способа

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

Исполнение способа и работу JIT компилятора мы проследим на базе теснее приятеля нам по прошлой статье способа сортировки коллекции:

->Collection viewMethod: #sort:
sort: criteria | left right mediane |
    (self size < 32) 
        ifTrue: [ ^ self insertSort: criteria ].

    mediane <- self popFirst.

    left  <- List new.
    right <- List new.
    self do: [ :x  |
        (criteria value: x value: mediane)
            ifTrue:  [ left  add: x ]
            ifFalse: [ right add: x ] ].

    left  <- left  sort: criteria.
    right <- right sort: criteria.

    right add: mediane.
    ^ left appendList: right

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

->Collection methods at: #sort:; disassemble
"проверка данные размера"
0000 PushArgument 0              "нулевой довод это неизменно self"
0001 MarkArguments 1
0002 SendMessage size
0003 PushLiteral 1               "по индексу 1 в массиве литералов этого способа лежит число 32"
0004 SendBinary <                "исполняем сопоставление"
0005 DoSpecial branchIfFalse 16  "переходим в зависимости от итога сопоставления"

"если условие исполнено:"
0008 PushArgument 0
0009 PushArgument 1
0010 MarkArguments 2
0011 SendMessage insertSort:
0012 DoSpecial stackReturn
0013 DoSpecial branch 17

"если условие не исполнено:"
0016 PushConstant nil           "равновесие стека"
0017 DoSpecial popTop

"mediane <- self popFirst"
0018 PushArgument 0
0019 MarkArguments 1
0020 SendMessage popFirst
0021 AssignTemporary 2
0022 DoSpecial popTop

"left <- List new"
0023 PushLiteral 4
0024 MarkArguments 1
0025 SendMessage new
0026 AssignTemporary 0
0027 DoSpecial popTop

"right <- List new"
0028 PushLiteral 6
0029 MarkArguments 1
0030 SendMessage new
0031 AssignTemporary 1
0032 DoSpecial popTop

"self do: ..."
0033 PushArgument 0
0034 PushBlock "тело блока"
0037     PushArgument 1             "criteria"
0038     PushTemporary 3            "x"
0039     PushTemporary 2            "mediane"
0040     MarkArguments 3
0041     SendMessage value:value:   "основное условие сортировки"
0042     DoSpecial branchIfFalse 52

"left add: x"
0045     PushTemporary 0
0046     PushTemporary 3
0047     MarkArguments 2
0048     SendMessage add:
0049     DoSpecial branch 56

"right add: x"
0052     PushTemporary 1
0053     PushTemporary 3
0054     MarkArguments 2
0055     SendMessage add:

0056     DoSpecial stackReturn
0057 MarkArguments 2
0058 SendMessage do:
0059 DoSpecial popTop

"рекурсивная сортировка left"
0060 PushTemporary 0
0061 PushArgument 1
0062 MarkArguments 2
0063 SendMessage sort:
0064 AssignTemporary 0
0065 DoSpecial popTop

"рекурсивная сортировка right"
0066 PushTemporary 1
0067 PushArgument 1
0068 MarkArguments 2
0069 SendMessage sort:
0070 AssignTemporary 1
0071 DoSpecial popTop

"right add: mediane"
0072 PushTemporary 1
0073 PushTemporary 2
0074 MarkArguments 2
0075 SendMessage add:
0076 DoSpecial popTop

"конкатенация отсортированных частей"
0077 PushTemporary 0
0078 PushTemporary 1
0079 MarkArguments 2
0080 SendMessage appendList:

"возврат итога"
0081 DoSpecial stackReturn

"(заглушка компилятора)"
0082 DoSpecial popTop
0083 DoSpecial selfReturn

Завершение

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

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

В дальнейшей статье (которая теснее написана и скоро будет опубликована) рассматриваются вопросы JIT компиляции Smalltalk способов в промежуточный IR код, внятный LLVM. В свою очередь, он будет компилироваться теснее в настоящие инструкции процессора. Мы проанализируем байт-коды способа и попытаемся осознать, что необходимо сделать, Дабы транслировать их в IR оптимальным образом.

Напоследок, маленький опрос:

Оцените, пожалуйста, подачу материала

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

Проголосовало 9 человек. Воздержалось 4 человека.

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB