llvm dev - Mar 2019 - Proposal for O1/Og Optimization and Code Generation Pipeline

Hi All,

I’ve been thinking about both O1 and Og optimization levels and have a
proposal for an improved O1 that I think overlaps in functionality
with our desires for Og. The design goal is to rewrite the O1
optimization and code generation pipeline to include the set of
optimizations that minimizes build and test time while retaining our
ability to debug.

This isn’t to minimize efforts around optimized debugging or negate O0
builds, but rather to provide a compromise mode that encompasses some
of the benefits of both. In effect to create a “build mode for
everyday development”.

This proposal is a first approximation guess on direction. I’ll be
exploring different options and combinations, but I think this is a
good place to start for discussion. Unless there are serious
objections to the general direction I’d like to get started so we can
explore and look at the code as it comes through review.


Optimization and Code Generation Pipeline

The optimization passes chosen fall into a few main categories,
redundancy elimination and basic optimization/abstraction elimination.
The idea is that these are going to be the optimizations that a
programmer would expect to happen without affecting debugging. This
means not eliminating redundant calls or non-redundant loads as those
could fail in different ways and locations while executing.  These
optimizations will also reduce the overall amount of code going to the
code generator helping both linker input size and code generation
speed.

Dead code elimination

 - Dead code elimination (ADCE, BDCE)
 - Dead store elimination
 - Parts of CFG Simplification
 - Removing branches and dead code paths and not including commoning
and speculation

Basic Scalar Optimizations

 - Constant propagation including SCCP and IPCP
 - Constant merging
 - Instruction Combining
 - Inlining: always_inline and normal inlining passes
 - Memory to register promotion
 - CSE of “unobservable” operations
 - Reassociation of expressions
 - Global optimizations - try to fold globals to constants

Loop Optimizations

Loop optimizations have some problems around debuggability and
observability, but a suggested set of passes would include
optimizations that remove abstractions and not ones that necessarily
optimize for performance.

 - Induction Variable Simplification
 - LICM but not promotion
 - Trivial Unswitching
 - Loop rotation
 - Full loop unrolling
 - Loop deletion

Pass Structure

Overall pass ordering will look similar to the existing pass layout in
llvm with passes added or subtracted for O1 rather than a new pass
ordering. The motivation here is to make the overall proposal easier
to understand initially upstream while also maintaining existing pass
pipeline synergies between passes.

Instruction selection

We will use the fast instruction selector (where it exists) for three reasons:
 - Significantly faster code generation than llvm’s dag based
instruction selection
 - Better debugability than selection dag - fewer instructions moved around
 - Fast instruction selection has been optimized somewhat and
shouldn’t be an outrageous penalty on most architectures

Register allocation

The fast register allocator should be used for compilation speed.

Thoughts?

Thanks!

-eric

> On Mar 28, 2019, at 10:09 PM, Eric Christopher via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Register allocation
> 
> The fast register allocator should be used for compilation speed.
I don’t think this is reasonable for anything claiming to have any level of
optimization enabled. I would assume basic would be used for this

-Matt

On 3/28/19 9:09 PM, Eric Christopher via llvm-dev wrote:
> Hi All,
>
> I’ve been thinking about both O1 and Og optimization levels and have a
> proposal for an improved O1 that I think overlaps in functionality
> with our desires for Og. The design goal is to rewrite the O1
> optimization and code generation pipeline to include the set of
> optimizations that minimizes build and test time while retaining our
> ability to debug.

+1

The fact that our O1 and O2 pipelines are so similar has generally
suggested to me that our O1 pipeline probably does too much.

>
> This isn’t to minimize efforts around optimized debugging or negate O0
> builds, but rather to provide a compromise mode that encompasses some
> of the benefits of both. In effect to create a “build mode for
> everyday development”.
>
> This proposal is a first approximation guess on direction. I’ll be
> exploring different options and combinations, but I think this is a
> good place to start for discussion. Unless there are serious
> objections to the general direction I’d like to get started so we can
> explore and look at the code as it comes through review.
>
>
> Optimization and Code Generation Pipeline
>
> The optimization passes chosen fall into a few main categories,
> redundancy elimination and basic optimization/abstraction elimination.
> The idea is that these are going to be the optimizations that a
> programmer would expect to happen without affecting debugging. This
> means not eliminating redundant calls or non-redundant loads as those
> could fail in different ways and locations while executing.  These
> optimizations will also reduce the overall amount of code going to the
> code generator helping both linker input size and code generation
> speed.
>
> Dead code elimination
>
>  - Dead code elimination (ADCE, BDCE)

Regarding BDCE: The trivialized values might indeed be irrelevant to
later calculations, but might harm the debugging experience? If BDCE
only was applied at O2 and higher, that's likely not a huge loss.
Regular DCE (meaning without the bit-tracking parts) is probably fine
for O1.

>  - Dead store elimination
>  - Parts of CFG Simplification
>  - Removing branches and dead code paths and not including commoning
> and speculation
>
> Basic Scalar Optimizations
>
>  - Constant propagation including SCCP and IPCP
>  - Constant merging
>  - Instruction Combining
>  - Inlining: always_inline and normal inlining passes
>  - Memory to register promotion
>  - CSE of “unobservable” operations
>  - Reassociation of expressions
>  - Global optimizations - try to fold globals to constants
>
> Loop Optimizations
>
> Loop optimizations have some problems around debuggability and
> observability, but a suggested set of passes would include
> optimizations that remove abstractions and not ones that necessarily
> optimize for performance.
>
>  - Induction Variable Simplification
>  - LICM but not promotion
>  - Trivial Unswitching
>  - Loop rotation
>  - Full loop unrolling
>  - Loop deletion
>
> Pass Structure
>
> Overall pass ordering will look similar to the existing pass layout in
> llvm with passes added or subtracted for O1 rather than a new pass
> ordering. The motivation here is to make the overall proposal easier
> to understand initially upstream while also maintaining existing pass
> pipeline synergies between passes.
>
> Instruction selection
>
> We will use the fast instruction selector (where it exists) for three
reasons:
>  - Significantly faster code generation than llvm’s dag based
> instruction selection
>  - Better debugability than selection dag - fewer instructions moved around
>  - Fast instruction selection has been optimized somewhat and
> shouldn’t be an outrageous penalty on most architectures
>
> Register allocation
>
> The fast register allocator should be used for compilation speed.

I'm not sure about this - we should understand the performance impact -
it might be severe.

Thanks again,

Hal

>
> Thoughts?
>
> Thanks!
>
> -eric
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

> >
> >  - Dead code elimination (ADCE, BDCE)
>
>
> Regarding BDCE: The trivialized values might indeed be irrelevant to
> later calculations, but might harm the debugging experience? If BDCE
> only was applied at O2 and higher, that's likely not a huge loss.
> Regular DCE (meaning without the bit-tracking parts) is probably fine
> for O1.
>
>
>
Probably not. I'll see what the impact is for sure.

> > Register allocation
> >
> > The fast register allocator should be used for compilation speed.
>
>
> I'm not sure about this - we should understand the performance impact -
> it might be severe.
>
>
Totally agree. I think evaluating the tradeoffs is going to be key. I also
have really no strong opinions and am happy to go where the data takes us.

Thanks :)

-eric
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190328/b1aeeeb7/attachment.html>

Hi Eric,

On Thu, Mar 28, 2019 at 7:09 PM Eric Christopher via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi All,
>
> I’ve been thinking about both O1 and Og optimization levels and have a
> proposal for an improved O1 that I think overlaps in functionality
> with our desires for Og. The design goal is to rewrite the O1
> optimization and code generation pipeline to include the set of
> optimizations that minimizes build and test time while retaining our
> ability to debug.
>
That would be nice: how do you distinguish O1 and Og with this view? (which
from your list would / wouldn't be included in Og?)

>
> This isn’t to minimize efforts around optimized debugging or negate O0
> builds, but rather to provide a compromise mode that encompasses some
> of the benefits of both. In effect to create a “build mode for
> everyday development”.
>
> This proposal is a first approximation guess on direction. I’ll be
> exploring different options and combinations, but I think this is a
> good place to start for discussion. Unless there are serious
> objections to the general direction I’d like to get started so we can
> explore and look at the code as it comes through review.
>
>
> Optimization and Code Generation Pipeline
>
> The optimization passes chosen fall into a few main categories,
> redundancy elimination and basic optimization/abstraction elimination.
> The idea is that these are going to be the optimizations that a
> programmer would expect to happen without affecting debugging. This
> means not eliminating redundant calls or non-redundant loads as those
> could fail in different ways and locations while executing.  These
> optimizations will also reduce the overall amount of code going to the
> code generator helping both linker input size and code generation
> speed.
>
> Dead code elimination
>
>  - Dead code elimination (ADCE, BDCE)
>  - Dead store elimination
>  - Parts of CFG Simplification
>  - Removing branches and dead code paths and not including commoning
> and speculation
>
> Basic Scalar Optimizations
>
>  - Constant propagation including SCCP and IPCP
>  - Constant merging
>  - Instruction Combining
>  - Inlining: always_inline and normal inlining passes
>  - Memory to register promotion
>  - CSE of “unobservable” operations
>  - Reassociation of expressions
>  - Global optimizations - try to fold globals to constants
>
> Loop Optimizations
>
> Loop optimizations have some problems around debuggability and
> observability, but a suggested set of passes would include
> optimizations that remove abstractions and not ones that necessarily
> optimize for performance.
>
>  - Induction Variable Simplification
>  - LICM but not promotion
>  - Trivial Unswitching
>  - Loop rotation
>  - Full loop unrolling
>  - Loop deletion
>
That is already a pretty good list. I would find interesting if we know the
opposite list: the passes that we should not include for speed and
debugaibility? Vectorizer? Unrolling? Jump Threading?
Also couldn't constant propagation and reassociation which are in your list
hurt debugability?

Thanks!

-- 
Mehdi


>
> Pass Structure
>
> Overall pass ordering will look similar to the existing pass layout in
> llvm with passes added or subtracted for O1 rather than a new pass
> ordering. The motivation here is to make the overall proposal easier
> to understand initially upstream while also maintaining existing pass
> pipeline synergies between passes.
>
> Instruction selection
>
> We will use the fast instruction selector (where it exists) for three
> reasons:
>  - Significantly faster code generation than llvm’s dag based
> instruction selection
>  - Better debugability than selection dag - fewer instructions moved around
>  - Fast instruction selection has been optimized somewhat and
> shouldn’t be an outrageous penalty on most architectures
>
> Register allocation
>
> The fast register allocator should be used for compilation speed.
>
> Thoughts?
>
> Thanks!
>
> -eric
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://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/20190329/65522846/attachment.html>

Thanks for posting this.  I'm absolutely of the opinion that current -O1 is
almost a "worst of all worlds" optimization level, where the
performance of
the generated code isn't good enough to be particularly useful (for our
users at least) but the debug experience is already getting close to being
as bad as -O2/3, so I'm personally very happy with your direction of
redefining -O1 (especially as that could then open up the way to future
enhancements like using PGO data to let us compile everything at -O1 for
the build time performance win, except for the critical hot functions that
get the full -O2/3 pipeline for the run time performance win).

How will this optimization level interact with LTO (specifically ThinLTO)?
Would -O1 -flto=thin to run through a different, faster LTO pipeline or are
we expecting that any everyday development build configuration won't
include LTO?

I'm a little bit more on the fence with what this would mean for -Og, as
I'd really like to try and come to some sort of community consensus on
exactly what -Og should mean and what its aims should be.  If you happen to
be at EuroLLVM this year then that would be absolutely perfect timing as
I'd already submitted a round table topic to try and start just that
process [ http://llvm.org/devmtg/2019-04/#rounds ].  My team's main focus
right now is in trying to fix as many -O2 debug experience issues as
possible, with the hope that we could consider using an -Og mode to mop up
what's left, but we've been surveying our users for a few years now
about
what they'd find useful in such an optimization level.

The general consensus is that performance must not be significantly worse
than -O2.  We've heard a few numbers thrown around like 5-10% runtime
slowdown compared to -O2 being the absolute maximum acceptable level of
intrusion for them to consider using such a mode.  I'm not really sure how
realistic that is and I'm inclined to think that we could probably stretch
that limit a little bit here and there if the debugging experience really
was that much better, but I think it gives a good indication of at least
what our users are looking for.  Essentially -O2 but with as few changes as
we can get away with making to make the debugging experience better.  I
know that this is somewhat woolly, so it might be that your proposed
pipeline is the closest we can get that matches such an aim, but once we've
decided what -Og should mean, I'd like to try and justify any changes with
some real data.  I'm willing for my team to contribute as much data as we
can.  We've also been using dexter [
http://llvm.org/devmtg/2018-04/slides/Bedwell-Measuring_the_User_Debugging_Experience.pdf
]
to target our -O2 debugging improvement work, but hopefully it will be
useful to provide another datapoint for the effects on the debugging
experience of disabling specific passes.

In my mind, -Og probably would incorporate a few things:
* Tweak certain pass behaviors in order to be more favorable towards
debugging [ https://reviews.llvm.org/D59431#1437716 ]
* Enable features favorable to debugging [
http://llvm.org/devmtg/2017-10/#lightning8 ]
* Disable whole passes that are known to fundamentally harm the debugging
experience if there is no other alternative approach (this proposal?)
* Still give a decent debug experience when used in conjunction with LTO.

Thanks again for writing up your proposal.  I'm really happy to see
movement in this area!

-Greg



On Fri, 29 Mar 2019 at 02:09, Eric Christopher via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi All,
>
> I’ve been thinking about both O1 and Og optimization levels and have a
> proposal for an improved O1 that I think overlaps in functionality
> with our desires for Og. The design goal is to rewrite the O1
> optimization and code generation pipeline to include the set of
> optimizations that minimizes build and test time while retaining our
> ability to debug.
>
> This isn’t to minimize efforts around optimized debugging or negate O0
> builds, but rather to provide a compromise mode that encompasses some
> of the benefits of both. In effect to create a “build mode for
> everyday development”.
>
> This proposal is a first approximation guess on direction. I’ll be
> exploring different options and combinations, but I think this is a
> good place to start for discussion. Unless there are serious
> objections to the general direction I’d like to get started so we can
> explore and look at the code as it comes through review.
>
>
> Optimization and Code Generation Pipeline
>
> The optimization passes chosen fall into a few main categories,
> redundancy elimination and basic optimization/abstraction elimination.
> The idea is that these are going to be the optimizations that a
> programmer would expect to happen without affecting debugging. This
> means not eliminating redundant calls or non-redundant loads as those
> could fail in different ways and locations while executing.  These
> optimizations will also reduce the overall amount of code going to the
> code generator helping both linker input size and code generation
> speed.
>
> Dead code elimination
>
>  - Dead code elimination (ADCE, BDCE)
>  - Dead store elimination
>  - Parts of CFG Simplification
>  - Removing branches and dead code paths and not including commoning
> and speculation
>
> Basic Scalar Optimizations
>
>  - Constant propagation including SCCP and IPCP
>  - Constant merging
>  - Instruction Combining
>  - Inlining: always_inline and normal inlining passes
>  - Memory to register promotion
>  - CSE of “unobservable” operations
>  - Reassociation of expressions
>  - Global optimizations - try to fold globals to constants
>
> Loop Optimizations
>
> Loop optimizations have some problems around debuggability and
> observability, but a suggested set of passes would include
> optimizations that remove abstractions and not ones that necessarily
> optimize for performance.
>
>  - Induction Variable Simplification
>  - LICM but not promotion
>  - Trivial Unswitching
>  - Loop rotation
>  - Full loop unrolling
>  - Loop deletion
>
> Pass Structure
>
> Overall pass ordering will look similar to the existing pass layout in
> llvm with passes added or subtracted for O1 rather than a new pass
> ordering. The motivation here is to make the overall proposal easier
> to understand initially upstream while also maintaining existing pass
> pipeline synergies between passes.
>
> Instruction selection
>
> We will use the fast instruction selector (where it exists) for three
> reasons:
>  - Significantly faster code generation than llvm’s dag based
> instruction selection
>  - Better debugability than selection dag - fewer instructions moved around
>  - Fast instruction selection has been optimized somewhat and
> shouldn’t be an outrageous penalty on most architectures
>
> Register allocation
>
> The fast register allocator should be used for compilation speed.
>
> Thoughts?
>
> Thanks!
>
> -eric
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://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/20190329/c895e5ea/attachment.html>

Awesome start.

Back when I did a similar project at HP/NonStop, the class of optimizations we
turned off for our O1 (Og equivalent) tended to be those that reordered code or
otherwise messed with the CFG.  In fact one of our metrics was:

-        The set of breakpoint locations available at Og should be the same as
those available at O0.
This is pretty easy to measure. It can mean either turning off optimizations or
doing a better job with the line table; either way you get the preferred user
experience. Not saying *Clang* has to use the "must be the same"
criterion, but being able to measure this will be extremely helpful.  Comparing
the metric with/without a given pass will give us a good idea of how much that
pass damages the single-stepping experience, and gives us hard data to decide
whether certain passes should stay or go.

I don't remember whether HP/NonStop turned off constant/value propagation,
but I *think* we did, because that can have a really bad effect on availability
of variables.  Now, if we're more industrious about generating DIExpressions
to recover values that get optimized away, that's probably good enough, as
usually you want to be looking at things and not so much modifying things during
a debugging session.

As for Sony's users in particular, working in a real-time environment does
constrain how much performance we can give away for other benefits like good
debugging.  I think we'll have to see how that falls out.

--paulr


From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Greg
Bedwell via llvm-dev
Sent: Friday, March 29, 2019 8:25 AM
To: Eric Christopher
Cc: llvm-dev; Ahmed Bougacha; Petr Hosek
Subject: Re: [llvm-dev] Proposal for O1/Og Optimization and Code Generation
Pipeline

Thanks for posting this.  I'm absolutely of the opinion that current -O1 is
almost a "worst of all worlds" optimization level, where the
performance of the generated code isn't good enough to be particularly
useful (for our users at least) but the debug experience is already getting
close to being as bad as -O2/3, so I'm personally very happy with your
direction of redefining -O1 (especially as that could then open up the way to
future enhancements like using PGO data to let us compile everything at -O1 for
the build time performance win, except for the critical hot functions that get
the full -O2/3 pipeline for the run time performance win).

How will this optimization level interact with LTO (specifically ThinLTO)? 
Would -O1 -flto=thin to run through a different, faster LTO pipeline or are we
expecting that any everyday development build configuration won't include
LTO?

I'm a little bit more on the fence with what this would mean for -Og, as
I'd really like to try and come to some sort of community consensus on
exactly what -Og should mean and what its aims should be.  If you happen to be
at EuroLLVM this year then that would be absolutely perfect timing as I'd
already submitted a round table topic to try and start just that process [
http://llvm.org/devmtg/2019-04/#rounds ].  My team's main focus right now is
in trying to fix as many -O2 debug experience issues as possible, with the hope
that we could consider using an -Og mode to mop up what's left, but
we've been surveying our users for a few years now about what they'd
find useful in such an optimization level.

The general consensus is that performance must not be significantly worse than
-O2.  We've heard a few numbers thrown around like 5-10% runtime slowdown
compared to -O2 being the absolute maximum acceptable level of intrusion for
them to consider using such a mode.  I'm not really sure how realistic that
is and I'm inclined to think that we could probably stretch that limit a
little bit here and there if the debugging experience really was that much
better, but I think it gives a good indication of at least what our users are
looking for.  Essentially -O2 but with as few changes as we can get away with
making to make the debugging experience better.  I know that this is somewhat
woolly, so it might be that your proposed pipeline is the closest we can get
that matches such an aim, but once we've decided what -Og should mean,
I'd like to try and justify any changes with some real data.  I'm
willing for my team to contribute as much data as we can.  We've also been
using dexter [
http://llvm.org/devmtg/2018-04/slides/Bedwell-Measuring_the_User_Debugging_Experience.pdf
] to target our -O2 debugging improvement work, but hopefully it will be useful
to provide another datapoint for the effects on the debugging experience of
disabling specific passes.

In my mind, -Og probably would incorporate a few things:
* Tweak certain pass behaviors in order to be more favorable towards debugging [
https://reviews.llvm.org/D59431#1437716 ]
* Enable features favorable to debugging [
http://llvm.org/devmtg/2017-10/#lightning8 ]
* Disable whole passes that are known to fundamentally harm the debugging
experience if there is no other alternative approach (this proposal?)
* Still give a decent debug experience when used in conjunction with LTO.

Thanks again for writing up your proposal.  I'm really happy to see movement
in this area!

-Greg



On Fri, 29 Mar 2019 at 02:09, Eric Christopher via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi All,

I’ve been thinking about both O1 and Og optimization levels and have a
proposal for an improved O1 that I think overlaps in functionality
with our desires for Og. The design goal is to rewrite the O1
optimization and code generation pipeline to include the set of
optimizations that minimizes build and test time while retaining our
ability to debug.

This isn’t to minimize efforts around optimized debugging or negate O0
builds, but rather to provide a compromise mode that encompasses some
of the benefits of both. In effect to create a “build mode for
everyday development”.

This proposal is a first approximation guess on direction. I’ll be
exploring different options and combinations, but I think this is a
good place to start for discussion. Unless there are serious
objections to the general direction I’d like to get started so we can
explore and look at the code as it comes through review.


Optimization and Code Generation Pipeline

The optimization passes chosen fall into a few main categories,
redundancy elimination and basic optimization/abstraction elimination.
The idea is that these are going to be the optimizations that a
programmer would expect to happen without affecting debugging. This
means not eliminating redundant calls or non-redundant loads as those
could fail in different ways and locations while executing.  These
optimizations will also reduce the overall amount of code going to the
code generator helping both linker input size and code generation
speed.

Dead code elimination

 - Dead code elimination (ADCE, BDCE)
 - Dead store elimination
 - Parts of CFG Simplification
 - Removing branches and dead code paths and not including commoning
and speculation

Basic Scalar Optimizations

 - Constant propagation including SCCP and IPCP
 - Constant merging
 - Instruction Combining
 - Inlining: always_inline and normal inlining passes
 - Memory to register promotion
 - CSE of “unobservable” operations
 - Reassociation of expressions
 - Global optimizations - try to fold globals to constants

Loop Optimizations

Loop optimizations have some problems around debuggability and
observability, but a suggested set of passes would include
optimizations that remove abstractions and not ones that necessarily
optimize for performance.

 - Induction Variable Simplification
 - LICM but not promotion
 - Trivial Unswitching
 - Loop rotation
 - Full loop unrolling
 - Loop deletion

Pass Structure

Overall pass ordering will look similar to the existing pass layout in
llvm with passes added or subtracted for O1 rather than a new pass
ordering. The motivation here is to make the overall proposal easier
to understand initially upstream while also maintaining existing pass
pipeline synergies between passes.

Instruction selection

We will use the fast instruction selector (where it exists) for three reasons:
 - Significantly faster code generation than llvm’s dag based
instruction selection
 - Better debugability than selection dag - fewer instructions moved around
 - Fast instruction selection has been optimized somewhat and
shouldn’t be an outrageous penalty on most architectures

Register allocation

The fast register allocator should be used for compilation speed.

Thoughts?

Thanks!

-eric
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://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/20190329/990e2f62/attachment-0001.html>

Eric Christopher via llvm-dev <llvm-dev at lists.llvm.org> writes:
>  - Inlining: always_inline and normal inlining passes
This gives me some pause.  Many a time I've been in gdb, tried to
execute a method and been told "sorry, can't find this, maybe it was
inlined."

That said, inlining is absolutely crucial for any kind of performance
with C++, so maybe this is an ok tradeoff.  Just wanted to raise the
point.

                      -David

A helpful intermediate for -Og would be to do the inlining anyways, but avoid
actually deleting the now-unused functions.

-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of David
Greene via llvm-dev
Sent: Friday, March 29, 2019 11:41
To: Eric Christopher via llvm-dev <llvm-dev at lists.llvm.org>
Cc: Ahmed Bougacha <abougacha at apple.com>; Petr Hosek <phosek at
google.com>
Subject: Re: [llvm-dev] Proposal for O1/Og Optimization and Code Generation
Pipeline

Eric Christopher via llvm-dev <llvm-dev at lists.llvm.org> writes:
>  - Inlining: always_inline and normal inlining passes
This gives me some pause.  Many a time I've been in gdb, tried to execute a
method and been told "sorry, can't find this, maybe it was
inlined."

That said, inlining is absolutely crucial for any kind of performance with C++,
so maybe this is an ok tradeoff.  Just wanted to raise the point.

                      -David
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi All,

Looks like people are generally supportive of the changes to O1 even
if there's some discussion around O1/Og equivalence that I'll take to
a separate set of replies. Mostly so that I can get O1 changes
separate from "new Og pipeline" changes even if I think that's the
direction we should ultimately go :)

In general though I wanted to give a heads up as to the direction I
was planning on taking things and seeing if anyone necessarily
disagreed with the general idea. I'll plan on working up a set of pass
pipeline patches (after some cleanup) and send out some reviews -
please let me know (privately) if you'd like to be explicitly cc'd on
any review otherwise I'll probably pick a set of people out of the cc
line here.

Thanks a lot for the responses and looking forward to getting some
changes going in this direction!

-eric

On Thu, Mar 28, 2019 at 7:09 PM Eric Christopher <echristo at gmail.com>
wrote:
>
> Hi All,
>
> I’ve been thinking about both O1 and Og optimization levels and have a
> proposal for an improved O1 that I think overlaps in functionality
> with our desires for Og. The design goal is to rewrite the O1
> optimization and code generation pipeline to include the set of
> optimizations that minimizes build and test time while retaining our
> ability to debug.
>
> This isn’t to minimize efforts around optimized debugging or negate O0
> builds, but rather to provide a compromise mode that encompasses some
> of the benefits of both. In effect to create a “build mode for
> everyday development”.
>
> This proposal is a first approximation guess on direction. I’ll be
> exploring different options and combinations, but I think this is a
> good place to start for discussion. Unless there are serious
> objections to the general direction I’d like to get started so we can
> explore and look at the code as it comes through review.
>
>
> Optimization and Code Generation Pipeline
>
> The optimization passes chosen fall into a few main categories,
> redundancy elimination and basic optimization/abstraction elimination.
> The idea is that these are going to be the optimizations that a
> programmer would expect to happen without affecting debugging. This
> means not eliminating redundant calls or non-redundant loads as those
> could fail in different ways and locations while executing.  These
> optimizations will also reduce the overall amount of code going to the
> code generator helping both linker input size and code generation
> speed.
>
> Dead code elimination
>
>  - Dead code elimination (ADCE, BDCE)
>  - Dead store elimination
>  - Parts of CFG Simplification
>  - Removing branches and dead code paths and not including commoning
> and speculation
>
> Basic Scalar Optimizations
>
>  - Constant propagation including SCCP and IPCP
>  - Constant merging
>  - Instruction Combining
>  - Inlining: always_inline and normal inlining passes
>  - Memory to register promotion
>  - CSE of “unobservable” operations
>  - Reassociation of expressions
>  - Global optimizations - try to fold globals to constants
>
> Loop Optimizations
>
> Loop optimizations have some problems around debuggability and
> observability, but a suggested set of passes would include
> optimizations that remove abstractions and not ones that necessarily
> optimize for performance.
>
>  - Induction Variable Simplification
>  - LICM but not promotion
>  - Trivial Unswitching
>  - Loop rotation
>  - Full loop unrolling
>  - Loop deletion
>
> Pass Structure
>
> Overall pass ordering will look similar to the existing pass layout in
> llvm with passes added or subtracted for O1 rather than a new pass
> ordering. The motivation here is to make the overall proposal easier
> to understand initially upstream while also maintaining existing pass
> pipeline synergies between passes.
>
> Instruction selection
>
> We will use the fast instruction selector (where it exists) for three
reasons:
>  - Significantly faster code generation than llvm’s dag based
> instruction selection
>  - Better debugability than selection dag - fewer instructions moved around
>  - Fast instruction selection has been optimized somewhat and
> shouldn’t be an outrageous penalty on most architectures
>
> Register allocation
>
> The fast register allocator should be used for compilation speed.
>
> Thoughts?
>
> Thanks!
>
> -eric

On Mon, Apr 1, 2019 at 6:47 PM Eric Christopher <echristo at gmail.com>
wrote:
> Hi All,
>
> Looks like people are generally supportive of the changes to O1 even
> if there's some discussion around O1/Og equivalence that I'll take
to
> a separate set of replies. Mostly so that I can get O1 changes
> separate from "new Og pipeline" changes even if I think
that's the
> direction we should ultimately go :)
>
One comment I'll make (as I'm somewhat obviously supportive having
discussed this before):

I think the key thing isn't that we *necessarily* leave -Og here. But that
if we have a good -O1 pipeline and use that as a starting point for -Og,
then we can critically evaluate whether there is something that we would
like to do at -Og but would harm the goals of -O1. If so, that becomes a
much more clear and precise basis for diverging. Until then, I suspect it
would still be a better starting point than -O2.

>
> In general though I wanted to give a heads up as to the direction I
> was planning on taking things and seeing if anyone necessarily
> disagreed with the general idea. I'll plan on working up a set of pass
> pipeline patches (after some cleanup) and send out some reviews -
> please let me know (privately) if you'd like to be explicitly cc'd
on
> any review otherwise I'll probably pick a set of people out of the cc
> line here.
>
> Thanks a lot for the responses and looking forward to getting some
> changes going in this direction!
>
> -eric
>
> On Thu, Mar 28, 2019 at 7:09 PM Eric Christopher <echristo at
gmail.com>
> wrote:
> >
> > Hi All,
> >
> > I’ve been thinking about both O1 and Og optimization levels and have a
> > proposal for an improved O1 that I think overlaps in functionality
> > with our desires for Og. The design goal is to rewrite the O1
> > optimization and code generation pipeline to include the set of
> > optimizations that minimizes build and test time while retaining our
> > ability to debug.
> >
> > This isn’t to minimize efforts around optimized debugging or negate O0
> > builds, but rather to provide a compromise mode that encompasses some
> > of the benefits of both. In effect to create a “build mode for
> > everyday development”.
> >
> > This proposal is a first approximation guess on direction. I’ll be
> > exploring different options and combinations, but I think this is a
> > good place to start for discussion. Unless there are serious
> > objections to the general direction I’d like to get started so we can
> > explore and look at the code as it comes through review.
> >
> >
> > Optimization and Code Generation Pipeline
> >
> > The optimization passes chosen fall into a few main categories,
> > redundancy elimination and basic optimization/abstraction elimination.
> > The idea is that these are going to be the optimizations that a
> > programmer would expect to happen without affecting debugging. This
> > means not eliminating redundant calls or non-redundant loads as those
> > could fail in different ways and locations while executing.  These
> > optimizations will also reduce the overall amount of code going to the
> > code generator helping both linker input size and code generation
> > speed.
> >
> > Dead code elimination
> >
> >  - Dead code elimination (ADCE, BDCE)
> >  - Dead store elimination
> >  - Parts of CFG Simplification
> >  - Removing branches and dead code paths and not including commoning
> > and speculation
> >
> > Basic Scalar Optimizations
> >
> >  - Constant propagation including SCCP and IPCP
> >  - Constant merging
> >  - Instruction Combining
> >  - Inlining: always_inline and normal inlining passes
> >  - Memory to register promotion
> >  - CSE of “unobservable” operations
> >  - Reassociation of expressions
> >  - Global optimizations - try to fold globals to constants
> >
> > Loop Optimizations
> >
> > Loop optimizations have some problems around debuggability and
> > observability, but a suggested set of passes would include
> > optimizations that remove abstractions and not ones that necessarily
> > optimize for performance.
> >
> >  - Induction Variable Simplification
> >  - LICM but not promotion
> >  - Trivial Unswitching
> >  - Loop rotation
> >  - Full loop unrolling
> >  - Loop deletion
> >
> > Pass Structure
> >
> > Overall pass ordering will look similar to the existing pass layout in
> > llvm with passes added or subtracted for O1 rather than a new pass
> > ordering. The motivation here is to make the overall proposal easier
> > to understand initially upstream while also maintaining existing pass
> > pipeline synergies between passes.
> >
> > Instruction selection
> >
> > We will use the fast instruction selector (where it exists) for three
> reasons:
> >  - Significantly faster code generation than llvm’s dag based
> > instruction selection
> >  - Better debugability than selection dag - fewer instructions moved
> around
> >  - Fast instruction selection has been optimized somewhat and
> > shouldn’t be an outrageous penalty on most architectures
> >
> > Register allocation
> >
> > The fast register allocator should be used for compilation speed.
> >
> > Thoughts?
> >
> > Thanks!
> >
> > -eric
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190401/4c11a389/attachment-0001.html>

Hi Greg,

Thanks for the detailed response!

On Fri, Mar 29, 2019 at 5:25 AM Greg Bedwell <gregbedwell at gmail.com>
wrote:
>
> Thanks for posting this.  I'm absolutely of the opinion that current
-O1 is almost a "worst of all worlds" optimization level, where the
performance of the generated code isn't good enough to be particularly
useful (for our users at least) but the debug experience is already getting
close to being as bad as -O2/3, so I'm personally very happy with your
direction of redefining -O1 (especially as that could then open up the way to
future enhancements like using PGO data to let us compile everything at -O1 for
the build time performance win, except for the critical hot functions that get
the full -O2/3 pipeline for the run time performance win).
>
Excellent. Thanks.
> How will this optimization level interact with LTO (specifically ThinLTO)? 
Would -O1 -flto=thin to run through a different, faster LTO pipeline or are we
expecting that any everyday development build configuration won't include
LTO?
>
I'll be honest... I hadn't thought about it at all. I'd think that
the
new O1 would supersede any O1 and so thin/normal lto invoked with O1
would give you the new pipeline.
> I'm a little bit more on the fence with what this would mean for -Og,
as I'd really like to try and come to some sort of community consensus on
exactly what -Og should mean and what its aims should be.  If you happen to be
at EuroLLVM this year then that would be absolutely perfect timing as I'd
already submitted a round table topic to try and start just that process [
http://llvm.org/devmtg/2019-04/#rounds ].  My team's main focus right now is
in trying to fix as many -O2 debug experience issues as possible, with the hope
that we could consider using an -Og mode to mop up what's left, but
we've been surveying our users for a few years now about what they'd
find useful in such an optimization level.
>
Sorry, I won't be able to make it. Conveniently I wrote up a nice
email with my general pipeline discussion. I can do more of a write-up
for debugging metrics if that will help? I've got the start of it
anyhow and since a number of people wanted to talk about it I can do
that this week if you think it will be helpful. I'd prefer to keep the
pass discussions on the mailing list as much as possible so that we
can a) keep our discussions focused, and b) include people who can't
necessarily make particular developer meetings.
> The general consensus is that performance must not be significantly worse
than -O2.  We've heard a few numbers thrown around like 5-10% runtime
slowdown compared to -O2 being the absolute maximum acceptable level of
intrusion for them to consider using such a mode.  I'm not really sure how
realistic that is and I'm inclined to think that we could probably stretch
that limit a little bit here and there if the debugging experience really was
that much better, but I think it gives a good indication of at least what our
users are looking for.  Essentially -O2 but with as few changes as we can get
away with making to make the debugging experience better.  I know that this is
somewhat woolly, so it might be that your proposed pipeline is the closest we
can get that matches such an aim, but once we've decided what -Og should
mean, I'd like to try and justify any changes with some real data.  I'm
willing for my team to contribute as much data as we can.  We've also been
using dexter [
http://llvm.org/devmtg/2018-04/slides/Bedwell-Measuring_the_User_Debugging_Experience.pdf
] to target our -O2 debugging improvement work, but hopefully it will be useful
to provide another datapoint for the effects on the debugging experience of
disabling specific passes.
That's a lot of "general consensus" :)

Of course, I'm approaching it from the perspective of "faster than
O0"
rather than "no slower than O2". I'm also not sure whether or not
the
game community is unusual here. I also expect that we can adapt or
change existing passes in order to make them more debugging friendly
over time. For example, the differences I suggested with respect to
cfg cleanup in my proposal. I have a lot of real data I've started
collecting here and I'll work on summarizing some of that in a future
email.

Sounds like a general approach of "let's start carving blocks of
marble and then break out the sanding tools" is welcome though :)
>
> In my mind, -Og probably would incorporate a few things:
> * Tweak certain pass behaviors in order to be more favorable towards
debugging [ https://reviews.llvm.org/D59431#1437716 ]
> * Enable features favorable to debugging [
http://llvm.org/devmtg/2017-10/#lightning8 ]
> * Disable whole passes that are known to fundamentally harm the debugging
experience if there is no other alternative approach (this proposal?)
> * Still give a decent debug experience when used in conjunction with LTO.
>
I don't think we're substantially apart here. I'm very much
personally
not a fan of extending the lifetime of local variables, but I think
it's absolutely a worthwhile discussion to have :)
> Thanks again for writing up your proposal.  I'm really happy to see
movement in this area!
>
Happy to help. This is something I've wanted to work on for years at
this point :)

-eric

> -Greg
>
>
>
> On Fri, 29 Mar 2019 at 02:09, Eric Christopher via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>>
>> Hi All,
>>
>> I’ve been thinking about both O1 and Og optimization levels and have a
>> proposal for an improved O1 that I think overlaps in functionality
>> with our desires for Og. The design goal is to rewrite the O1
>> optimization and code generation pipeline to include the set of
>> optimizations that minimizes build and test time while retaining our
>> ability to debug.
>>
>> This isn’t to minimize efforts around optimized debugging or negate O0
>> builds, but rather to provide a compromise mode that encompasses some
>> of the benefits of both. In effect to create a “build mode for
>> everyday development”.
>>
>> This proposal is a first approximation guess on direction. I’ll be
>> exploring different options and combinations, but I think this is a
>> good place to start for discussion. Unless there are serious
>> objections to the general direction I’d like to get started so we can
>> explore and look at the code as it comes through review.
>>
>>
>> Optimization and Code Generation Pipeline
>>
>> The optimization passes chosen fall into a few main categories,
>> redundancy elimination and basic optimization/abstraction elimination.
>> The idea is that these are going to be the optimizations that a
>> programmer would expect to happen without affecting debugging. This
>> means not eliminating redundant calls or non-redundant loads as those
>> could fail in different ways and locations while executing.  These
>> optimizations will also reduce the overall amount of code going to the
>> code generator helping both linker input size and code generation
>> speed.
>>
>> Dead code elimination
>>
>>  - Dead code elimination (ADCE, BDCE)
>>  - Dead store elimination
>>  - Parts of CFG Simplification
>>  - Removing branches and dead code paths and not including commoning
>> and speculation
>>
>> Basic Scalar Optimizations
>>
>>  - Constant propagation including SCCP and IPCP
>>  - Constant merging
>>  - Instruction Combining
>>  - Inlining: always_inline and normal inlining passes
>>  - Memory to register promotion
>>  - CSE of “unobservable” operations
>>  - Reassociation of expressions
>>  - Global optimizations - try to fold globals to constants
>>
>> Loop Optimizations
>>
>> Loop optimizations have some problems around debuggability and
>> observability, but a suggested set of passes would include
>> optimizations that remove abstractions and not ones that necessarily
>> optimize for performance.
>>
>>  - Induction Variable Simplification
>>  - LICM but not promotion
>>  - Trivial Unswitching
>>  - Loop rotation
>>  - Full loop unrolling
>>  - Loop deletion
>>
>> Pass Structure
>>
>> Overall pass ordering will look similar to the existing pass layout in
>> llvm with passes added or subtracted for O1 rather than a new pass
>> ordering. The motivation here is to make the overall proposal easier
>> to understand initially upstream while also maintaining existing pass
>> pipeline synergies between passes.
>>
>> Instruction selection
>>
>> We will use the fast instruction selector (where it exists) for three
reasons:
>>  - Significantly faster code generation than llvm’s dag based
>> instruction selection
>>  - Better debugability than selection dag - fewer instructions moved
around
>>  - Fast instruction selection has been optimized somewhat and
>> shouldn’t be an outrageous penalty on most architectures
>>
>> Register allocation
>>
>> The fast register allocator should be used for compilation speed.
>>
>> Thoughts?
>>
>> Thanks!
>>
>> -eric
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Fri, Mar 29, 2019 at 12:41 AM Mehdi AMINI <joker.eph at gmail.com>
wrote:
>
> Hi Eric,
>
> On Thu, Mar 28, 2019 at 7:09 PM Eric Christopher via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
>>
>> Hi All,
>>
>> I’ve been thinking about both O1 and Og optimization levels and have a
>> proposal for an improved O1 that I think overlaps in functionality
>> with our desires for Og. The design goal is to rewrite the O1
>> optimization and code generation pipeline to include the set of
>> optimizations that minimizes build and test time while retaining our
>> ability to debug.
>
>
> That would be nice: how do you distinguish O1 and Og with this view? (which
from your list would / wouldn't be included in Og?)
>
As a first pass I'd just make them identical, but there's a lot of
work around statistics collecting (I'll refer you to Greg and Paul's
emails as well) before saying "this is 'done'".
>>
>>
>> This isn’t to minimize efforts around optimized debugging or negate O0
>> builds, but rather to provide a compromise mode that encompasses some
>> of the benefits of both. In effect to create a “build mode for
>> everyday development”.
>>
>> This proposal is a first approximation guess on direction. I’ll be
>> exploring different options and combinations, but I think this is a
>> good place to start for discussion. Unless there are serious
>> objections to the general direction I’d like to get started so we can
>> explore and look at the code as it comes through review.
>>
>>
>> Optimization and Code Generation Pipeline
>>
>> The optimization passes chosen fall into a few main categories,
>> redundancy elimination and basic optimization/abstraction elimination.
>> The idea is that these are going to be the optimizations that a
>> programmer would expect to happen without affecting debugging. This
>> means not eliminating redundant calls or non-redundant loads as those
>> could fail in different ways and locations while executing.  These
>> optimizations will also reduce the overall amount of code going to the
>> code generator helping both linker input size and code generation
>> speed.
>>
>> Dead code elimination
>>
>>  - Dead code elimination (ADCE, BDCE)
>>  - Dead store elimination
>>  - Parts of CFG Simplification
>>  - Removing branches and dead code paths and not including commoning
>> and speculation
>>
>> Basic Scalar Optimizations
>>
>>  - Constant propagation including SCCP and IPCP
>>  - Constant merging
>>  - Instruction Combining
>>  - Inlining: always_inline and normal inlining passes
>>  - Memory to register promotion
>>  - CSE of “unobservable” operations
>>  - Reassociation of expressions
>>  - Global optimizations - try to fold globals to constants
>>
>> Loop Optimizations
>>
>> Loop optimizations have some problems around debuggability and
>> observability, but a suggested set of passes would include
>> optimizations that remove abstractions and not ones that necessarily
>> optimize for performance.
>>
>>  - Induction Variable Simplification
>>  - LICM but not promotion
>>  - Trivial Unswitching
>>  - Loop rotation
>>  - Full loop unrolling
>>  - Loop deletion
>
>
> That is already a pretty good list. I would find interesting if we know the
opposite list: the passes that we should not include for speed and
debugaibility? Vectorizer? Unrolling? Jump Threading?
Jump threading for sure :)

Vectorization and the passes to get us there as well as unrolling are
likely to hurt debugging by changing induction variables and overall
stepping behavior. It's -sometimes- possible to recover, but it's
pretty difficult. Things like GVN and aggressive CSE/commoning can
really hurt in that you don't know how you got into a section of code
and from where.
> Also couldn't constant propagation and reassociation which are in your
list hurt debugability?
>
The former can affect which variables exist, and there's a little bit
of conversation in Paul's email around how you measure or deal with
it. Reassociation can affect how things move around a bit, but IMO
it's not too terrible. Measuring will help of course :)

Thanks!

-eric

> Thanks!
>
> --
> Mehdi
>
>
>>
>>
>> Pass Structure
>>
>> Overall pass ordering will look similar to the existing pass layout in
>> llvm with passes added or subtracted for O1 rather than a new pass
>> ordering. The motivation here is to make the overall proposal easier
>> to understand initially upstream while also maintaining existing pass
>> pipeline synergies between passes.
>>
>> Instruction selection
>>
>> We will use the fast instruction selector (where it exists) for three
reasons:
>>  - Significantly faster code generation than llvm’s dag based
>> instruction selection
>>  - Better debugability than selection dag - fewer instructions moved
around
>>  - Fast instruction selection has been optimized somewhat and
>> shouldn’t be an outrageous penalty on most architectures
>>
>> Register allocation
>>
>> The fast register allocator should be used for compilation speed.
>>
>> Thoughts?
>>
>> Thanks!
>>
>> -eric
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev