Sun, 11 Jan 2015 19:22:03 -0000

Related articles |
---|

Automatic algorithm optimisation via fast matrix exponentiation willvarfar@gmail.com (2015-01-11) |

Re: Automatic algorithm optimisation via fast matrix exponentiation nuno.lopes@ist.utl.pt (Nuno Lopes) (2015-01-11) |

From: | "Nuno Lopes" <nuno.lopes@ist.utl.pt> |

Newsgroups: | comp.compilers |

Date: | Sun, 11 Jan 2015 19:22:03 -0000 |

Organization: | Compilers Central |

References: | 15-01-010 |

Keywords: | optimize |

Posted-Date: | 11 Jan 2015 21:35:34 EST |

*> Lovely article:*

*>*

*> http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation*

*>*

*> Do any compilers do this kind of thing?*

Partially, yes.

For example, LLVM has a quadratic recurrence solver (named SCEV --

scalar evolution). For this purpose, matrix exponentiation is pretty

much equivalent to recurrence solving. So, if LLVM manages to rewrite

an induction variable as a recurrence, and if it manages to compute

its closed-form, then LLVM may replace a loop with straight-line code.

I believe GCC and MSVC can do similar things, since it's a somehow required

piece of technology for automatic vectorization, which all compilers can do

to some extent these days..

Nuno

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.