RFR: 8333258: C2: high memory usage in PhaseCFG::insert_anti_dependences()

[Roland Westrelin]

On Wed, 19 Jun 2024 16:28:15 GMT, Vladimir Kozlov <kvn at openjdk.org> wrote:

>> In a debug build, `PhaseCFG::insert_anti_dependences()` is called
>> twice for a single node: once for actual processing, once for
>> verification.
>> 
>> In TestAntiDependenciesHighMemUsage, the test has a `Region` that
>> merges 337 incoming path. It also has one `Phi` per memory slice that
>> are stored to: 1000 `Phi` nodes. Each `Phi` node has 337 inputs that
>> are identical except for one. The common input is the memory state on
>> method entry. The test has 60 `Load` that needs to be processed for
>> anti dependences. All `Load` share the same memory input: the memory
>> state on method entry. For each `Load`, all `Phi` nodes are pushed 336
>> times on the work lists for anti dependence processing because all of
>> them appear multiple times as uses of each `Load`s memory state: `Phi`s
>> are pushed 336 000 on 2 work lists. Memory is not reclaimed on exit
>> from `PhaseCFG::insert_anti_dependences()` so memory usage grows as
>> `Load` nodes are processed:
>> 
>> 336000 * 2 work lists * 60 loads * 8 bytes pointer = 322 MB. 
>> 
>> The fix I propose for this is to not push `Phi` nodes more than once
>> when they have the same inputs multiple times.
>> 
>> In TestAntiDependenciesHighMemUsage2, the test has 4000 loads. For
>> each of them, when processed for anti dependences, all 4000 loads are
>> pushed on the work lists because they share the same memory
>> input. Then when they are popped from the work list, they are
>> discarded because only stores are of interest:
>> 
>> 4000 loads processed * 4000 loads pushed * 2 work lists * 8 bytes pointer = 256 MB. 
>> 
>> The fix I propose for this is to test before pushing on the work list
>> whether a node is a store or not.
>> 
>> Finally, I propose adding a `ResourceMark` so memory doesn't
>> accumulate over calls to `PhaseCFG::insert_anti_dependences()`.
>
> We should use `VectorSet` for something like that.
> `worklist_visited` is definitely should be `VectorSet`.
> Instead of `already_enqueued` we should add `VectorSet` for `mem` to check if it was processed before. This assumes that this loop don't modify graph. Unfortunately we have one modification `store->add_prec(load);` which we should do something about. I may miss other ocde which modify graph.

VectorSet would work for worklist_visited but it's not the thing that I'm trying to fix here. @vnkozlov's comment is not only about worklist_visited.

Also if there are few uses, the existing code would only have to go over a few `worklist_visited` elements while using a `VectorSet` would possibly require zeroing a small array. Is it that clear cut that a `VectorSet` is always better?

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

PR Comment: https://git.openjdk.org/jdk/pull/19791#issuecomment-2180549488