Multiplication by a constant - how?

MicroSoft Visual C seems to be capable to generate multiplication by a
constant using sequence of shifts and adds no longer than 6 operations
(total), using at most two registers. The optimization is used always
and does not seem to be confined to any special cases. Does anybody
know what algorithm is used and where can I look for information?


Examples:


a = a * 127; // 1111111 bin


=> mov eax, dword ptr [a]
      mov ecx, eax
      shl eax, 7
      sub eax, ecx


a = a * 11101; // 10101101011101 bin


=> mov eax, dword ptr [a]
      mov ecx, eax
      lea eax, [eax+eax*8]
      lea eax, [ecx+eax*4]
      lea eax, [eax+eax*4]
      lea eax, [eax+eax*4]
      lea eax, [eax+eax*2]
      lea eax, [ecx+eax*4]


a = a * 11229; // 10101111011101 bin


=> mov eax, dword ptr [a]
      mov ecx, eax
      lea eax, [eax+eax*2]
      lea eax, [ecx+eax*4]
      lea eax, [eax+eax*8]
      shl eax, 05
      sub eax, ecx
      lea eax, [eax+eax*2]


...etc


Thanks and regards --


Sergey Solyanik
Bentley Systems, Inc


Sergey.Solyanik@bentley.com
[In the computer theory biz this topic is known as addition chains. I know
lots of heuristics but no general optimal scheme. -John]


--

Return to the comp.compilers page.
Search the comp.compilers archives again.