OptBisect implementation for new pass manager

Greetings!

As the generic Pass Instrumentation framework for new pass manager is finally *in*,
I'm glad to start the discussion on implementation of -opt-bisect through that framework.

As it has already been discovered while porting other features (namely, -time-passes)
blindly copying the currently existing legacy implementation is most likely not a perfect
way forward. Now is a chance to take a fresh look at the overall approach and perhaps
do better, without the restrictions that legacy pass manager framework imposed on
the implementation.

Kind of a summary of what we have now:
- There is a single OptBisect object, requested through LLVMContext
(managed as ManagedStatic).

- OptBisect is defined in lib/IR, but does use analyses,
which is a known layering issue

- Pass hierarchy provides skipModule etc helper functions

- Individual passes opt-in to OptBisect activities by manually calling skip* helper functions
whenever appropriate

With current state of new-pm PassInstrumentation potential OptBisect implementation
will have the following properties/issues:
- OptBisect object that exists per compilation pipeline, managed similar to PassBuilder/PassManagers
(which makes it more suitable for use in parallel compilations)

- no more layering issues imposed by implementation since instrumentations by design
can live anywhere - lib/Analysis, lib/Passes etc

- since Codegen is still legacy-only we will have to make a joint implementation that
provides a sequential passes numbering through both new-PM IR and legacy Codegen pipelines

- as of right now there is no mechanism for opt-in/opt-out, so it needs to be designed/implemented
Here I would like to ask:
- what would be preferable - opt-in or opt-out?

     \- with legacy implementation passes opt\-in both for bisect and attribute\-optnone support at once\.
       Do we need to follow that in new\-pm implementation?

Also, I would like to ask whether people see current user interface for opt-bisect limiting?
Do we need better controls for more sophisticated bisection?
Basically I'm looking for any ideas on improving opt-bisect user experience that might
affect design approaches we take on the initial implementation.

regards,
Fedor.

Fedor Sergeev <fedor.sergeev@azul.com> writes:

    \- what would be preferable \- opt\-in or opt\-out?

    \- with legacy implementation passes opt\-in both for bisect and

attribute-optnone support at once.
Do we need to follow that in new-pm implementation?

Also, I would like to ask whether people see current user interface
for opt-bisect limiting?

Ideally I would prefer an opt-out model. Practiclaly speaking, I'm not
sure that's possible. Presumably opt-bisect doesn't apply to analysis
passes. What happens if a transformation pass depends on another
transformation pass earlier in the pipeline? If the earlier
transformation pass is bisected out, then...???

It seems to me that optnone and opt-bisect are two different things and
therefore they should be handled orthogonally.

As for the user interface:

It might be nice to have opt-bisect skip/count capability similar to
DebugCounters. But even that might not be enough. Often a bug requires
some subset of transformations to run. For example, if the pipeline is:

A->B->C->D->E

I might need B, D and E to run to see the bug (A and C don't matter).
If I understand things correctly, today opt-bisect would report that all
of A-E need to run to manifest the bug. That's usually plenty good
enough as running and not running E may result in a small enough set of
diffs to be workable. But it may be that running B->D->E and B->D
results in a smaller number of diffs. Skip/count would get us to
B->C->D->E and even that might be an improvement.

I don't see this as a day-one requirement for the new opt-bisect, but
rather a longer-term goal to improve debugging precision.

How does all of this relate to bugpoint? AFAIK bugpoint doesn't use
opt-bisect at all. It can arrive at the B->D->E minimal pipeline. It
seems worthwhile to put some effort into unifying capabilities and
sharing code. bugpoint is a bit of a mess, unfortunately. It would be
great to modernize it and make use of new internal debugging
capabilities that didn't exist when it was created. Maybe that's a
project that could start after the new PM becomes default and the new
opt-bisect is in place.

                          -David

Hi Fedor,

can you make an example where a pass actually needs to opt-out? Because IMO, bisect should quite literally to DebugCounter-style skip every step in every ::run method’s loop. Passes should not even be concerned with this.

Cheers,
Philip

This isn't so much an issue for the optimization pipeline, but code generation involves some passes which are mandatory (e.g. isel).

-Eli

Well, I think we don’t have a clear idea about new-PM codegen should work in general. Is this really something that concerns us right now?

Philip

Philip,

It kinda depends on user expectations.
What do you really expect as a result of your compilation when you set -opt-bisect-limit=X?
Do you just get a resulting IR and scan for the bad pattern?
Then you dont care about pass sequences and do brute-force bisect.

Do you expect to get a runnable code at the end and check for buggy run-time behavior?
Then you need to keep the passes that are required to produce runnable code.
In our Java JIT compiler we have quite a number of passes where we lower the semantics
to C level and those lowerings are absolutely required for the code to be runnable.

regards,
Fedor.

I'm concerned about codegen. If Codegen is not yet ready for the new
PM, should the new PM really become default? I would at least like to
see a plan of how Codegen is going to migrate before the new PM becomes
default. Codegen pass pipelines have been wonky ever since I started
working with LLVM and it would be nice to get that cleaned up.

                            -David

Philip Pfaffe <philip.pfaffe@gmail.com> writes:

Well, I think we don’t have a clear idea about new-PM codegen should work in general. Is this really something that concerns us right now?

I dont believe it has anything to do specifically with New-PM.
It is just a property of getting a “real code”.
There are passes that you cant skip if you want to get down to the runnable code.

regards,
Fedor.

I would really like to separate OptBisect and New-PM-by-default discussions! :slight_smile:

regards,
Fedor.

It kinda depends on user expectations.
What do you really expect as a result of your compilation when you set -opt-bisect-limit=X?
Do you just get a resulting IR and scan for the bad pattern?
Then you dont care about pass sequences and do brute-force bisect.

This is what I’d expect.

opt-bisect is often used to debug why a program compiled at -O0 produces different output to a program compiled at -O1 or -O2. We want to eliminate the bad pass/optimization but still produce a working executable.

Fedor Sergeev <fedor.sergeev@azul.com> writes:

>
>> - what would be preferable - opt-in or opt-out?
>>
>> - with legacy implementation passes opt-in both for bisect and
>> attribute-optnone support at once.
>> Do we need to follow that in new-pm implementation?
>>
>> Also, I would like to ask whether people see current user interface
>> for opt-bisect limiting?
>
> Ideally I would prefer an opt-out model. Practiclaly speaking, I'm not
> sure that's possible. Presumably opt-bisect doesn't apply to analysis
> passes.
Sure it doesnt.

> What happens if a transformation pass depends on another
> transformation pass earlier in the pipeline? If the earlier
> transformation pass is bisected out, then...???
If we talk about current bisection scheme then the only passes that
are run after the bisection point are those required-to-run passes.
And that means required passes should not depend on anything else than
other required passes. Which seems to be a very reasonable restriction to me.

> It seems to me that optnone and opt-bisect are two different things and
> therefore they should be handled orthogonally.
I have heard this opinion more than once :slight_smile:
Makes sense to me as well.

regards,
Fedor.

But they're deeply connected. I debug codegen problems all the time.
That opt-bisect doesn't work with codegen is really unfortunate.

If opt-bisect should work with codegen then we need to think about how
codegen will work with the new PM.

I agree that whether or not the new PM becomes default is somewhat
orthogonal but eventually it will and at that point I hope we have a
functioning opt-bisect for codegen.

                            -David

Fedor Sergeev <fedor.sergeev@azul.com> writes:

Fedor Sergeev <fedor.sergeev@azul.com> writes:

What happens if a transformation pass depends on another
transformation pass earlier in the pipeline? If the earlier
transformation pass is bisected out, then...???

If we talk about current bisection scheme then the only passes that
are run after the bisection point are those required-to-run passes.
And that means required passes should not depend on anything else than
other required passes. Which seems to be a very reasonable restriction
to me.

Let's say opt-bisect is opt-in. Then the pass does something like this:

if (ShouldRun(Me)) {
  ...
}

return;

Let's say pass A and B both opt-in. Pass B depends on pass A. If Pass
A is bisected out, then even though B depends on it and the PassManager
will think it's running pass A, pass A won't actually do anything. Pass
A doesn't know whether it's being run due to a dependency or not.

If opt-bisect is opt-out (so passes don't do anything to participate in
bisection), then in theory the PassManager will run pass A because B
needs it. But the bisect mechanism will have to get out of the way to
fulfill the dependency. This also potentially changes the order passes
run, which could lead to real trouble.

So pass A needs to opt out of opt-bisect. But someone has to know that
something depends on pass A in order to have pass A opt-out (or not
opt-in).

Therefore, it seems like opt-in is safer but unfortunately that makes
for a worse debugging experience.

Now, one could argue that perhaps pass B shouldn't be so strict and have
a dependency on pass A. But it exists today in codegen and maybe other
places.

                       -David

But they're deeply connected. I debug codegen problems all the time.

> That opt-bisect doesn't work with codegen is really unfortunate.
Perhaps I'm missing some context here, but afaik current -opt-bisect-limit does work with codegen.
And even if you turn on new pass manager and use -opt-bisect-limit you will
still get bisect on codegen (which runs under legacy and thus has legacy OptBisect
applied there).

> If opt-bisect should work with codegen then we need to think about how
> codegen will work with the new PM.
Just as it works now - IR passes are run through new PM pipeline, while Codegen passes
are run through legacy pipeline.

> I agree that whether or not the new PM becomes default is somewhat
> orthogonal but eventually it will and at that point I hope we have a
> functioning opt-bisect for codegen.
I do expect opt-bisect to be functional for the whole compilation that involves
new PM at a very first attempt of implementation being discussed here.
Thats why I mentioned the need for "joint implementation" in my original mail.

regards,
Fedor.

>
> -David
>
> Fedor Sergeev <fedor.sergeev@azul.com> writes:
>
>> I would really like to separate OptBisect and New-PM-by-default
>> discussions! :slight_smile:
>>
>> regards,
>> Fedor.
>>
>>> I'm concerned about codegen. If Codegen is not yet ready for the new
>>> PM, should the new PM really become default? I would at least like to
>>> see a plan of how Codegen is going to migrate before the new PM becomes
>>> default. Codegen pass pipelines have been wonky ever since I started
>>> working with LLVM and it would be nice to get that cleaned up.
>>>
>>> -David
>>>
>>> Philip Pfaffe <philip.pfaffe@gmail.com> writes:
>>>
>>>> Well, I think we don't have a clear idea about new-PM codegen should
>>>> work in general. Is this really something that concerns us right now?
>>>>
>>>> Philip
>>>>
>>>> > Hi Fedor,
>>>> >
>>>> > can you make an example where a pass actually needs to opt-out?
>>>> > Because IMO, bisect should quite literally to DebugCounter-style
>>>> skip
>>>> > every step in every ::run method's loop. Passes should not even
>>>> be
>>>> > concerned with this.
>>>> This isn't so much an issue for the optimization
>>>> pipeline, but
>>>> code
>>>> generation involves some passes which are mandatory (e.g. isel).
>>>> -Eli
>>>> --
>>>> Employee of Qualcomm Innovation Center, Inc.
>>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,

But they’re deeply connected. I debug codegen problems all the time.
That opt-bisect doesn’t work with codegen is really unfortunate.
Perhaps I’m missing some context here, but afaik current
-opt-bisect-limit does work with codegen.
And even if you turn on new pass manager and use -opt-bisect-limit you will
still get bisect on codegen (which runs under legacy and thus has legacy
OptBisect
applied there).

One concern for me here is that in legacy optbisect, you will get a continuous counting of passes from IR through codegen, like:
PASS (1): IR pass no.1

PASS (n): IR pass no.n
PASS (n+1): Codegen pass no.1

PASS (n+m): Codegen pass no.m

Now with this new design, we need the new opt-bisect from Pass instrumentation (for new PM for IR) together with
-opt-bisect-limit (for legacy PM for codegen). And they do their own counting separately. It may make bisecting become a little
bit complex.

We may want a wrapper above them so that user will not notice the difference from the change.

I definitely hope there could be one new opt-bisect for new PM that can cover both IR and codegen, but seems it will not
be easy since new PM doesn’t deal with codegen.

Thats why I specifically mentioned in my original mail:

We absolutely need to be able to generate executable programs using opt-bisect, so some mechanism for not skipping required passes is needed. It might be nice to have a mode where no passes are skipped and the IR/MIR is dumped when the bisect limit is reached, but I don't see that as a requirement.

Regarding opt-in versus opt-out, I think we want to make this as easy and transparent to pass developers as possible. It would be nice to have the mechanism be opt-out so that passes that were added with no awareness of opt-bisect would be automatically included. However, there is a small wrinkle to this. I can't defend this as a reasonable design choice, but the SelectionDAGISel pass has a sort of hybrid behavior. It can't actually be skipped, but it OptBisect says it should be skipped it drops the optimization level to OptNone. That's a machine function pass, so it doesn't matter so much right now. It's just something to think about.

One of the reasons that we combined the optnone handling and the opt-bisect handling is that we specifically wanted these two behaviors to be linked. The exact rule we would like to use for opt bisect is that no pass which runs at O0 is skipped by opt-bisect. There's a test that verifies this. Conversely, if a pass is able to respect the optnone attribute then it should also be skippable by opt-bisect. Of course, I would be open to considering a use case where this reasoning isn't desirable.

With regard to there being one OptBisect object per compilation pipeline, I have some concerns. Specifically, the behavior of opt-bisect depends on the sequence of passes run before the limit is reached being consistent and repeatable. My inclination would be to not allow parallel compilation when opt-bisect is enabled. I can imagine cases where you might specifically want to debug something that only happens in a parallel build, but it's more difficult to imagine something that only happens in a parallel build and doesn't depend on interactions between threads. In such a case, would we be able to guarantee that the sequence of passes and any interaction between pipelines was repeatable. Basically, here I feel like I'm exploring a hypothetical idea where other people have specific use cases. If so, please explain the use case to me.

-Andy

Hi Andrew,

We absolutely need to be able to generate executable programs using opt-bisect, so some mechanism for not skipping required passes is needed. It might be nice to have a mode where no passes are skipped and the IR/MIR is dumped when the bisect limit is reached, but I don’t see that as a requirement.

At this point it makes no sense to worry about the code generation pipeline. As long as there is no new-PM design for that, this point is just moot. Designing opt-bisect against code generation without actually understanding what we’re designing against is guaranteed to produce a bad architecture. So lets figure out the optimizer bisect first, and incrementally upgrade that once we’ve ironed out codegen.

Regarding opt-in versus opt-out, I think we want to make this as easy and transparent to pass developers as possible. It would be nice to have the mechanism be opt-out so that passes that were added with no awareness of opt-bisect would be automatically included. However, there is a small wrinkle to this. I can’t defend this as a reasonable design choice, but the SelectionDAGISel pass has a sort of hybrid behavior. It can’t actually be skipped, but it OptBisect says it should be skipped it drops the optimization level to OptNone. That’s a machine function pass, so it doesn’t matter so much right now. It’s just something to think about.

One of the reasons that we combined the optnone handling and the opt-bisect handling is that we specifically wanted these two behaviors to be linked. The exact rule we would like to use for opt bisect is that no pass which runs at O0 is skipped by opt-bisect. There’s a test that verifies this. Conversely, if a pass is able to respect the optnone attribute then it should also be skippable by opt-bisect. Of course, I would be open to considering a use case where this reasoning isn’t desirable.

Mixing OptNone and bisect is a software engineering bug: it’s mixing different layers of abstraction. Bisect is something that’s at pass manager scope: run passes until whatever. OptNone in turn doesn’t belong in the pass manager layer. It only concerns function passes, and crumbles quickly considering other IRUnits or even codegen. I don’t have a clear vision what OptNone handling should look like, but at this point I consider it entirely orthogonal to bisect handling.

From a software architecture perspective I don’t see a reason why passes should even know about something like bisect happening. That is simply not their domain. If a pass shouldn’t be skipped for whatever reason, that’s not something the pass should worry about, that’s the bisect driver’s problem! My proposal here would be make it an opt-out design, but let the driver control that. E.g., for skipping, let the user provide a list of passes they don’t want skipped.

With regard to there being one OptBisect object per compilation pipeline, I have some concerns. Specifically, the behavior of opt-bisect depends on the sequence of passes run before the limit is reached being consistent and repeatable. My inclination would be to not allow parallel compilation when opt-bisect is enabled.

I don’t have a strong opinion here, but just as a data point: my mental model here is to expect bisect to expect a deterministic outcome per module. That model isn’t threatened by parallel execution.

Cheers,
Philip

Well, I did not really mean to emphasize parallel compilation topic here.
But as you asked - our JIT compiler which is LLVM library linked into java machine typically performs
multiple parallel compilations, each compiling a separate module from a separate context in a single thread.
It is not your typical fully-parallel compilation since every compile is independent on LLVM level.
However as it is a library in a single process, it does share all the globals, OptBisect object in particular.
Naturally, that makes -opt-bisect-limit usage for live in-VM compilation rather problematic.

Having OptBisect object handled separately for each individual compilation pipeline enables us
with ability to apply bisection to the live in-VM compilation.
(recently we did introduce OptPassGate interface that allows to install a different OptBisect for each context,
but it is much less clean than what we can get with new-pm).

regards,
Fedor.