Здесь перечислены как ошибки, так и просто неоптимальные решения. Их оказалось не так уж мало, но как ни странно, они не помешали реализовать сам компилятор и были выявлены очень поздно. Ошибки перечислены в порядке их обнаружения.
Ошибка проявлялась при загрузке четырехбайтового значения, адресуемого ссылочной переменной:
Код:
По видимому источник ошибки - использование copy/paste.
Компилятор был написан на языке C и в силу непонятных причин вместо макроса isalpha использовался следующий код:
После перевода исходного текста с C на Context этот код перобразовался в
В итоге то, что требует одного обращения по индексу и одного сравнения, стало требовать нескольких десятков этих же действий. Следующая неоптимальная и не совсем корректная в смысле переносимости реализация функции isalpha сократила время копиляции втрое:
Макрос isalpha обычно реализуется так:
Компилятор выводит на консоль число прочитанных строк. Первоначально он делал это всякий раз, как встречался символ перевода строки (LF) и это заметно снижало скорость работы. Очевидное решение - выводить номер каждой десятой или сотой строки. В конце процесса нужно еще раз вывести число прочитанных строк.
Комбинация используемых в команде индексных регистров определяет сегментный регистр, который будет использоваться. Если нужно использовать другой сегментный регистр, перед командой должен быть помещен префикс замены сегмента - байт, указывающий какой сегментный регистр должен использоваться в следующей за ним команде. В некоторых случаях ассемблер выдавал префиксы замены сегмента, когда они не нужны.
Код:
Скорее всего источник ошибки - использование copy/paste. Также по-видимому лучше вместо загрузки байта и обнуления AH/BH загружать в AX/BX слово, хотя различные процессоры могут отнестись к этому по-разному. Приведенный код хоть и не хорош, но по крайней мере правильно работает.
Код:
Позже для случаев типа приведенного был реализован специальный вариант генерации кода:
Код:
Если случайно окажется, что сегмент и смещение объекта имеют одинаковые ненулевые значения, ссылка на этот объект будет ошибочно посчитана пустой. Разумеется, без записи результата сравнения в CL обойтись можно, но это плата за простоту компилятора выражений. В тексте компилятора нигде не нужно проверять инициализацию ссылок, так что и эта ошибка была выявлена не сразу. Сейчас уже сложно выяснить, почему такая ошибка была сделана.
Ошибка проявлялась если в тексте программы был незакрытый комментарий:
В функции Scan() отсутствовал выход из цикла пропуска пробелов/комментариев при достижении конца файла. Возвращаемый функцией Read() символ EOF (#26) никак не учитывался.
Первое исправление ошибки также было некорректным. Замена возврата EOF завершением работы и выдачей диагностического сообщения устранило эту ошибку, до создало другую - если после завершающего программу слова end не было символов, компиляция завершалась сообщением об обнаружении конца файла. Начав считывать слово, сканер вызывает функцию Read() пока она не вернет символ, не являющийся ни буквой ни цифрой. После считывания буквы d опять взывается функция Read() и на этом все заканчивалось:
Ошибка не была замечена, поскольку используемый автором текстовый редактор вставлял символы CR/LF и в конце последней строки текста тоже.
Приведенный фрагмент воспринимается компилятором как завершенный комментарий. В языке C++ это так и есть, комментарии не могут быть вложенными и вторая строка не считается однострочным комментарием. В Context'е комментарии могут вкладываться друг в друга и вторая строка должна считаться вложенным комментарием.
Для чтения символа из компилируемого файла использовалась пара функций Read() и Next():
Если требуется чтение символа, нужно последовательно вызвать обе эти функции. Замена их парой функций Look() и Read() позволяет немного сократить код:
Вместо вызова Read() нужно выполнять вызов Look(), вместо вызовов Read() и Next() - только вызов Read().
Две ошибки проявлялись при компиляции следующей программы:
Код:
В отличие от сравнения целых и символьных операндов, которое по умолчанию есть сравнение
первого операнда со вторым (результат команды cmp AX/AL, BX/BL
Ошибка в Context 2.0:
Код:
По видимому источник ошибки - использование copy/paste.
Следующий фрагмент считался корректным:
Желание cъэкономить несколько строк привело к следующему коду:
Ошибка в Context 2.0.
Функция Find может возвращать значение от 0 до nDict, так что условие
I>nDict всегда ложно и дальнейшее зависит от значения
поля Class неинициализированного элемента массива.
Ошибка проявлялась при компиляции следующей программы:
Код:
После выполнения call управление вновь попадает в начало главной функции (метка F) и call выполняется снова. Со всеми вытекающими последствиями.
Функция Ctrl помимо прочего должна была устанавливать глобальную переменную Retn и она это делала, но перед вызовом самой себя, а не после.
В первой версии компилятора ошибка отсутствовала - код функции завершался командой ret независимо ни от чего. В последующих ни одна из функций не завершалась выходом по условию. В Windows-версии факт отсутствия оператора возврата устанавливался путем анализа промежуточного представления программы и эта ошибка отсутствовала.
Выбранный способ синтаксического анализа не использует список зарезервированных слов. В DOS-версиях список просто отсутствовал, соответственно любое слово могло быть идентификатором:
В Windows-версии список появился и использовался для запрета использования зарезервированных слов в качестве идентификаторов. Но список никак не связан с синтаксическим анализатором и не обязан совпадать с распознаваемыми им словами. При реализации цикла repeat/until (в минимальной версии он отсутстует) оба слова не были добавлены в список. Следовало добавить их еще в минимальной версии - слово function, например, было в списке, хотя типы-функции не были реализованы. А вот inline появилось только в версии 2.14, до нее его необходимость была неочевидна и здесь возможна несовместимость с ранее написанными программами. Основная проблема здесь в том, что некорректное содержание списка слов не проявляется при компиляции правильной программы.
Предполагалось, что во вкючаемых файлах могут быть законченные части программы, например функции целиком, но следующий распределенный по трем файлам текст считался допустимым:
Нехорошо в нем почти все:
Нечто похожее возможно и в C++:
Ключевое слово не может быть разбито на части, в остальном все то же самое.
Код был бы правильным, если бы в EAX был не адрес функции, а адрес ячейки памяти, содержащей адрес функции. В DOS-версии компилятора этой ошибки не было.
Ошибка в Context 2.0. Имеет место, в частности, при компиляции следующего примера:
Создаваемый код неправильно вычисляет смещение и разрушает стек:
Помимо ошибки код включает много лишних действий. В данном случае он легко сводится к двум командам:
Ошибка связана с некорректным использованием признака занятости регистра EAX (fEAX). Исправление потребовало полной замены фрагмента кода, отвечающего за вычисление смещения элемента массива (iINDEX). По-видимому, в простых случаях ошибка не проявляется.
Вообще, использование fEAX нельзя считать хорошим решением, правильнее использовать некую схему предварительного распределения регистров (хотя бы локальную), но по ряду причин это не было сделано.
Компилятор содержит ряд функций, длина которых значительна. Некоторые их них не могут быть разбиты на части без использования косвенной рекурсии (в минимальной версии компилятора она не допускается), другие могут быть разделены. Во всех или почти во всех случаях неповторяющийся блок кода не оформлялся как отдлельная функция и отделялся от других блоков пустыми строками. Само по себе это не ошибка, но запутывает текст и может быть источником ошибок, например из-за большой области видимости локальных переменных. Выделение именованных функций позволяет улучшить читаемость текста. Например, сканер может быть переписан так:
или, если использовать отсутствующий в минимальных версиях компилятора цикл repeat/until:
Вызываемые функции также могут быть разбиты на части.
В компиляторе Tiny Context не проверяются символы, следующие за выражениями (в частности, оператор присваивания и точка с запятой после присваивания). Это сделано сознательно для сокращения объема кода (было желание получить работающий код короче 1000 строк), но как выяснилось, может приводить к неочевидным и нежелательным результатам, а именно успешой компиляции некорректной программы и генерации отличного от ожидаемого кода. Пример (фрагмент функции val, преобразующей строку в число):
Знак вопроса вызывает завершение компиляции первого выражения и трактуется как точка с запятой, следующая точка с запятой трактуется как оператор присваивания, оператор присваивания - как точка с запятой, а плюс как оператор присваивания:
Это было обнаружено при переводе компилятора на платформу MOS6502. На месте знака вопроса остался оператор умножения, который не реализовывался и должен был быть заменен вызовом функции mul. В результате код компилировался, но преобразования работали неверно.
В первоначальных вариантах компиляторов Tiny Context для восьмиразрядных систем
CP/M-80 и Apple DOS/6502
для сравнения значений двух выражений генерировался следующий код (пример
проверки условия
Тот же результат можно получить выполнив два вычитания и одно сравнение:
Оба варианта корректны, первый при удачном стечении обстоятельств выполнится быстрее, второй короче и при неудачном для первого варианта стечении обстоятельств выполнится быстрее.
При инициализации ссылки на функцию не проверяется равенство их порядков. Следующий код код компилируется но, естественно, не работает:
Такой код тоже компилируется:
Ошибка была обнаружена только при переходе от версии 2 к версии 3.
Если в программе встречается директива вставки, например
поиск файла system.inc выполняется в текущем каталоге. Если компилируемая программа (и включаемый файл) находятся где-то еще и в командной строке задается путь к ней, то включаемый файл не будет найден (или он будет взят из текущего каталога, если файл с таким именем в нем есть).
Ошибка была обнаружена только при переходе от версии 2 к версии 3.
Ошибка в преобразующей строку в число функции Val присутстует во всех версиях компилятора кроме самой первой. Ошибка была внесена при реализации преобразования строковых представлений чисел в шестнадцатеричной системе счисления. Если строка начинается с префикса, индекс в ней увеличнивается на его длину, затем выполняется цикл преобразования. Но если для строковых представлений чисел в десятичной системе счисления ошибки нет (функция Val вызывается только если строка начинается с цифры), то для представлений чисел в шестнадцатеричной системе нужно еще проверять наличие хотя бы одного символа после префикса. Это не было сделано.
К слову, заимствованное из Turbo Pascal использование $ в качестве префикса не так уж хорошо. Если будет нужно добавить представления чисел в системах счисления с другим основанием (например 2), сделать это по аналогии сложно, т.к. выбор символов для префикса ограничен и неочевиден. Аналогия с 0x лучше, но и здесь не все хорошо. Например, 0o (ноль-о) в качестве префикса числа в восьмеричной системе может восприниматься как два нуля. А вот 0b в качестве префикса числа в двоичной системе счисления вполне подходит.
При компиляции следующего кода происходит ошибка:
При разборе определения глобальной переменной P соответствующий элемент добавлялся в конец словаря, но число элементов словаря увеличивалось на единицу только после разбора инициализирующего выражения. При раборе этого выражения в словарь также могут добавляться элемены - в данном случае безымянная строковая константа.
Ошибка не была обнаружена, поскольку в минимальной версии инициализация не была реализована, соответсвенно в коде самого компилятора она не использовалась.
При компиляции следующего кода выдается сообщение о несовместимости типов:
Результат сравнения ссылки с NULL имеет логический тип для обозначения которого используется константа nDICT (максимально возможное число элементов словаря). Тип устанавливается правильно, но затем при проверке операндов логического сложения выполняется проверка равенства нулю их порядков ссылок (nRef) и это приводит к ошибке т.к. при разборе сравнения с NULL nRef не обнуляется. При проверке типа выражения в условных операторах nRef не анализируется и это не ошибка поскольку ссылок на объекты логического типа быть не может (такие объекты существуют только во время оценки условий и нигде не сохраняются).
Ошибка была обнаружена только в Context 3, куда она благополучно перешла из Context 2. В версиях для DOS этой ошибки не было.
Эта маленькая программа выводила на консоль n внесто x:
следующая программа не могла быть скомпилировалась:
Ошибка появилась в 30-й ревизии Context3.
В начале кода главной функции этой программы не корректировалось значение регистра ESP:
т.е. отсутствовала команда
В результате вызов функции F() значение @S меняется и вместо qwerty на консоль выводится мусор. Немного изменив программу можно получить и Segmentation fault:
Теперь в результате вызов функции F() значение @S становится равным NULL и печать размещенной по этому адресу "строки" приводит к Segmentation fault.
Ошибка в функции нумерации узлов дерева (Enum) была перенесена в Context3 из Context2. Помимо нумерации узлов Enum также должна вычислять общий размер локальных переменных и для блока sequence она этого не делала. И короткое название функции не отражает ее действий...
Ошибка обнаружена в интерпретаторе подмножества Context'а. Следующая функция должна перводить число N в строку дополняя ее пробелами слева до длины S:
Она же использовалась для вывода номера строки в сообщении об ошибке, но при этом значение параметра S задавалось равным нулю. Если номер строки больше или равен десяти в первом рекурсивном вызове ноль превращался в максимальное целое число (0xFFFF или 0xFFFFFFFF в зависимости от разрядности системы) и в последнем рекурсивном вызове в выходной массив записывалось очень много пробелов. Со всеми вытекающими последствиями.
Во втором интерпретаторе этой ошибки не было, но была другая (не проявлявшаяся):
В функции Str в качестве буфера использовалась строковая константа. К ошибке это не приводит только потому, что в функции первода строки в число была проверка переполнения и программа однопоточная.
Вторая функция была перенесена в интерпретатор из Context'а для DOS без изменений.
Ошибка была во всех версиях Context 2.x. Перед выполнениемдеения находящееся в регистре EAX делимое должно быть расширено со знаком до шестидесятичетырехразрядного значения в пере регистров EDX:EAX. Для этого существует команда cdq. Вместо нее выполнялось обнуление значения в регистре EDX.
Ошибка была в Tiny Context для процессора 8080. В качестве основной пары регистров была выбрана пара DE, простая замена ее на пару HL позволяет уменьшить размер кода и увеличить скорость его работы примерно на четверть.
Ошибка была в Tiny Context 1.18. Константа размещается прямо в коде, перед ней безусловный переход, после нее загрузка адреса в регистр AX:
Вместо этого можно использовать
Команда call поместит адрес строки в стек и выполнит переход к метке E, команда pop поместит адрес строки в AX - экономия двух байтов.
Для тестирования быстродействия создаваемого компиляторм кода (а также быстродействия процессоров) использовался в том числе и архиватор, реализующий алгоритм LZSS. Для поиска совпадений в нем был использован алгоритм KMP (Кнута-Морриса-Пратта), для вычисление массива сдвигов образца (Tmp - образец, D - массив сдвигов) был написан следующий неочевидный код:
Сейчас уже невозможно вспомнить, как он был получен. Сделав ряд преобразований, аналогичных приведенным в описании алгоритма КМП, можно получить эквивалентный код (D[0] в поиске не использовался, так что отсутствие его инициализации значения не имеет):
Это почти тоже самое, что приводится во множестве источников, за исключением условия K=0
во второй ветви select'а. Дополнительное условие приводит к тому, что в ряде случаев элементу
D[J] присваивается нуль вместо минус единицы. Работу поиска это не нарушает,
но приводит к небольшим дополнительным затратам. Преобразованный код неоптимален и может
быть немного улучшен.
Собственно поиск совпадений
тоже можно улучшить (и это дает более заметный выигрыш)
Скомпилированный с помощью gcc C-эквивалент исправленного и улучшенного кода на Intel Core i5 работает процентов на двадцать быстрее неоптимального оригинала. Но очень сложно найти те многочисленные машины, на которых тестировался неоптимальный код.
Как-то получулось, что одна из тестовых программ - n0.com - поиск хода в игре ним - была скомпилирована не тем компилятором, да и сама программа тоже была не та. Программа должна была собираться самой первой версией Context'а (0.50) и в ней самой знаковые целые должны были быть заменены беззнаковыми т.к. этом компиляторе знакоый тип не реализован. Вместо этого неизмененный исходный текст был скомпилирован с помощью Context 1.01.
Непонятно, почему это не было сразу замечено - время работы должно отличаться раза в полтора-два.
В беззнаковой версии для обозначения игроков вместо 1 и -1 использованы значения 0 и 1. Для смены игрока использована формула
Она правильна, т.е. преобразует 0 в 1 и 1 в 0, но вычисление остатка от деления - достаточно медленная операция (особенно на 8088/8088). Если бы компилятор поддерживал битовые операции, можно было бы использовать следующую формулу:
Поскольку их нет можно было бы использовать следующий код, но не факт, что это лучше:
Ошибка в версиях 1.3 (DOS) и 1.4 (Win32). Если вызывается функция, возвращающая число с плавающей точкой (real) и ее результат не присваивается никакой переменной и не передается другой функции как параметр, то результат не удаляется из стека сопроцессора. Следующая программа
Преобразуется в некорректный код:
@00002: push BP mov BP,SP fld SS:[BP+4] ;Загрузка параметра в стек сопроцессора fwait mov SP,BP pop BP retn 8 @00003: push BP mov BP,SP mov BX,offset @32768 fld CS:[BX+0] ;Загрузка константы в стек сопроцессора fwait sub SP,8 mov BX,SP fstp SS:[BX] ;Запись параметра в стек fwait call @00002 ;Вызов функции mov SP,BP ;Результат остается в стеке сопроцессора pop BP mov AX,4C00H int 21H
Ошибка в Tiny Context 1.16. Код инициализации переменной
обрабатывается кодом следующим фрагментом кода компилятора:
Ошибка приводит к некоррекной компиляции Tiny Context 1.18 (первой версии, использующей локальные переменные).
Существует последовательность действий, при выполнении которых компиляция все же выполняется успешно:
Видимо, из-за чего-то подобного ошибка не была замечена сразу.
В некорректном коде всего три неверные команды - одна инициализация в функции Stop(), она не влияет на нормальную работу, и две инициализации в функции val():
Вместо слов записваются только их младшие байты и это все портит.
И последнее. Для поиска в словаре использован простой перебор, соответственно время поиска пропорционально квадрату числа имен, уже находящихся в словаре. Но это не ошибка. Точнее проявится она только при компиляции программы, содержащей тысячи или десятки тысяч объектов, например:
Эта программа бессмысленна и число объектов в ней значительно превышает возможности DOS-версии компилятора. Реальная же программа, содержащая такое количество объектов должна быть разбита на части (модули или классы), иначе разобраться в ней будет сложно.