[LLVMdev] [cfe-dev] costing optimisations

[David Tweed]

Hi,

Here's a personal perspective on the issue:

Firstly I don't think TeX does pre-estimation of work, it's just the
standard stepwise "refinement stuff". However, the idea itself isn't
necessarily a bad one.

In the academic community there's a set of people (John Cavazos, Lous-Noel
Pouchet, others I've forgotten) doing work on estimating which sets of
optimizations are most likely to produce a good speed up using estimation
functions. (Note they're concerned primarily with outputted code speed,
followed by the fact there are just too many combinations of optimizations
to evaluate directly.) There's a couple of important differences: they're
using estimation functions found by machine learning on "scientific-ish"
code, which probably has more uniformity than completely unrestricted
programs. It's also based on the idea that there's just not the manpower
available to understand the complicated interactions between components on
the plethora of modern machines. From reading papers (and I've not yet
implemented enough of this stuff to test how well it really works) it looks
like a reasonable argument.

However, it's also potentially introducing highly
non-predictable/principle-of-least-surprise behaviour into the compiler,
particularly since llvm can be used as a JIT. So I suspect it wouldn't be
something most people would want for mainstream clang/llvm, but if might be
interesting if someone were to implement some passes like this (probably
out-of-tree) and see if it proves beneficial.

Of course Sean's point that superlinear behaviour ought to be reported as
it's probably a bug is very true,

Regards,
Dave 



-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Sean Silva
Sent: 23 November 2012 06:47
To: john skaller
Cc: Clang; llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] [cfe-dev] costing optimisations

Adding LLVMdev, since this is intimately related to the optimization passes.

> I think this is roughly because some function level optimisations are
> worse than O(N) in the number of instructions.

Please profile this and mail llvmdev regarding passes with
significantly superlinear behavior (e.g. O(n^2)). My understanding is
that these kinds of algorithmic problems are generally considered bugs
in the optimizer and will be fixed.

> Roughly, a pass would calculate the cost of running on some
> unit (translation unit, function), and a "goodness" estimating
> how much improvement might be expected. The optimiser
> then tries to simultaneously maximise goodness and minimise
> cost by selecting some sequence of passes.

I'm doubt there is a way to compute expected benefit that is
significantly cheaper than actually performing the optimization
itself. You also have to consider that passes interact with each other
in complicated and "poorly understood" ways so it's hard to
extrapolate one pass's estimated benefit to overall code improvement
in the end. I say "poorly understood" because as far as I know there
is no formal or scientific underpinning to the choice and ordering of
passes which are run as the "standard compile opts" (e.g. -O1, -O2,
-O3, etc.) besides very high-level, extremely rough heuristics.

> Another way to do this would be to calculate a time limit on
> a pass and abort it if it exceeded the limit.

No way. This would make the optimizations nondeterministic.

-- Sean Silva

On Thu, Nov 22, 2012 at 11:50 PM, john skaller
<skaller at users.sourceforge.net> wrote:
> Hi, I've been having some of the usual problems with C compiler
optimisations:
> they work fine on small functions but drop dead on big ones.
>
> I think this is roughly because some function level optimisations are
> worse than O(N) in the number of instructions.
>
> Changing the command line -O level is not a solution.
> The optimiser should adapt to ensure reasonable compile times.
>
> Has anyone thought about costing optimisation passes and using
> a linear optimisation formula to select when to apply them?
>
> TeX does something like this to calculate the best places to put
> line breaks when typesetting.
>
> Roughly, a pass would calculate the cost of running on some
> unit (translation unit, function), and a "goodness" estimating
> how much improvement might be expected. The optimiser
> then tries to simultaneously maximise goodness and minimise
> cost by selecting some sequence of passes.
>
> Another way to do this would be to calculate a time limit on
> a pass and abort it if it exceeded the limit.
>
> Some optimisations could be coded to do this kind of thing
> internally, i.e. partition a function and optimise the pieces,
> rather than the whole function, to avoid time overruns.
>
> FYI: I have a product which generates big functions.
> It does this for two reasons: performance is one,
> and lack of suitable semantics in C, roughly this
> is coroutine calls (exchange of control), and probably
> continuation passing. LLVM also lacks these fundamentals
> and is too high level to implement them, so the implementation
> is done natively but the result is big functions.
>
> --
> john skaller
> skaller at users.sourceforge.net
> http://felix-lang.org
>
>
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev