RFR: 8301489: ShortLoopOptimizer might lift instructions before their inputs

[Tobias Hartmann]

On Thu, 15 Jun 2023 11:13:02 GMT, Daniel Skantz <duke at openjdk.org> wrote:

> ShortLoopOptimizer might lift instructions before their inputs on some graph shapes. We propose adding a check that the insertion point for an instruction that is a candidate for hoisting should not be higher up the dominator tree than any inputs to the instruction.
> 
> Testing: tier1-tier3.
> 
> Additional testing: observed that `(cur_invariant && !v.is_valid())` never occurs on tier1-tier3 before the added test case.
> Also verified that the depth check is equivalent to `(*vp->block() == _insert->block()) || dominates(*vp, _insert)` on all of tier1-tier3.
> 
> Failure case: in the attached image the `arraylength` instruction from B10 is lifted to B0, as the dominator of B10 is calculated as B0. This is based on the logic in [`ComputeLinearScanOrder::compute_dominator_impl`](https://github.com/openjdk/jdk/blob/master/src/hotspot/share/c1/c1_IR.cpp#L801).  But the array input is in Block 3. This is later spotted in `c1_LIRAssembler.cpp` with `Error: ShouldNotReachHere()`. We can reproduce the error on other instructions too -- the reader may refer to the test case provided.
> 
> ![image](https://github.com/openjdk/jdk/assets/111436254/9130516c-073d-45d1-a38a-af776e5e6672)

Great work investigating this, Daniel! 

>From your comments in JBS, it seems that the underlying issue is additional exception edges in the graph that affect dominator computation. Could you elaborate a bit more on that with respect to the example that you provided in the PR description?

I'm not an expert in C1 though (paging @veresov and @rwestrel as the author of JDK-7153771).

Thanks,
Tobias

src/hotspot/share/c1/c1_ValueMap.cpp line 367:

> 365:   bool _valid = true;
> 366: 
> 367:   void visit(Value* vp) {

Since `Value` is already a pointer type, can't we use `Value v` here?

src/hotspot/share/c1/c1_ValueMap.cpp line 375:

> 373: 
> 374:  public:
> 375:   bool is_valid() {return _valid; }

Suggestion:

  bool is_valid() { return _valid; }

src/hotspot/share/c1/c1_ValueMap.cpp line 380:

> 378: #ifdef ASSERT
> 379:       assert(insert != nullptr, "insertion point should not be null");
> 380: #endif

Suggestion:

    assert(insert != nullptr, "insertion point should not be null");

-------------

PR Review: https://git.openjdk.org/jdk/pull/14492#pullrequestreview-1485433201
PR Review Comment: https://git.openjdk.org/jdk/pull/14492#discussion_r1233546636
PR Review Comment: https://git.openjdk.org/jdk/pull/14492#discussion_r1233545065
PR Review Comment: https://git.openjdk.org/jdk/pull/14492#discussion_r1233544383