Eliminate MethodFromClassRecord SVM records

[dsouzai]

The getResolvedMethods frond end query generates unnecessary MethodFromClassRecord SVM validation records; it creates a validation record for each method in a class. The reason is because the front end can't tell which of those resolved methods the compiler is going to use, and the SVM needs every (used) resolved method accounted for. I found a way to sidestep this (#23587). This PR and this bit of code for the MethodFromClassRecord

openj9/runtime/compiler/runtime/SymbolValidationManager.cpp

Lines 869 to 870 in 79f167d

	SVM_ASSERT_ALREADY_VALIDATED(this, beholder);
	return addVanillaRecord(method, new (_region) MethodFromClassRecord(method, beholder, index));

though highlights a characteristic that was overlooked right from the beginning: its only real purpose is to associate an ID to a method in a class; it doesn't actually help with any additional validation¹. This is because it requires its defining class to have been validated, which involves a class chain validation; therefore, the method's index is guaranteed to be the same by virtue of the class chain validation.

Thus, the SVM needs to be updated to only generate IDs for methods of classes and not actually create validation records for them. However, this requires having some way of linking the ID associated with a class with the IDs that will be associated with its methods, such that it does not require a validation record; otherwise, there is no benefit as every class with require 2 or 3 validation records (Class and/or ClassChain, and MethodsFromClass). Essentially, there has to be a way on the load run for the SVM to generate IDs for methods of a class such that they are exactly the same as those generated in the compile run.

The only way (I can think of thus far) to do so is to generate the method IDs immediately after the class ID. This has the effect of moving a method ID association from a later point in a compilation to an earlier point, which changes which record was the first to generate the ID, but does not change consistency between records with the same ID². This turns out to be fairly non-trivial. The reason is related to constraints associated with the Well Known Classes, Array Classes, and possibly others.

For example, with the WKC, the IDs for the methods must be generated using the guaranteed ID generator, since the WKC ID generated after the previous WKC's methods must be consistent across runs. However, for other classes, the ID cannot be generated with the guaranteed ID generator since on a load run, the SVM does not increment IDs during validation (except for the guaranteed ones) and instead acquires them from the validation records loaded out of the SCC; thus, the method IDs must use their defining class's ID as a starting point.

All this gets complicated and sticky really quickly. After a failed attempt at what I thought was going to be a simple extension of the getResolvedMethods improvement above, I'm opening this issue to track this since this probably does have a decent amount of benefit.

Footnotes

1. Technically this statement isn't entirely accurate; if it were there would be no need to associate IDs to the methods at all (see https://github.com/eclipse-openj9/openj9/issues/23558#issuecomment-4099744672). ↩

2. I should note a very subtle point. Generating IDs immediately after generating an ID for a class means that Scenario 4 in https://github.com/eclipse-openj9/openj9/pull/23587 will never happen. ↩

[dsouzai]

@jdmpapin (in case you find this an interesting read).

[jdmpapin]

A few thoughts.

its only real purpose is to associate an ID to a method in a class; it doesn't actually help with any additional validation.

Associating IDs with values at load time is itself also a form of validation, where the SVM checks that the value corresponds correctly to any prior uses of the same ID, and doesn't correspond to any distinct ID. Essentially we're just validating that the live "RAM" entities relate to each other in the right way. I don't think it's all that unusual for this to be the only form of validation represented by a validation record. For example, some other records that work similarly would be superclass from class, and array class.

generate the method IDs immediately after the class ID.

One problem with this strategy, which you might or might not consider significant, is that it means always assigning IDs to every method of a class even if getResolvedMethods() might never be called on it. (At least, I don't know that we always call it on every class the compiler encounters.) IIRC, SVM IDs are 16-bit, and a class can have up to 16 bits worth of methods. So if a class has many methods, but would not have been the subject of getResolvedMethods(), or maybe if there are a few such classes, then this strategy could unnecessarily exhaust the space of available IDs.

Are there a lot of calls to getResolvedMethods()? One idea, just for your consideration, would be to try to put restrictions on it that allow the compiler to discover which subset of the methods are actually significant. There could be a new type that represents the method without revealing its "RAM" identity, so you can have unrestricted use of the info that is already determined by the class chain validation, e.g. method index, name, signature. And then if you want to get a real TR_ResolvedMethod*, then you can "hydrate" it into one, which would involve generating a validation. Crucially then the validations would be only for the specific methods that need them.

[dsouzai]

Associating IDs with values at load time is itself also a form of validation, where the SVM checks that the value corresponds correctly to any prior uses of the same ID, and doesn't correspond to any distinct ID. Essentially we're just validating that the live "RAM" entities relate to each other in the right way. I don't think it's all that unusual for this to be the only form of validation represented by a validation record. For example, some other records that work similarly would be superclass from class, and array class.

Eliminating the explicit MethodFromClass records doesn't remove this type of validation; the relation between two types of validations still holds. If we consider the before and after:

Before:

1. J9Method 0xA is given ID x by a VirtualMethodFromCP record
2. J9Method 0xA is also acquired via a getMethodFromClass front end query, but since it has already been seen by the SVM, the x ID is reused

After:

1. J9Method 0xA is given ID y when its class is validated
2. J9Method 0xA is acquired by a virtualmethodFromCP query, but since it has already been seen by the SVM, the y ID is reused

In both scenarios, the ID is the same, and thus at validation time, consistency must be maintained. Thus, all that changed is what first defined the ID for 0xA.

One problem with this strategy, which you might or might not consider significant, is that it means always assigning IDs to every method of a class even if getResolvedMethods() might never be called on it. (At least, I don't know that we always call it on every class the compiler encounters.) IIRC, SVM IDs are 16-bit, and a class can have up to 16 bits worth of methods. So if a class has many methods, but would not have been the subject of getResolvedMethods(), or maybe if there are a few such classes, then this strategy could unnecessarily exhaust the space of available IDs.

I did think about this. However, given that the SVM IDs are uint16_t, that gives us 65k symbols to work with. A Java Class can have exactly this number of methods (though then it would have no more space for other entries such as CP entries). In general, given the large number of methods available, I suppose this does risk exhaustion, but statistically I think this is unlikely in a compilation. Maybe if we ever started doing hot/very-hot/scorching relocatable compilations, this might become a problem.

Are there a lot of calls to getResolvedMethods()?

My MethodsFromClass prototype I think reduced the number of MethodFromClass records (caused by getResolvedMethods) by ~11k in one bench, so about 90kib in savings. Removing MethodFromClass in general I think has the potential to save even more (if I can manage to get it to work).

One idea, just for your consideration, would be to try to put restrictions on it that allow the compiler to discover which subset of the methods are actually significant. There could be a new type that represents the method without revealing its "RAM" identity, so you can have unrestricted use of the info that is already determined by the class chain validation, e.g. method index, name, signature. And then if you want to get a real TR_ResolvedMethod*, then you can "hydrate" it into one, which would involve generating a validation. Crucially then the validations would be only for the specific methods that need them.

This would be the most ideal way to go about it; I just don't know how easy it is to do so compared to auto ID generation for methods of a class.

[jdmpapin]

Eliminating the explicit MethodFromClass records doesn't remove this type of validation

To clarify, I didn't think you were suggesting removing that validation per se. I was just responding to the idea that the record doesn't really do validation.

... this strategy could unnecessarily exhaust the space of available IDs.

... Maybe if we ever started doing hot/very-hot/scorching relocatable compilations, this might become a problem.

I don't think this would be very related to the opt level. It's just about whether the compiler comes across classes with many methods. Of course, maybe it's not a concern if those classes are rare enough to come by, or if they can just be considered too expensive to deal with properly in AOT compilations. I know typical classes have nowhere near enough methods to be a problem.

[Edit: I was thinking mainly of very high numbers of methods in a single class, like at least 10k. Maybe you were thinking of more modest but still sort of large counts, e.g. 100 methods per class. In that case I can see where there could be a connection to opt level, since we might expect higher opt compilations to encounter many more classes.]

Are there a lot of calls to getResolvedMethods()?

My MethodsFromClass prototype I think reduced the number of MethodFromClass records ...

Sorry, I meant statically. Essentially: are there a lot of call sites that would need to be updated if you wanted to use my idea, or are there only a few?

One idea ... would be to try to put restrictions on it that allow the compiler to discover which subset of the methods are actually significant. ...

This would be the most ideal way to go about it; I just don't know how easy it is to do so compared to auto ID generation for methods of a class.

Since you seem to agree about the approach, I'd suggest trying to evaluate how easy/hard it would be. If nothing else, I think it's obviously correct, so it might be the easy option in that sense even if it involves more churn.

---

Some more thoughts on the core proposal here.

I don't think it would work in general to choose which methods get fresh IDs based on whether they've been seen before. That doesn't seem correctly repeatable at load time, or if it is, then I think the reasoning justifying it would be very subtle.

One observation though is that method records also tell you the defining class, so the first time you encounter a class, it's not possible for more than one of its methods to have been seen already.

The best I can come up with at the moment is this: The first time a class is encountered and associated with a previously unused ID i, i must be greater than all other IDs used up to that point. (Right? 😅) So then its methods are assigned IDs i+1, i+2, ..., i+n in the order they're given in the bytecode/ROM class. Then if the class was the defining class from a method record, the method ID in that record must be i+k for some 1≤k≤n. That is, it shouldn't be allowed to affect the way that IDs are assigned to the methods. There's some extra weirdness in that the class won't even have passed its class chain validation yet, which determines how many methods it defines, but I guess it will necessarily be just about to do so in the next record or so. I think this scheme would probably work, but it would take some more thought to be sure.

[dsouzai]

The best I can come up with at the moment is this: The first time a class is encountered and associated with a previously unused ID i, i must be greater than all other IDs used up to that point. (Right? 😅) So then its methods are assigned IDs i+1, i+2, ..., i+n in the order they're given in the bytecode/ROM class. Then if the class was the defining class from a method record, the method ID in that record must be i+k for some 1≤_k_≤_n_. That is, it shouldn't be allowed to affect the way that IDs are assigned to the methods. There's some extra weirdness in that the class won't even have passed its class chain validation yet, which determines how many methods it defines, but I guess it will necessarily be just about to do so in the next record or so. I think this scheme would probably work, but it would take some more thought to be sure.

This is essentially what my failed attempt involved. Right after associating a fresh ID to a class, associate IDs to its methods (ie, iterate over all its methods, associate IDs). Conceptually I know this is correct, but I was just getting bogged down in the implementation details. The WKC is a good example, where you have to use getNewSymbolID() to generate the IDs, but for classes from explicit validation records, you have to use the ID of the class. But even there, because you can start off with an array class, you need to make sure you do it only for the base component and right after.

Hence this issue; maybe I will get time one day to correctly implement this, or someone else will heh.