© Иван Рощин, Москва

Z80: оптимизация загрузки констант в регистры

(«Радиолюбитель. Ваш компьютер» 9/2000, 2/2001, под псевдонимом BV_Creator)
Дата последнего редактирования: 24.07.2003.

Процессор Z80, производимый компанией ZiLOG с 1976 года, используется, помимо персональных компьютеров, во множестве других микропроцессорных устройств. Так что эта статья будет полезна не только владельцам ZX Spectrum. Она адресована, во-первых, тем, кто задумал писать оптимизирующий компилятор какого-либо языка высокого уровня (ЯВУ) для Z80, и, во-вторых, тем, кто пишет программы для Z80 на ассемблере и оптимизирует их вручную. Рассматриваемые здесь приёмы оптимизации могут быть применены по аналогии и для других типов процессоров, у которых команды загрузки «регистр –> регистр» или другие команды, изменяющие содержимое регистров, быстрее и/или короче, чем команды загрузки «память –> регистр».

Почему на ZX Spectrum основным языком программирования является ассемблер, а компиляторы Паскаля, Си и других ЯВУ практически не используются? Ведь на этих языках гораздо проще писать программы! Ответ прост: всё дело в том, что формируемая в процессе компиляции программа в машинных кодах получается медленнее и длиннее аналогичной программы на ассемблере. А при небольшом объёме памяти и низком быстродействии ZX Spectrum это имеет решающее значение.

А почему программа получается неоптимальной? Да потому, что компилятор действует довольно примитивно. Надо ему, например, в программе поместить в аккумулятор число 0 — он и сформирует команду LD A,0. А любой хоть сколько-нибудь разбирающийся в ассемблере программист напишет в такой же ситуации команду XOR A, что будет и быстрее, и короче. Программист также учитывает и использует тот факт, что к моменту, когда в регистр надо загрузить константу, может быть известно содержимое некоторых регистров. Например, надо загрузить в аккумулятор число 1, а там находится 0. Понятное дело, вместо LD A,1 пишем INC A. Ещё пример: надо загрузить в аккумулятор 3, а к этому моменту в регистре H как раз оказывается 3 — естественно, пишем команду LD A,H.

Понятно, что компилятор тоже надо научить таким способам оптимизации. Тогда он, вполне возможно, сможет формировать даже более оптимальные программы, чем человек: ведь компилятор рассмотрит все возможные варианты оптимизации и выберет лучший, чего человек при всём желании не способен сделать. Ну кто, например, догадается, что если A=0, а надо получить A=6, то, при соответствующем значении некоторых флагов, можно обойтись одной лишь командой DAA?

Да, вот так мы и подошли вплотную к теме этой статьи. Речь пойдёт об оптимизации загрузки констант в регистры и регистровые пары Z80. Команды загрузки констант — одни из наиболее часто встречающихся, и их оптимизация принесёт неплохой выигрыш в объёме и быстродействии.

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

Команды LD XH,n, LD XL,n, LD YH,n, LD YL,n — недокументированные, но, тем не менее, использующиеся во многих программах.

Пусть к тому моменту, когда в регистр или в регистровую пару должна быть помещена константа, нам известно хоть что-то из нижеперечисленного:

• содержимое всех или некоторых регистров процессора;
• значения всех или некоторых флагов;
• содержимое каких регистров больше не нужно;
• значение каких флагов больше не нужно.

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

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

1. Если известно, что в регистре или регистровой паре уже находится то число, которое надо туда занести, то никакой команды не требуется, и в объектный код ничего не добавляем. Экономия составит от 2 до 4 байтов/от 7 до 14 тактов, в зависимости от вида регистра или регистровой пары.
2. Если надо поместить константу в один из регистров A, B, C, D, E, H, L (обозначим его R1) и известно, что эта константа уже содержится в другом регистре (также в одном из A, B, C, D, E, H, L — обозначим его R2), то помещаем в объектный код команду LD R1,R2. Экономия составит 1 байт/3 такта.

   Пример: надо поместить #23 в регистр D; знаем, что в регистре B также #23; помещаем в объектный код команду LD D,B.

   Примечание: под словами «помещаем в объектный код команду…» имеется в виду помещение в объектный код соответствующих данной команде машинных кодов. Отметим также, что компилятор может формировать не объектный, а непосредственно исполняемый код.

3. Если надо поместить константу в один из регистров XH, XL (обозначим его R1) и известно, что эта константа уже содержится в другом регистре (в одном из A, B, C, D, E, XH, XL — обозначим его R2), то помещаем в объектный код команду LD R1,R2. Экономия составит 1 байт/3 такта.

   Пример 1: надо поместить #76 в регистр XH; знаем, что в регистре A также #76; помещаем в объектный код команду LD XH,A.

   Пример 2: надо поместить #18 в регистр XL; знаем, что в регистре XH также #18; помещаем в объектный код команду LD XL,XH.

4. Если надо поместить константу в один из регистров YH, YL (обозначим его R1) и известно, что эта константа уже содержится в другом регистре (в одном из A, B, C, D, E, YH, YL — обозначим его R2), то помещаем в объектный код команду LD R1,R2. Экономия составит 1 байт/3 такта.

   Пример 1: надо поместить #29 в регистр YH; знаем, что в регистре E также #29; помещаем в объектный код команду LD YH,E.

   Пример 2: надо поместить #74 в регистр YL; знаем, что в регистре YH также #74; помещаем в объектный код команду LD YL,YH.

5. Если надо поместить константу в одну из регистровых пар BC, DE, HL, IX, IY и известно, что один из байтов константы уже находится на своём месте, переформулируем задачу оптимизации: надо поместить оставшийся байт константы в соответствующий регистр регистровой пары, причём так, чтобы не изменить значение уже находящегося на своём месте байта. Экономим как минимум 1 байт/3 такта.

   Пример: надо поместить #2574 в HL; знаем, что H=#25. Пробуем решить задачу оптимизации загрузки #74 в регистр L — даже если это не получится, в объектном коде будет команда LD L,#74, что всё равно короче и быстрее, чем LD HL,#2574.

6. Если надо поместить константу в одну из регистровых пар BC, DE, HL (обозначим эту регистровую пару RR) и известно, что значение старшего байта константы есть в одном из регистров A, B, C, D, E, H, L (обозначим этот регистр R1), а значение младшего байта константы также есть в одном из этих регистров (обозначим его R2), то оптимизацию можно выполнить, поместив в объектный код команды LD RRH,R1: LD RRL,R2 (где RRH и RRL — старший и младший регистры регистровой пары RR). Экономия составит 1 байт/2 такта.

   Внимание! Надо учитывать, что после выполнения первой команды LD значение регистра RRH изменится, и если R2 совпадает с RRH, то оптимизацию выполнить нельзя. Иногда в этом случае помогает перестановка команд LD местами.

   Пример 1: надо поместить #1234 в HL; знаем, что A=#12, E=#34; помещаем в объектный код команды LD H,A: LD L,E.

   Пример 2: надо поместить #7536 в BC; знаем, что A=#75, B=#36; помещаем в объектный код команды LD C,B: LD B,A (именно в этом порядке!).

   Пример 3: надо поместить #8762 в DE; знаем, что D=#62, E=#87. Тем не менее, оптимизацию выполнить нельзя.

7. Если надо поместить константу в одну из регистровых пар BC, DE, HL (обозначим эту регистровую пару RR) и известно, что значение регистровой пары AF как раз равно этой константе (для установления этого факта компилятору придётся отслеживать значение регистра флагов, включая и недокументированные флаги), то можно поместить в объектный код команды PUSH AF: POP RR. Экономия составит 1 байт/–11 тактов (т.е. теряем в скорости за счёт сокращения длины). Это может пригодиться, когда малый объём программы важнее скорости её выполнения.
8. Если надо поместить константу в регистровую пару IX или IY (обозначим эту пару RR1) и известно, что эта константа уже содержится в одной из регистровых пар AF, BC, DE, HL (обозначим её RR2), то можно поместить в объектный код команды PUSH RR2: POP RR1. Как и в предыдущем случае, выигрыш в длине составит один байт, а проигрыш в скорости — 11 тактов.
9. Если надо поместить константу в регистровую пару HL (или DE) и известно, что содержимое регистровой пары DE (или HL) больше не понадобится, то поступаем так: пробуем решить задачу оптимизации помещения требуемой константы в DE (HL), и если получилось сделать это менее чем за 2 байта и/или 6 тактов, то затем помещаем в объектный код ещё команду EX DE,HL. При этом удаётся сэкономить в длине и/или скорости (сколько именно — зависит от конкретного случая, максимум — 2 байта/6 тактов).

   Пример 1: надо поместить в HL константу #1653. Известно, что DE=#1653 и DE больше не понадобится. Помещаем в объектный код команду EX DE,HL. Экономия составит 2 байта/6 тактов.

   Пример 2: надо поместить в DE константу #8736. Известно, что HL=#8735, HL больше не понадобится, изменять флаги нельзя. Решая задачу оптимизации помещения #8736 в HL, получим, что это можно сделать командой INC HL за 1 байт/6 тактов. Это удовлетворяет ограничению в 2 байта/6 тактов. Помещаем в объектный код ещё команду EX DE,HL. Экономия составит 1 байт/0 тактов.

10. Если надо поместить константу в одну из регистровых пар BC, DE, HL и известно, что значения регистровых пар BC, DE, HL, BC', DE', HL' (за исключением той пары, в которую надо поместить константу) больше не нужны (или даже если значение какой-либо регистровой пары ещё понадобится, но так оказалось, что это значение равно значению альтернативной регистровой пары), то поступаем так: помещаем в объектный код команду EXX, а затем решаем задачу оптимизации помещения константы в нужную регистровую пару с учётом того, что основной и альтернативный набор регистров поменялся местами. Если получилось сделать это менее чем за 2 байта и/или 6 тактов, то оптимизация удалась (а если не удалась — естественно, команду EXX из объектного кода надо убрать). Экономия зависит от конкретного случая, максимум — 2 байта/6 тактов.

    Пример 1: надо поместить в BC константу #8624; известно, что BC'=#8623, значения BC', DE', HL', DE, HL и регистра флагов больше не понадобятся. Помещаем в объектный код команду EXX. Решаем задачу помещения #8624 в BC с учётом того, что BC теперь равно #8263. Это можно сделать командой INC C за 1 байт/4 такта, что удовлетворяет ограничению в 2 байта/6 тактов. Экономия составит 1 байт/2 такта.

    Пример 2: надо поместить в HL константу #7258; известно, что DE'=#7258, BC=#1289, BC'=#1289, значения DE', HL', DE больше не понадобятся. Помещаем в объектный код команду EXX. Решаем задачу помещения #7258 в HL с учётом того, что DE теперь равно #7258. Это можно сделать командой EX DE,HL за 1 байт/4 такта, что удовлетворяет ограничению в 2 байта/6 тактов. Экономия составит 1 байт/2 такта.

11. Если надо поместить в аккумулятор константу, которая уже содержится в A', и если значение A' больше не нужно и если флаги позволяют, помещаем в объектный код команду EX AF,AF'. Экономия составит 1 байт/3 такта.

    Что здесь и далее мы будем понимать под выражением «если флаги позволяют»? Вот что: либо если разрешено менять значения всех флагов, либо если можно менять значения не всех флагов или вообще нельзя менять флаги, но известно значение флагов до выполнения команды, и знаем, что после выполнения команды флаги, значения которых нельзя менять, не изменятся.

    Кстати, в этом случае это касается и альтернативного регистра флагов.

    Пример: надо поместить в аккумулятор #47; известно, что A'=#47; значение AF' больше не понадобится; значение флага C нельзя менять, но известно, что он одинаково установлен как в основном, так и в альтернативном флаговом регистре. Помещаем в объектный код команду EX AF,AF'.

12. Если надо поместить в аккумулятор константу, которую можно получить с помощью одной из операций ADD, ADC, SUB, SBC, AND, OR, XOR, где в качестве второго операнда выступает один из регистров A, B, C, D, E, H, L, и если флаги позволяют, то помещаем в объектный код соответствующую команду. Экономия составит 1 байт/3 такта.

    Пример 1: надо поместить в аккумулятор 0, сохранив при этом значение флага N (известно, что N=1) и не сохраняя значение всех других флагов. Помещаем в объектный код команду SUB A.

    Пример 2: надо поместить в аккумулятор #25; известно, что флаг CY=1; сохранять значения флагов не нужно. Известно, что A=#20, B=4. Помещаем в объектный код команду ADC A,B.

13. Если надо поместить в аккумулятор константу, которую можно получить с помощью одной из операций CPL, RLCA, RLA, RRCA, RRA, DAA, и если флаги позволяют, то помещаем в объектный код соответствующую команду. Экономия составит 1 байт/3 такта.

    Пример 1: надо поместить в аккумулятор #55; знаем, что A=#AA; знаем, что надо сохранить значения флагов CY и Z. Помещаем в объектный код команду CPL.

    Пример 2: надо поместить в аккумулятор 6; знаем, что A=0; знаем, что флаг H=1, флаг N=0, и что сохранять значения флагов не нужно. Помещаем в объектный код команду DAA.

14. Если надо поместить константу в один из регистров A, B, C, D, E, H, L, XH, XL, YH, YL (обозначим его R1), а в этом регистре находится значение на единицу меньше (больше) требуемого (по модулю 256), и если флаги позволяют, то помещаем в объектный код команду INC (DEC) R1. Экономия составит 1 байт/3 такта.

    Пример 1: надо поместить #23 в регистр D, а в этом регистре находится #22. Помещаем в объектный код команду INC D.

    Пример 2: надо поместить #FF в регистр XH, а в этом регистре находится 0. Помещаем в объектный код команду DEC XH.

15. Если надо поместить константу в одну из регистровых пар BC, DE, HL, IX, IY (обозначим её RR1), а в этой регистровой паре находится значение на единицу меньше (больше) требуемого (по модулю 65536), то помещаем в объектный код команду INC (DEC) RR1. Экономия составит 2 байта/4 такта.

    Пример: надо поместить #13FF в BC, а там находится #1400. Помещаем в объектный код команду DEC BC.

16. Если надо поместить константу в один из регистров C, E, L, XL, YL (обозначим его R1, а регистровую пару, в которую он входит, — RR1), изменять значения флагов нельзя, и известно, что в этом регистре находится значение на единицу меньше (больше) требуемого (не по модулю 256, а по абсолютной величине!), то помещаем в объектный код команду INC (DEC) RR1. Экономия составит 1 байт/1 такт.

    Пример: надо поместить #32 в C; знаем, что C=#31 и изменять значения флагов нельзя. Помещаем в объектный код команду INC BC.

17. Если надо поместить константу в один из регистров B, C, D, E, H, L, XH, XL, YH, YL (обозначим его R1, регистровую пару, в которую он входит, — RR1, а второй регистр пары RR1 — R2), и если известно значение RR1, то можно попробовать сделать это с помощью команды INC RR1 или DEC RR1. Eсли R1 — один из регистров H, L, XH, XL, YH, YL, то, кроме INC/DEC, можно попробовать и команды ADD RR1,RR1; ADD RR1,BC; ADD RR1,DE; ADD RR1,SP, если флаги позволяют. При этом надо учитывать, что содержимое R2 может быть испорчено. Экономия составит 1 байт/1 такт при использовании INC/DEC и 1 байт/–4 такта при использовании ADD.

    Пример 1: надо поместить #82 в D; знаем, что DE=#81FF, значение E больше не понадобится, флаги изменять нельзя. Помещаем в объектный код команду INC DE.

    Пример 2: надо поместить #40 в H; знаем, что HL=#2000 и сохранять флаги не нужно. Помещаем в объектный код команду ADD HL,HL.

    Пример 3: надо поместить #12 в XL; знаем, что IX=#5309, значение XH больше не понадобится, сохранять флаги не нужно. Помещаем в объектный код команду ADD IX,IX.

    Пример 4: надо поместить #25 в H; знаем, что HL=#1000, BC=#1500; можно изменять флаги, кроме Z. Помещаем в объектный код команду ADD HL,BC.

18. Если надо поместить константу в H (XH, YH), текущее значение H (XH, YH) известно, а значение L (XL, YL) неизвестно, однако менять его нельзя, можно (если флаги позволяют) использовать следующий факт: команды ADD HL,BC (ADD IX,BC; ADD IY,BC), ADD HL,DE (ADD IX,DE; ADD IY,DE) и ADD HL,SP (ADD IX,SP; ADD IY,SP) не изменят регистр L (XL, YL), если младший байт второго слагаемого (соответственно BC, DE и SP) равен нулю. Экономия составит 1 байт/–4 такта.

    Пример: надо поместить #70 в XH; знаем, что XH=#20, SP=#5000; можно менять значения всех флагов, кроме Z и S. Помещаем в объектный код команду ADD IX,SP.

19. Если надо поместить константу в L (XL, YL), текущее значение L (XL, YL) известно, а значение H (XH, YH) неизвестно, однако менять его нельзя, можно (если флаги позволяют) использовать следующий факт: команды ADD HL,BC (ADD IX,BC; ADD IY,BC), ADD HL,DE (ADD IX,DE; ADD IY,DE) и ADD HL,SP (ADD IX,SP; ADD IY,SP) не изменят регистр H (XH, YH), либо если старший байт второго слагаемого (соответственно BC, DE и SP) равен нулю и переноса в старший байт при сложении не будет, либо если старший байт равен #FF и при сложении произойдёт перенос в старший байт. Экономия составит 1 байт/–4 такта.

    Пример 1: надо поместить в L #26; знаем, что L=#10, BC=#0016, сохранять флаги не нужно. Помещаем в объектный код команду ADD HL,BC.

    Пример 2: надо поместить в YL #70; знаем, что YL=#74, DE=#FFFC, сохранять флаги не нужно. Помещаем в объектный код команду ADD IY,DE.

20. Если в одну из регистровых пар HL, IX, IY (обозначим её RR1) надо поместить константу, которая может быть получена с помощью одной из операций ADD RR1,RR1; ADD RR1,BC; ADD RR1,DE; ADD RR1,SP, то помещаем в объектный код соответствующую команду (если флаги позволяют). Экономия составит 2 байта/–1 такт.

    Пример 1: надо поместить в HL #AAAA; знаем, что HL=#5555, сохранять флаги не нужно. Помещаем в объектный код команду ADD HL,HL.

    Пример 2: надо поместить в IX #7624; знаем, что IX=#1211, DE=#6413, сохранять флаги не нужно. Помещаем в объектный код команду ADD IX,DE.

21. Если в регистровую пару HL надо поместить константу, которая может быть получена с помощью одной из операций ADC HL,HL; ADC HL,BC; ADC HL,DE; ADC HL,SP; SBC HL,HL; SBC HL,BC; SBC HL,DE; SBC HL,SP, то помещаем в объектный код соответствующую команду (если флаги позволяют). Экономия составит 1 байт/–5 тактов.

    Пример 1: надо поместить в HL 0; знаем, что CY=0 и сохранять флаги не нужно. Помещаем в объектный код команду SBC HL,HL.

    Пример 2: надо поместить в HL #2299; знаем, что HL=#2266, BC=#0032, CY=1 и сохранять флаги не нужно. Помещаем в объектный код команду ADC HL,BC.

22. Возьмём два множества команд: первое — (ADD HL,HL, ADD HL,BC, ADD HL,DE), второе — (ADD HL,HL, ADD HL,BC, ADD HL,DE, INC H, DEC H, INC L, DEC L, INC HL, DEC HL). Если в регистровую пару HL надо поместить константу, то можно попробовать (если флаги позволяют) сделать это с помощью двух команд, одна из которых взята из первого множества, а другая — из второго. Экономия памяти составит 1 байт, а потеря быстродействия будет зависеть от того, какая команда была выбрана из второго множества: INC H, DEC H, INC L или DEC L — 5 тактов; INC HL или DEC HL — 7 тактов; ADD HL,HL, ADD HL,BC или ADD HL,DE — 12 тактов.

    Пример 1: надо поместить в HL #8080; знаем, что HL=#2020 и сохранять флаги не нужно. Помещаем в объектный код команды ADD HL,HL: ADD HL,HL.

    Пример 2: надо поместить в HL #8081; знаем, что HL=#4040 и сохранять флаги не нужно. Помещаем в объектный код команды ADD HL,HL: INC L.

    Пример 3: надо поместить в HL #8082; знаем, что HL=#4040 и сохранять флаги не нужно. Помещаем в объектный код команды INC L: ADD HL,HL.

    Пример 4: надо поместить в HL #1234; знаем, что HL=#1111, DE=#0111, BC=#0012 и сохранять флаги не нужно. Помещаем в объектный код команды ADD HL,DE: ADD HL,BC.

23. Если в одну из регистровых пар HL, IX, IY (обозначим её RR1) надо поместить константу, которая может быть получена с помощью одной из операций ADD RR1,RR1; ADD RR1,BC; ADD RR1,DE; ADD RR1,SP, и если известно, что содержимое флага переноса нельзя изменять, а в результате выполнения команды ADD оно изменится на противоположное, то после помещения в объектный код команды ADD помещаем ещё команду CCF (инвертирование флага переноса). Экономия составит 1 байт/–5 тактов.

    Пример 1: надо поместить в HL #1234; знаем, что HL=#1123, DE=#0111, флаг переноса установлен и изменять его нельзя. Помещаем в объектный код команды ADD HL,DE: CCF.

    Пример 2: надо поместить в IY 0; знаем, что IY=#FFF0, BC=#0010, флаг переноса сброшен и изменять его нельзя. Помещаем в объектный код команды ADD IY,BC: CCF.

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

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

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

Может быть, кто-то хотел бы написать компилятор ЯВУ для ZX Spectrum, но его останавливают такие проблемы, как реализация редактора, интерфейса с пользователем и т.п.? Могу посоветовать вот что: в ассемблере ZX ASM 3.10 прекрасный интерфейс, и компилятор сделан в виде отдельного оверлея. Таким образом, никто не мешает написать компилятор любого другого языка (C, Pascal и т.д.) и подключить его к ZX ASM.

И ещё коснусь вопроса оптимизации. Хотелось бы, чтобы в Интернете был сайт, специально посвящённый оптимизации кода Z80, чтобы программисты со всего мира могли воспользоваться размещённой там информацией (и добавить свою). Не знаю — возможно, что-то подобное уже существует? Если нет — может быть, кто-нибудь этим займётся?