RFR: 8312980: C2: "malformed control flow" created during incremental inlining [v4]

[Roland Westrelin]

On Tue, 10 Oct 2023 09:47:20 GMT, Roland Westrelin <roland at openjdk.org> wrote:

>> Hi @rwestrel  thanks for analyzing this bug!
>> 
>> If I understand your algo correctly, you follow down the uses over all paths. But it is not a DFS, you might visit nodes multiple times if there are multiple paths to it. Can there be multiple paths? And if they fork and join many times, there could be an exponential explosion of paths.
>> 
>> If you find some use that is dominated by `ctl`, then you clone the path. You do this again and again, possibly with many paths. You possibly clone nodes multiple times if there is overlap between the paths.
>> 
>> So what exactly happens if there are 2 paths to a node that is dominated by `ctl`? Are eventually all inputs properly and consistently replaced? Can you help me get convinced here? Does it somehow rely on IGVN to common some cloned nodes again?
>> 
>> **An alternative**: First do a down-BFS starting at all replaced nodes, and find all candidate nodes for cloning. The boundary of the down-BFS is at Phi, CFG or pinned nodes, but goes through all other nodes. You mark the boundary nodes that need their inputs cloned.
>> Now you do a up-BFS starting at these marked nodes through the candidate nodes only, to find  which nodes you actually need to clone.
>> This way, you only need 2 BFS, the cost is cleanly limited. And I feel like correctness would be easier to understand/prove.
>
>> If I understand your algo correctly, you follow down the uses over all paths. But it is not a DFS, you might visit nodes multiple times if there are multiple paths to it. Can there be multiple paths? And if they fork and join many times, there could be an exponential explosion of paths.
> 
> Yes, that's right.
> 
>> If you find some use that is dominated by `ctl`, then you clone the path. You do this again and again, possibly with many paths. You possibly clone nodes multiple times if there is overlap between the paths.
> 
> That's correct.
> 
>> So what exactly happens if there are 2 paths to a node that is dominated by `ctl`? Are eventually all inputs properly and consistently replaced? Can you help me get convinced here? Does it somehow rely on IGVN to common some cloned nodes again?
> 
> It does rely on igvn. The traversal stops at CFG nodes or pinned nodes. All nodes in between are freely floating nodes. Most will be commoned. There might be some exceptions (`SubTypeCheck` nodes wouldn't be commoned by igvn) but they are harmless as none of these nodes have side effects. 
> 
>> **An alternative**: First do a down-BFS starting at all replaced nodes, and find all candidate nodes for cloning. The boundary of the down-BFS is at Phi, CFG or pinned nodes, but goes through all other nodes. You mark the boundary nodes that need their inputs cloned. Now you do a up-BFS starting at these marked nodes through the candidate nodes only, to find which nodes you actually need to clone. This way, you only need 2 BFS, the cost is cleanly limited. And I feel like correctness would be easier to understand/prove.
> 
> The classical c2 way would be to keep a map of old and cloned nodes to avoid duplicates. But unless the current implementation is demonstrated to be too expensive I don't see the need to make it more complicated. I don't believe there's a correctness issue given all nodes with a side effect should be pinned so no node with a side effect will be duplicated.

> @rwestrel It took me a day, but I found an example:

Well done. I pushed an updated fix. In principle, the fix remains the same but cloning happens in 3 steps. First all nodes that need to be cloned are collected. Then all of them are cloned and a mapping from current to cloned nodes is kept. Finally edges of the cloned nodes are updated using the mapping.

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

PR Comment: https://git.openjdk.org/jdk/pull/15905#issuecomment-1774716960