Из журнала Info Guide #7, Рязань, 06.2005 (в текст внесены исправления из Errata IG#8) Основы оптимизации под Z80 Существует 4 направления оптимизации:по размеру, по скорости, по сжатому размеру и по объёму исходника. На последнем останав- ливаться здесь не будем. Оптимизация по размеру 1. Если структура программы определена, следует подсчитать количество обращений к каждой процедуре (это очень легко - изме- нить метку её названия и попытаться оттра- нслировать), а на основании этого числа и её,процедуры,размера можно решить вопрос о лишении её статуса подпрограммы и внесении в вызывающий фрагмент. Иногда подпрограмма от этого не выигрывает. Например, в случае множества условных возвратов (они короче условных переходов) в ней. CALL addr : RET заменяется на JP addr или, если возможно, JR addr. Ещё лучше пе- ренести фрагмент с JP к указанному в нём адресу. CALL addr:JP addr2 упрощается аналогич- но: переносом вплотную к указанному в CALL адресу и заменой упомянутой конструкции на LD BC,addr2:PUSH BC. Крупный цикл наподобие опроса клавиш - с большим количеством переходов на одну и ту же точку - логично сократить так же, занося адрес точки на стек и пользуясь ус- ловными возвратами. Сложную систему условий часто удаётся привести к какому-либо виду, содержащему таблицу, возможно, обрабатываемую командой CPIR. Окончания циклов вида JR NZ,exit:CALL addr:JR Z,loop:exit приводятся к виду CALL Z,addr:JR Z,loop. Иногда для этого прихо- дится менять признаки завершения в подпро- грамме addr, а подчас и создавать эту под- программу, если её нет :) Разумным распределением соглашений о флагах на выходе из разных процедур (не- плохо использовать факты, что п/п такая-то всегда устанавливает CY, а другая п/п пре- дпочитает сбрасывать Z ). можно добиться более частого использования условных вызо- вов и сэкономить тем самым немало байт и строчек кода. Полезно время от времени прогуляться по исходнику и записать самые популярные фра- гменты вызова некоторых процедур. Часто перед CALL стоят однотипные команды. Это позволяет внести их в начало процедуры,по- льзуясь тем, что в ассемблере,в отличие от ЯВУ, возможно сколько угодно точек входа в процедуру! В конце концов процедуры склеи- ваются в ёлки наподобие такой: OUT0 LD A,16 JR $+4 OUT7 LD A,23 OUTME LD (pg),A OUTNO PUSH BC LD BC,32765 OUT (C),A POP BC RET И это ещё не самый крупный экземпляр!:) Если же,например,после CALL часто стоит какая-либо операция, которая в других слу? чаях безвредна (что-то вроде OR A или LD HL,(addr) ), можно подставить эту операцию в конец самой процедуры. Бывают случаи,ко- гда ничего подставить нельзя,но оказывает- ся выгодным сделать промежуточную вызывал- ку процедуры - с самыми частыми командами, сопутствующими этому вызову. Приведённые рекомендации относятся к организации программы и почти не касаются её внутреннего устройства. На следующей странице мы поговорим и об устройстве. По- путно отметим здесь, что существует способ программирования без использования команд CALL, а также средство экономии памяти пу- тём создания интерпретируемой или компили- руемой системы команд (скрипта). 2. Есть ряд конструкций, неоптимальных с точки зрения размера / скорости / регист- ров практически всегда.Вот несколько таких "запрещённых конструкций": SLA A (заменяется на ADD A,A ); SLA L:RL H (заменяется на ADD HL,HL ); RL L:RL H (заменяется на ADC HL,HL ); Два последних совета можно применить к другим похожим случаям, если перераспреде- лить регистры; Полная альтернатива вида JR C,cy LD reg,число JR ok cy LD reg,число2 ok (заменяется на LD reg,число2: JR C,ok: LD reg,число: ok или, если reg - аккумуля- тор: SBC A,A:AND число!число2:XOR число ); PUSH HL:SBC HL,DE:POP HL (заменяется на SBC HL,DE : ADD HL,DE - проверьте: флаги в том же состоянии!); -Из Errata #IG8--------------------------- В случае с PUSH HL:SBC HL,DE:POP HL име- лось в виду CY=0. ------------------------------------------ DEC B:JR NZ,loop (заменяется на DJNZ, если не важен флаг Z ) - можно перераспре- делить регистры ради такой оптимизации; LD L,(IX) INC HX LD H,(IX) DEC HX INC IX (заменяется на LD L,(IX-128):INC IX:LD H, (IX+127) с другим нач. значением IX ); LD A,reg:OR A (кроме индексных; заменя- ется на INC reg:DEC reg ); В дальнейшем вы найдёте и другие. Попадаются возможности избежать счётчи- ка цикла, если выходить по переполнению младшего байта адреса: INC L:JR NZ,loop. Многие условные вычисления, связанные с инкрементом (и не только), удобнее органи- зовать арифметически. Самым эффективным способом размещать переменные программы почти всегда будут встроенные в текст переменные вида: var1=$+1 LD DE,0 Из всех мест, где переменная упоминает- ся, для этого следует выбирать место,в ко- тором выигрыш максимален (например, где рассматриваемую переменную вычитают). Другой вариант размещения - в блоке си- стемных переменных Бейсика (IY+disp) - вы- годен при большом количестве таких же эк- зотических действий с переменной, как упо- мянутое вычитание.Тем более, IY часто про- стаивает. Понятно, что вариант с IY будет короче, чем LD HL,var1:SUB (HL), но длин- нее LD HL,var1:LD A,(HL):XOR 1:LD (HL),A. Подпрограмма с возможностью затыкания входа реализуется подставлением или убира- нием команды RET в её начале, без каких бы то ни было переменных. Часто можно посчитать сплошной кусок программы состоящим из нескольких последо- вательных действий. Обычно бессознательно мы пишем эти секции независимыми от резу- льтатов друг друга. Это важно для "быстро- го" (или "экстремального") программирова- ния (термин для программирования без опти- мизации и поиска ошибок - когда на это нет времени,нужно гарантировать их изначальное отсутствие). Но противопоказано для опти- мизации. Как правило,после какого-либо ци- кла ряд регистров содержит нуль.Между тем, нули могут потребоваться ниже (возможно,не в других регистрах и не в соседних эта- пах). Перестановкой регистров и этапов мо- жно выигрывать значительные объёмы. За счёт перестановки регистров можно перенести большинство 16-разрядных опера- ций в регистровую пару HL, освободить ин- дексные регистры, получить дополнительный операнд в стеке через EX (SP),HL, свести операции память-память к команде LDI (LDD) и т.п. Обращайте внимание на команды инициали- зации регистров и флагов.На всякий случай, вписывая их, всегда выделяйте (например, сдвигом строки текста влево).Это будет на- поминанием,что при удачном стечении обсто- ятельств команды можно закомментировать. Одинаковые инициализации можно также про- водить через PUSH...POP. При оптимизации используют и свойства циклов:они бывают разнонаправленные;бывают со входом в середину,с выходом из середины или со стандартным входом-выходом; параме- трические и по условию; с прединкрементом и постинкрементом (можно переносить часть операций из конца цикла в начало и наобо- рот). Допустимо использовать фрагменты ПЗУ, которые вам понравятся. В ПЗУ 48k реализо- ваны многие полезные действия, не послед- ними из которых являются LDDR : RET (адрес 5729=#1661 ) и LDIR : RET (адрес 13251= =#33C3 ), идеальные для условных вызовов и условных переходов. Но несовместимость,ко- торая может получиться, если вы программи- руете по ВАШЕ нестандартное ПЗУ, будет це- ликом именно на ВАШЕЙ совести :). Базовый вариант ПЗУ - 1982 года, далее происходили дополнения (следует, впрочем,отличать 1982 от SOS 128k, тоже помеченного этой датой). С точки зрения памяти, часто бывает вы- годно хранить упакованными отдельные редко используемые части программы - пусть не код, а описание, или часть шрифтов, карт и т.п.При последующем "склеивании" программы есть резон не паковать уже сжатые таким образом части. Оптимизация по сжатому размеру Во многих случаях важен не объём памя- ти, занимаемый программой, а её размер на диске или в ПЗУ (будь она прошивкой). Гра- мотное использование упаковщиков позволяет решить многие аспекты этой проблемы. Большинство применяемых для сжатия кода упаковщиков основано на методах LZ (A. Lempel, J.Ziv) - копирования повторяющихся участков из уже распакованной половины файла в ещё не распакованную. Желательно знать и точный формат упакованных данных, но и основных представлений достаточно. Важную роль в определении физического размера программы будет играть загрузчик и детали,ему сопутствующие: распаковщик,блок SETUP (настройки программы),процедуры ини- циализации.Инициализация тоже вошла в этот список,поскольку хранение её в памяти ПОС- ЛЕ запуска программы чаще не обосновано - наравне с другими частями загрузчика.Но не всегда:распаковщик может использовать сама программа для извлечения нужных её данных из файлов, а загрузчиком (если он турбиро- ванный) тоже не грех воспользоваться сно- ва,без его повторения в рабочей части про- граммы. Встречаются,конечно,и случаи,когда программа должна иметь возможность сохра- нять саму себя, и ей приходится держать в памяти все свои части. Для достижения наибольшей компрессии и оптимального использования хвостов секто- ров лучше всего иметь единственный упако- ванный блок (если не один упакованный, то по крайней мере загружаемый - один),с дан- ными, разбрасываемыми впоследствии по раз- ным частям памяти. Число перебросок лучше продумать и сократить ещё на этапе разра- ботки программы. Впрочем, столкнувшись с этим, нетрудно лишний раз исправить прог- рамму с точки зрения распределения памяти, изменив пару констант. При компрессии музыкальных и графичес- ких данных нужно выбирать наиболее подхо- дящие форматы и компрессоры.Однако при ма- лом количестве таких данных общий компрес- сор/декомпрессор выгоднее. Оптимизация кода для сжатия являет со- бой особую проблему. Здесь помогает только метод проб и ошибок. Но, в частности, оче- видно, что: - похожие блоки программы следует разме- щать рядом; - некоторые циклы выгодно раскрывать в конструкцию DUP...EDUP ; - серия JP на один адрес пакуется лучше, чем серия таких же JR ; - все области с необязательным содержи- мым (переменные) лучше заполнить нулями или кодами соседних команд; - области буферов лучше исключать из ко- дового блока. Для экспериментов с упаковкой проще всего отассемблировать и выгрузить неско- лько вариантов программы,после чего пооче- рёдно сжимать их компрессором(ами). Оптимизация по скорости Перед проведением оптимизации по скоро- сти не мешает провести оптимизацию и по размеру - с целью удаления паразитных кус- ков кода,но избегая добавления лишних вло- женностей CALL...RET. В дальнейшем оптимизируемая по скорости программа может как уменьшаться по длине, так и увеличиваться. Изначально оптимизации подвергаются ал- горитмы. Многие вещи можно производить ты- сячей способов: сортировку, умножение,про- крутку экрана,спектральные преобразования, декодирование Хаффмана, геометрические по- строения, чтение байтов с диска и т.д. Тот способ, который может быть менее оправдан с точки зрения размера и простоты реализа- ции, порой оказывается более быстрым. Например,умножение через "квадрат полу- суммы минус квадрат полуразности" требует предварительной генерации таблицы квадра- тов и,соответственно,выделения под неё па- мяти, быстрая сортировка может быть вообще не наглядной, а быстрое декодирование Хаф- фмана - не только не наглядным, но ещё и труднопроверяемым. Но тем не менее,они вы- годны по скорости. Разумеется,всё ускорять не надо,тем бо- лее варварскими методами табличного вида, заполняющими всю память. Нужно выбирать именно те части программы, которые влияют на время её выполнения особенно сильно. В простейших случаях такая часть одна: она называется "внутренний цикл" (inner loop) и находится легко - в месте самой глубокой вложенности многоярусного цикла.Как прави- ло, циклы, число проходов которых исчисля- ется тысячами, а то и миллионами, сводят к табличным операциям и раскрывают в первую очередь.(Раскрытие цикла заключается в за- мене его повторами типа DUP...EDUP.) Кроме того,продумывают всевозможные варианты за- писи с разными регистрами и в каждом слу- чае считают такты. Может, однако,оказаться,что цикл второй вложенности (если считать изнутри) содер- жит так много команд, что замедляет прог- рамму сильнее внутреннего. Между тем,о нём часто забывают и потому не учитывают. Более сложный вариант - программа со множеством поочерёдно проводимых операций. Если операции заключены в серию циклов, затруднительно даже выяснить, сколь долго в сумме выполняется каждая из них. Подсчи- тать число проходов можно,поставив в любом месте: PUSH AF LD A,0 ADD A,1 LD ($-3),A LD A,0 ADC A,0 LD ($-3),A LD A,0 ADC A,0 LD ($-3),A (и т.д.) POP AF Если найдётся способ оценить среднее количество тактов в каждой операции,то,уз- нав количество проходов, мы получим и вре- мя. Можно попытаться подсчитывать и преры- вания.Можно исключать процедуры по одной и сравнивать общее время. В зависимости от вклада, вносимого каж- дой процедурой,можно выбрать две-три-деся- ток самых неторопливых и заняться ускоре- нием именно их.Ускорение заключается в вы- боре разных реализаций простейших операций и удобного для них разделения регистров процессора. Желательно содержать все обра- батываемые данные, сколько возможно, в ре- гистрах - с минимальным использованием па- мяти.Используйте альтернативные наборы. IX и IY здесь лучше к применению в роли сум- маторов или счётчиков цикла, поскольку об- ращение через них к памяти дольше обычно- го. (Опять-таки,бывают и обратные случаи.) Будьте также осторожны с IY - при режиме прерываний IM 1 или вызовах RST 56 модифи- цировать его опасно. Данные удобно размещать по круглым ад- ресам, что упростит расчёт этих адресов, а заодно сможет позволить заменять что-ни- будь вроде INC HL на, скажем, INC L. После внедрения семейства таблиц можно перейти к рассмотрению возможностей ОБХО- ДОВ процедур в каких-либо случаях, с соот- ветствующей подменой результата. В конце концов запретите прерывания и задействуйте стек - либо как хранилище потока данных на ввод или вывод,либо как дополнительное 16- разрядное слагаемое при вычислениях. Если показалось, что близок тупик,ищите другой алгоритм. Как правило,он находится. Больше заранее просчитанных данных;исполь- зование особенностей стека ( LD SP,HL, ав- тоинкремент,таблицы процедур,цепочки вызо- вов в стеке); другие форматы таблиц,умень- шающие количество упоминаемых констант;для визуальных эффектов - огрубление вычисле- ний,поблочный вывод...и вообще ЛЮБЫЕ дикие идеи, какие только придут в вашу голову. Далеко не все варианты испробованы, велик шанс найти что-то новое, ни с кем не сове- туясь! Процедуры ПЗУ для использования в программах Добавляю несколько интересных процедур ПЗУ к списку уже известных 8880,8020,3584 и т.д. Некоторые из этих процедур очень корот- кие,и можно задаться вопросом:зачем их ис- пользовать?Однако даже такие очень полезны для оставления в качестве адресов на стеке - этакий Форт. Список публикуется впервые. #e88: ;HL=экранный адрес с прибавлением #800 LD A,H RRCA*3 DEC A OR #50 LD H,A EX DE,HL ;DE=атрибутный адрес LD H,C,L,B ;B=например, число ;атрибутных строк, ;C=например, 0 ADD HL,HL*5 LD B,H,C,L ;BC=HL=CB*32 RET #e9b: LD A,24 SUB B #e9e: LD D,A RRCA*3 AND #E0 LD L,A LD A,D AND #18 OR #40 LD H,A ;HL=адрес A-й знакоместной ;строки RET #1117: INC HL LD (HL),E INC HL LD (HL),D SCF RET #1660: EX DE,HL LDDR RET #169a: LD D,(HL) INC HL LD E,(HL) RET #16fd: LD (HL),C INC HL LD (HL),B RET #172d: LD C,A LD B,0 ADD HL,BC LD C,(HL) INC HL LD B,(HL) DEC HL RET #18b9: INC HL*6 LD A,(HL) RET #19f5: ADD HL,DE PUSH DE LDIR POP HL RET #1bb0: RST 8 DB #FF ;"0 OK..." #1c19: LD C,(HL) INC HL LD B,(HL) EX DE,HL PUSH BC RET #1e7d: OUT (C),A RET #229b: устанавливает цвет бордюра и 23624 по A #231a: LD C,1 RET Z LD C,-1 RET #2aee: EX DE,HL INC HL LD E,(HL) INC HL LD D,(HL) RET #2ba6: EX DE,HL LD A,B OR C RET Z PUSH DE LDIR POP HL RET #2f8b: PUSH DE LD L,A,H,0 LD E,L,D,H ADD HL,HL ADD HL,HL ADD HL,DE ADD HL,HL ;HL=A*10 LD E,C ADD HL,DE ;HL=A*10+C LD C,H,A,L POP DE RET #3406: A=BC=A*5 ADD HL,BC RET #350b: PUSH HL LD A,0 LD (HL),A INC HL LD (HL),A INC HL RLA LD (HL),A RRA INC HL LD (HL),A INC HL LD (HL),A POP HL RET A. Coder