[llvm-dev] [RFC] Add IR level interprocedural outliner for code size.

[Andrey Bokhanko via llvm-dev]

Hi Quentin,

I really don't have a dog in this race, but... we can theoritize on
strengths and weaknesses of different approaches ad infinitum -- or just
accept that "the proof is in the pudding", or so they say.

And the proof is here! -- look at the numbers.

If anything, I believe it makes sense to at least accept Riddle's phase
to the trunk and let two approaches evolve in parallel. It probably silly
to have both enabled at the same time, so one that currently provides a
greater benefit should work on -Os/-Oz. With time, evolution will decide
which one should survive -- as it always does.

Yours,
Andrey
===
Compiler Architect
NXP

On Monday, July 24, 2017, Quentin Colombet via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hi River,
>
> On Jul 24, 2017, at 11:55 AM, River Riddle via llvm-dev <
> llvm-dev at lists.llvm.org
> <javascript:_e(%7B%7D,'cvml','llvm-dev at lists.llvm.org');>> wrote:
>
> Hi Jessica,
>  The comparison to the inliner is an interesting one but we think it's
> important to note the difference in the use of heuristics. The inliner is
> juggling many different tasks at the same time, execution speed, code size,
> etc. which can cause the parameters to be very sensitive depending on the
> benchmark/platform/etc. The outliners heuristics are focused solely on the
> potential code size savings from outlining, and is thus only sensitive to
> the current platform. This only creates a problem when we are over
> estimating the potential cost of a set of instructions for a particular
> target. The cost model parameters are only minimums: instruction sequence
> length, estimated benefit, occurrence amount. The heuristics themselves are
> conservative and based upon all of the target information available at the
> IR level, the parameters are just setting a lower bound to weed out any
> outliers. You are correct in that being at the machine level, before or
> after RA, will give the most accurate heuristics but we feel there's an
> advantage to being at the IR level. At the IR level we can do so many more
> things that are either too difficult/complex for the machine level(e.g
> parameterization/outputs/etc). Not only can we do these things but they are
> available on all targets immediately, without the need for target hooks.
> The caution on the use of heuristics is understandable, but there comes a
> point when trade offs need to be made. We made the trade off for a loss in
> exact cost modeling to gain flexibility, coverage, and potential for
> further features. This trade off is the same made for quite a few IR level
> optimizations, including inlining. As for the worry about code size
> regressions, so far the results seem to support our hypothesis.
>
>
> Would still be interesting to see how well this could perform on some
> exact model (i.e., at the Machine level), IMO. Target hooks are cheap and
> choosing an implementation because it is simpler might not be the right
> long term solution.
> At the very least, to know what trade-off we are making, having prototypes
> with the different approaches sounds sensible.
> In particular, all the heuristics about cost for parameter passing
> (haven’t checked how you did it) sounds already complex enough and would
> require target hooks. Therefore, I am not seeing a clear win with an IR
> approach here.
>
> Finally, having heuristics solely focused on code size do not seem
> realistic. Indeed, I am guessing you have some thresholds to avoid
> outlining some piece of code too small that would end up adding a whole lot
> of indirections and I don’t like magic numbers in general :).
>
> To summarize, I wanted to point out that an IR approach is not as a clear
> win as you describe and would thus deserve more discussion.
>
> Cheers,
> -Quentin
>
>  Thanks,
> River Riddle
>
> On Mon, Jul 24, 2017 at 11:12 AM, Jessica Paquette <jpaquette at apple.com
> <javascript:_e(%7B%7D,'cvml','jpaquette at apple.com');>> wrote:
>
>>
>> Hi River,
>>
>> I’m working on the MachineOutliner pass at the MIR level. Working at the
>> IR level sounds interesting! It also seems like our algorithms are similar.
>> I was thinking of taking the suffix array route with the MachineOutliner in
>> the future.
>>
>> Anyway, I’d like to ask about this:
>>
>> On Jul 20, 2017, at 3:47 PM, River Riddle via llvm-dev <
>> llvm-dev at lists.llvm.org
>> <javascript:_e(%7B%7D,'cvml','llvm-dev at lists.llvm.org');>> wrote:
>>
>> The downside to having this type of transformation be at the IR level is
>> it means there will be less accuracy in the cost model -  we can somewhat
>> accurately model the cost per instruction but we can’t get information on
>> how a window of instructions may lower. This can cause regressions
>> depending on the platform/codebase, therefore to help alleviate this there
>> are several tunable parameters for the cost model.
>>
>>
>> The inliner is threshold-based and it can be rather unpredictable how it
>> will impact the code size of a program. Do you have any idea as to how
>> heuristics/thresholds/parameters could be tuned to prevent this? In my
>> experience, making good code size decisions with these sorts of passes
>> requires a lot of knowledge about what instructions you’re dealing with
>> exactly. I’ve seen the inliner cause some pretty serious code size
>> regressions in projects due to small changes to the cost model/parameters
>> which cause improvements in other projects. I’m a little worried that an
>> IR-level outliner for code size would be doomed to a similar fate.
>>
>> Perhaps it would be interesting to run this sort of pass pre-register
>> allocation? This would help pull you away from having to use heuristics,
>> but give you some more opportunities for finding repeated instruction
>> sequences. I’ve thought of doing something like this in the future with the
>> MachineOutliner and seeing how it goes.
>>
>> - Jessica
>>
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> <javascript:_e(%7B%7D,'cvml','llvm-dev at lists.llvm.org');>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170725/d565a5e2/attachment-0001.html>