14 Mar 1997 00:30:31 -0500

Related articles |
---|

Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-14) |

Re: Multiplication by a constant - how? rweaver@ix.netcom.com (1997-03-16) |

Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16) |

Re: Multiplication by a constant - how? d.sand@ix.netcom.com (Duane Sand) (1997-03-16) |

Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16) |

Re: Multiplication by a constant - how? dlmoore@ix.netcom.com (David L Moore) (1997-03-16) |

Re: Multiplication by a constant - how? preston@tera.com (1997-03-21) |

[4 later articles] |

From: | Sergey Solyanik <Sergey.Solyanik@bentley.com> |

Newsgroups: | comp.compilers |

Date: | 14 Mar 1997 00:30:31 -0500 |

Organization: | BSI |

Keywords: | arithmetic, optimize |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.