[LLVMdev] [cfe-dev] costing optimisations

[john skaller]

On 23/11/2012, at 5:46 PM, Sean Silva wrote:

> 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.

I'll try, but at the moment I'm having trouble building Clang/LLVM.
Bug report in Bugzilla. 10 hours build time followed by failure
on the Release version isn't much fun (and also uses a lot of
power -- everything is solar/wind powered). The Debug+Asserts
version did build, that's what is taking so long. I thought perhaps
the assertions or lack of optimisation might slow things down
so I tried to build a release version.

I think I built Debug+Asserts using clang 3.1. However once installed,
the Release version is being built by 3.3svn/Debug+Asserts.


> 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 agree. It's also hard to tell how good linear passes are compared
to recursive optimisations. However one has to have some way
of choosing which optimisation passes to run, when to run them,
and how many times, so some judgement has to be made anyhow.
Making a numerical judgment and using formula to choose by
weighting can't be worse (once suitable numbers are found).

>> 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.


Not if you set the time to infinity.

At present I have a test suite which imposes a timeout on each test.
This is in case a bug make the test run forever. But it also kills
the test if the compile runs too long.

So I have non-deterministic behaviour already. Sometimes a test
runs and sometime not (because part of the compilation is cached,
it may succeed on a second attempt).

--
john skaller
skaller at users.sourceforge.net
http://felix-lang.org