This is an archive of the discontinued LLVM Phabricator instance.

[FaultMaps] Let the frontend pre-select implicit null check candidates.
ClosedPublic

Authored by sanjoy on Jun 29 2015, 4:33 PM.

Details

Summary

This change introduces a !make.implicit metadata that allows the
frontend to pre-select the set of explicit null checks that will be
considered for transformation into implicit null checks.

The reason for not using profiling data instead of !make.implicit is
explained in the change to FaultMaps.rst.

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 28730.Jun 29 2015, 4:33 PM
sanjoy retitled this revision from to [FaultMaps] Let the frontend pre-select implicit null check candidates..
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added a subscriber: Unknown Object (MLST).

Some questions about the direction:

1 - How early/late do you expect the frontend to insert these annotations? If it's early, isn't there a very real chance that the annotations will get dropped/misplaced during optimization? Conversely, if it's late, isn't it going to be difficult for the frontend to correlate the IR to the side information you're expecting it to use?
[I understand it won't be a correctness issue either way, but the performance issue seems real.]

2 - I anticipate that for LLILC we'll want this to be profile-driven -- we don't have healing, but typically (in other .Net JITs) use machine faults anyway for the null checks that are implicit in MSIL instructions because we're comfortable assuming that their failure rate is effectively zero; so I'd expect that our reader will annotate branch profiles with that assumption, that optimizations will make a reasonable effort to propagate the branch profiles (please correct me if that's a bad assumption), and that we'll then want to consume that information for the implicit null check optimization. It seems like that approach will be perfectly compatible with this change if we simply add a pass that LLILC can opt into / you can opt out of that runs just before implicit null check optimization which annotates super-cold checks as !make-implicit. So my questions are
2a - Does that approach sound feasible to you?
2b - Was your change of direction simply because you think you'll get better performance this way, or are there any issues with using profile information that you're aware of that we'll run into if we add a pass like I just described?

[Of course, if metadata annotations are more robust than I'm imagining, #2 is a non-issue and we can just annotate branches appropriately when we initially generate LLVM IR.]

The code itself looks good to me given the direction.

This change tries to be conservative towards making null checks
implicit, the assumption being that it is okay to fail to make some
cold null checks implicit but it is not okay to accidentally make a
hot (or even lukewarm) null check implicit.

1 - How early/late do you expect the frontend to insert these annotations? If it's early, isn't there a very real chance that the annotations will get dropped/misplaced during optimization? Conversely, if it's late, isn't it going to be difficult for the frontend to correlate the IR to the side information you're expecting it to use?

Our frontend inserts these early (during IR generation) so there is a
possibility that the metadata will get dropped, and we will miss the
optimization. However, any metadata based annotation scheme faces
this same problem, and it can be fixed on a case by case basis as we
encounter optimizations that drop this metadata unnecessarily. In
practice, I think it will be adequate to add a second clause to places
within LLVM that touch the !prof metadata.

I'm also not opposed to having an '-aggressive' switch that bypasses
the check for !make.implicit metadata.

2 - I anticipate that for LLILC we'll want this to be profile-driven -- we don't have healing, but typically (in other .Net JITs) use machine faults anyway for the null checks that are implicit in MSIL instructions because we're comfortable assuming that their failure rate is effectively zero; so I'd expect that our reader will annotate branch profiles with that assumption,
that optimizations will make a reasonable effort to propagate the branch profiles (please correct me if that's a bad assumption),

I think that is reasonable. Moreover, I don't think you'll have any
trouble fixing and upstreaming fixes to optimization passes to make
them better preserve branch profiles (if you find any issues).

and that we'll then want to consume that information for the implicit null check optimization. It seems like that approach will be perfectly compatible with this change if we simply add a pass that LLILC can opt into / you can opt out of that runs just before implicit null check optimization which annotates super-cold checks as !make-implicit. So my questions are

2a - Does that approach sound feasible to you?

Yes. We can also factor the logic that selects null checks that are
to be made implicit into a separate pass if it gets too complicated.

2b - Was your change of direction simply because you think you'll get better performance this way, or are there any issues with using profile information that you're aware of that we'll run into if we add a pass like I just described?

So for us, coldness of a branch is necessary but not sufficient to
guarantee that making a null check implicit will be profitable. In
other words, even if LLVM is able to prove (I don't know if it can do
this currently) that a certain null check is very cold, it may not be
safe to make the check implicit if the failing path does not have code
to heal the null check. This is why we needed something stronger than
branch profiling data.

  • Sanjoy

Sounds good to me. I like the idea of an '-aggressive' switch; without it, the profile-driven pre-pass would either need to redundantly pattern-match to determine which compares precede dereferences or needlessly annotate irrelevant compares with !make-implicit.

This revision was automatically updated to reflect the committed changes.