RFR: 8298952: All nodes should have type(n) == Value(n) after IGVN [v3]
Tobias Hartmann
thartmann at openjdk.org
Tue Jan 31 08:14:15 UTC 2023
On Mon, 30 Jan 2023 12:31:38 GMT, Emanuel Peter <epeter at openjdk.org> wrote:
>> I want to verify that **type(n) == Value(n)** after every IGVN round. Basically: all optimizations that can be made should be made.
>>
>> FYI: this is a part of a bigger effort to verify IGVN, and refactor the notification code for CCP and IGVN:
>> [JDK-8298951](https://bugs.openjdk.org/browse/JDK-8298951) `Umbrella: improve CCP and IGVN verification`
>> I recently implemented CCP Node::Value verification [JDK-8257197](https://bugs.openjdk.org/browse/JDK-8257197).
>>
>> I'm extending the flag `-XX:+VerifyIterativeGVN` (used to enable Use-Def verification) to `-XX:VerifyIterativeGVN=XY`, where `X` can enable the Value verification (low overhead), and `Y` enables the Use-Def verification (very slow, requires increasing timeouts).
>>
>> This patch has passed tier1-5 and stress testing. Performance testing showed no significant runtime change.
>>
>> **I would love to hear your opinion, especially about the special cases, but also my fixes named below.**
>>
>> For the verification to pass, I had to **fix some things**:
>> - Add `gvn.transform` to some `new Node` cases where it was missing, else I got `type(n) == nullptr`.
>> - Add missing notification logic in `PhaseIterGVN::add_users_to_worklist`: notify tripcount phi of LongCountedLoop if the limit changes (int case was already implemented), notify Sub node if input CastII has changing input, notify And in shift-and (shift-mask) operation. Every optimization should have corresponding notification if (recursive) inputs change. These were easy to fix examples.
>> - `ConstraintCastNode::Value` violated the idempotence guarantee: subsequent calls to Value returned different values. Fixed that.
>> - `CastLLNode::Ideal` can be widened after loop-opts, with the goal of commoning CastLL nodes. For that, we need to call `record_for_post_loop_opts_igvn` for them, even before IGVN (when `can_reshape` is still false). They may otherwise not land on the post loop-opts worklist.
>> - During CCP, some integer types are saturated (widened). But IGVN could narrow them again. So add them to IGVN worklist if they are saturated (widened) during CCP.
>> - `kill_dead_code`: tries to remove dead nodes recursively, in analogy to what IGVN would do, but more efficiently. Unfortunately, we do not call `add_users_to_worklist` for the dead nodes, which IGVN would do. I do the notification once per dead node now. `kill_dead_code` could be refactored and made more efficient, maybe we can do that in a future RFE.
>> - `PhaseIdealLoop::clone_loop_handle_data_uses` calls `_igvn.replace_input_of(use, idx, phi)`, but does not notify the users. I got a failure in tier5-common, where use was a CmpI of a loop-exit test, and the tripcount-phi needed to be notified. I added notification here, but I wonder if it needs to be added to `replace_input_of` generally?
>> - `CastII`: implemented notification for `CmpI -> Bool -> If -> IfProj -> CastII`. This handles case where previously we have `in1 != X`, see comment in code.
>> - `Sub` with input of chain of `ConstraintCast`: rare case, implemented a BFS traversal down the casts, to the `Sub` nodes.
>> - Replaced a `set_req` with `set_req_X` in `CmpPNode::Ideal`, as it removed the last use of the previous input, and lead to `fatal error: no reachable node should have no use`.
>>
>> As with CCP Node::Value verification, a few cases have to be **exempt from verification (special cased)**.
>> https://github.com/openjdk/jdk/blob/fe5552be65e9dd9c044d41e8295bb176d9754e28/src/hotspot/share/opto/phaseX.cpp#L1244-L1296
>>
>> - `Integer` widen: expected, must special case.
>> - `Load`: must special case because of deep traversal in Value. We may be able to make special case logic more precise. One might also experiment with deep notification, but that could be expensive and complex. I would leave special case as is, and address improvements in a future RFE.
>> - `CmpP`: deep traversal of CFG to determine domination (independence between two pointers). Probably needs to be special cased.
>>
>> **Note**: I want to address these `memory` optimizations in a follow up RFE. We had the idea of simply putting all these nodes on a special list that is always processed during IGVN. We will have to investigate performance impact either way.
>
> Emanuel Peter has updated the pull request incrementally with one additional commit since the last revision:
>
> Fix tests that directly query TypeProfileLevel, we had issues because I changed the type
Great work, Emanuel. Nice analysis and comments in code.
> I added notification here, but I wonder if it needs to be added to replace_input_of generally?
Yes, I think that would be cleaner.
I added some minor suggestions. You also need to update the copyright dates of the modified files.
src/hotspot/share/opto/c2_globals.hpp line 623:
> 621: develop(uint, VerifyIterativeGVN, 0, \
> 622: "Verify Iterative Global Value Numbering" \
> 623: "=XY, with Y: verify Def-Use modifications during sparse IGVN" \
Do you understand what "sparse" refers to? Maybe we should simply remove that word.
src/hotspot/share/opto/connode.hpp line 57:
> 55: class ConINode : public ConNode {
> 56: public:
> 57: ConINode( const TypeInt *t ) : ConNode(t) {
Suggestion:
ConINode(const TypeInt* t) : ConNode(t) {
src/hotspot/share/opto/node.hpp line 415:
> 413: #ifdef ASSERT
> 414: bool is_dead() const;
> 415: static bool is_not_dead(const Node* n);
Should this be non-static?
src/hotspot/share/opto/node.hpp line 716:
> 714: DEFINE_CLASS_ID(CompressM, Vector, 6)
> 715: DEFINE_CLASS_ID(Con, Type, 19)
> 716: DEFINE_CLASS_ID(ConI, Con, 0)
Suggestion:
DEFINE_CLASS_ID(Con, Type, 19)
DEFINE_CLASS_ID(ConI, Con, 0)
src/hotspot/share/opto/phaseX.cpp line 1244:
> 1242: }
> 1243:
> 1244: // Check that if type(n) == n->Value(), return true if we have a failure.
Suggestion:
// Check that type(n) == n->Value(), return true if we have a failure.
src/hotspot/share/opto/phaseX.cpp line 1251:
> 1249: bool PhaseIterGVN::verify_node_value(Node* n) {
> 1250: // If we assert inside type(n), because the type is still a nullptr, then maybe
> 1251: // the node never went through gvn.transform, which would be a bug.
Suggestion:
// the node never went through gvn.transform, which would be a bug.
src/hotspot/share/opto/phaseX.cpp line 1705:
> 1703: if (in1 != in2) { // if they are equal, the CmpI can fold them away
> 1704: if (in1 == n) {
> 1705: // in1 modified -> could turn into X -> do traversal basen on right pattern.
Suggestion:
// in1 modified -> could turn into X -> do traversal based on right pattern.
src/hotspot/share/opto/phaseX.cpp line 1708:
> 1706: for (uint i2 = 0; i2 < cmp->outcnt(); i2++) {
> 1707: Node* bol = cmp->raw_out(i2); // For each Bool
> 1708: if(bol != nullptr && bol->is_Bool()) {
Suggestion:
if (bol != nullptr && bol->is_Bool()) {
src/hotspot/share/opto/phaseX.cpp line 1711:
> 1709: for (uint i3 = 0; i3 < bol->outcnt(); i3++) {
> 1710: Node* iff = bol->raw_out(i3); // For each If
> 1711: if(iff != nullptr && iff->is_If()) {
Suggestion:
if (iff != nullptr && iff->is_If()) {
src/hotspot/share/opto/phaseX.cpp line 1714:
> 1712: for (uint i4 = 0; i4 < iff->outcnt(); i4++) {
> 1713: Node* if_proj = iff->raw_out(i4); // For each IfProj
> 1714: if(if_proj != nullptr && (if_proj->is_IfFalse() || if_proj->is_IfTrue())) {
Suggestion:
if (if_proj != nullptr && (if_proj->is_IfFalse() || if_proj->is_IfTrue())) {
src/hotspot/share/opto/phaseX.cpp line 1786:
> 1784: }
> 1785: // If changed LShift inputs, check And users for shift and mask (And) operation
> 1786: if(use_op == Op_LShiftI || use_op == Op_LShiftL) {
Suggestion:
if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
-------------
Changes requested by thartmann (Reviewer).
PR: https://git.openjdk.org/jdk/pull/11775
More information about the hotspot-compiler-dev
mailing list