Code (Text): ;===================================================================== lea ecx,[eax*2+eax] ; eax*3 *77 shl eax,4 ; eax*16 lea eax,[eax*4+eax] ; eax*16*5 sub eax,ecx ; eax*16*5 - eax*3 ;=====================================================================
bogrus Для 18,26,33,77 можно и за меньшее число инструкций сделать All Для 65 найдено решение в 2 инструкции. Для 23,37,91 найдены решения в 3 инструкции. Также найдены оптимальные решения для некоторых констант не входивших в задание 8) Но в общем активности не наблюдается, неужели ни одна из оставшихся констант вам не нравится? 33 39 41 53 52 54 56 57 58 61 67 68 70 71 77 78 79 83 85 87 89 90
61,41,52,65: Code (Text): .data const_61 dd 04325C54h const_41 dd 063E7064h const_52 dd 04EC4EC5h const_65 dd 03F03F04h .code mov edx,eax shl eax,2 div const_xx или, если источник в edx, то две операции: Code (Text): lea eax,[edx*4] div const_xx
boozook Таким макаром можно и в одну инструкцию уложиться 61,41,52,65: .data const_61 dd 0,61,122,183... const_41 dd 0,41,82,123... const_52 dd 0,52,104,156... const_65 dd 0,65,130,195... .code lea eax,[eax*4+const_xx] All Кстати началось Hugi Compo 25: http://www.frontiernet.net/~fys/hugi/hcompo.htm Задача оптимизировать решение игры Sudoku. Интересная игра между прочим.
_G3 Ну да, только умножение, в таком случае, будет через своп происходить, т.е. будут выполняться еще инструкции, для обработки исключений
А в чем проблема-то? Берем классику типа Уорнера и читаем про алгоритм скорейшего умножения с помощью сдвигов, сложений и вычитаний. Думаем над ним, вносим творческие дополнения, аккуратно реализуем его (я сам все это уже делал когда-то) - и любуемся на готовые результаты для любых констант в пределах, скажем, 64 битов... Да, это не lea конечно, но зато очень похоже, и главное подойдет для архитектур, у которых нет lea вообще. p.s. кстати, идеи в этом алгоритме те же, что и в этой ветке: взвешивание двоичных деревьев, разложение на множители и т.п...
77: lea ebx,[eax+eax*8] lea ebx,[eax+ebx*2] lea eax,[eax+ebx*4] Nothing >>А в чем проблема-то? Покажи на примере числа 876341
_G3 Программа выдала вот это: (K - это число) (K<<20 - K<<17 - K<<15 - K<<13 - K<<8 + K<<6 - K<<3 - K<<1 - K) Переводить в lea не буду - лень Всего 8 сдвигов и сложений (или вычитаний, что одно и то же по сути). С lea вижу проблемы только в том, что множитель там может быть только 1,2,4,8 - и все, остальные приходится делать сдвигами, правда есть преимущество в том, что можно хранить временные результаты в других регистрах (хотя это нечестно, их тогда сохранять и восстанавливать надо!) Я вот одного не пойму, а зачем кому-то что-то быстро умножать на 876341 на x86 архитектуре? Во-первых число слишком большое и кривое, на практике вряд ли встретится, а во-вторых - штатное умножение mul/imul побыстрее будет на таких числах . Такие упражнения с lea хороши для небольших чисел - там и выигрыщ может быть и изящество проявить можно...
Тоже лень думать, я написал брутфорсер Цифры ещё не кончились? Code (Text): ;============================ ;============================ lea eax,[eax*2+eax] ; 39 lea eax,[eax*4] ; 68 lea ecx,[eax*2+eax] ; lea ecx,[eax*2] ; lea eax,[ecx*4+eax] ; lea eax,[ecx*8+eax] ; ;============================ ;============================ lea ecx,[eax*4+eax] ; 41 lea ecx,[eax*2] ; 70 lea eax,[ecx*8+eax] lea eax,[ecx*8+eax] ; ;============================ lea eax,[eax*4+ecx] ; lea ecx,[eax*2+eax] ; 53 ;============================ lea eax,[ecx*8+eax] ; lea ecx,[eax*8+eax] ; 83 lea eax,[eax*2+ecx] ; lea eax,[eax*2+ecx] ; ;============================ lea eax,[ecx*8+eax] ; lea eax,[eax*2] ; 54 ;============================ lea eax,[eax*2+eax] ; lea eax,[eax*4+eax] ; 85 lea eax,[eax*8+eax] ; lea ecx,[eax*2] ; ;============================ lea eax,[ecx*8+eax] ; lea eax,[eax*8] ; 56 ;============================ lea ecx,[eax*2+eax] ; lea ecx,[eax*4+eax] ; 87 lea eax,[ecx*2+eax] ; lea eax,[ecx*8+eax] ; ;============================ lea eax,[eax*2+ecx] ; lea eax,[eax*2+eax] ; ;============================ lea ecx,[eax*8+eax] ; 57 lea ecx,[eax*4+eax] ; 89 lea eax,[ecx*2+eax] ; lea eax,[ecx*4+eax] ; ;============================ lea eax,[eax*4+ecx] lea ecx,[eax*4+eax] ; 61 ;============================ lea eax,[eax*2+ecx] ; lea eax,[eax*2] ; 90 lea eax,[eax*8+ecx] ; lea eax,[eax*4+eax] ; ;============================ lea eax,[eax*8+eax] ; lea ecx,[eax*2+eax] ; 67 ;============================ lea eax,[eax*8] ; lea eax,[eax*8+ecx] ; ;============================ Code (Text): ;============================ lea eax,[eax*4] ; 52 lea ecx,[eax*2+eax] ; lea eax,[ecx*4+eax] ; ;============================ Осталось 58 71 78 79 и 876341
Code (Text): ;============================ ;============================ lea eax,[eax*2] ; 58 lea eax,[eax*2] ; 78 lea ecx,[eax*2+eax] ; lea eax,[eax*2+eax] ; lea eax,[eax*4+eax] ; lea ecx,[eax*2+eax] ; lea eax,[ecx*8+eax] ; lea eax,[ecx*4+eax] ; ;============================ ;============================ lea ecx,[eax*2] ; 71 lea ecx,[eax*2+eax] ; 79 shl ecx,5 ; lea eax,[eax*2] ; sub ecx,eax ; lea eax,[eax*8+ecx] ; lea eax,[eax*8+ecx] ; lea eax,[eax*4+ecx] ; ;============================ ;============================
> "Тоже лень думать" Эт-точно, не в бровь, а в глаз С одной стороны задачка занудно-тривиальная - можно и без брутфорсера за пять минут элементарную табличку в Excel на все 2-3ходовые варианты составить А с другой стороны не понятно, что дает минимизация числа инструкций. Нужен минимум команд - используй imul, нужен максимум скорости - тогда придется учитывать латентности и возможности распараллеливания, а не тупо считать число команд Вот для справочки - латентности операций lea и imul: Code (Text): Проц lea r32,[r+r*i] imul r32,imm8 ------ --------------- ------------- AMD K7 2 5 AMD 64 2 3 P6 1 4 P4 4 14 P4E 1-2(?) 10 Выводы: 1) Три зависимых LEA, удовлетворяющие условию "минимума числа команд" однозначно проигрывают imul на Атлонах, в лучшем случае могут дать 1 тик выигрыша на P6 и 2 тика на P4 (в лучшем, т.к. они нагружают декодер и исполнительные блоки и => придерживают исполнение следующих независимых команд). Пожалуй только для "загадочно-полутормозного" P4E (model 3, Prescott & Co) может быть заметный выигрыш. 2) В P6 lea и shl однотиковые и не параллелятся (идут через один порт p0), а вот на атлонах и P4 можно несколько уменьшить латентность за счет распараллеливания при использовании независимых операций. Поэтому не все варианты с одинаковым числом команд равнозначны. Например, из приведенных 3-ходовых вариантов для множителя 23 самым быстрым является первый вариант _G3, он же "классический" рекомедуемый AMD для K7. Также и для других 3-ходовых существуют более быстрые варианты с одной независимой операцией (элементарно находятся по таблице): Code (Text): 39=3+9*4 ;все 3,5,9 реализуются через lea 52=16+9*4=32+5*4 ;все 16,32,64 - через shl 56=16+5*8=32+3*8 61=64-3 67=64+3 68=32+9*4 70=64+3*2 77=5+9*8 Ну и при неминимальном числе команд, можно не проиграть на P6 и выиграть на атлонах и P4. Например "очевидное решение" из двух зависимых lea для множителя 33 можно заменить на столь же очевидное решение в 3 хода Code (Text): mov ecx,eax shl eax,5 add eax,ecx которое может дать те же 2 тика на P6 (если mov проскочит через рорт p1), для атлона даст экономию в 2 тика, а для P4 в 3 тика
