Bad graph detected in build_loop_late but I have no clue

[Roland Westrelin]

> Isn’t that paper describe global code motion? Is build_loop_early/late() actually doing code motion before real loop optimizations?
>
> In particular, I don’t understand this statement.
>   set_ctrl(n, least);
>
> Is this set_ctrl(Y, X) saying Y control dependent on X.  The definition of control dependence is in [2]?

No, it's not a control dependence. A control dependence would be an edge
between Y and X. build_loop_early/late() is not doing code motion
either. In that case, Y is a floating node. So there's no need for code
motion as it can freely move within the constraints encoded by input and
output edges. What build_loop_early/late() does is find the earliest
legal placement for a floating node (after all its inputs), the latest
legal placement (before all its uses) and the best placement (as late as
possible but out of loops if possible). That placement is then recorded
by by set_ctrl() that is by associating a floating node with a control
node (which cannot float). The result is not a schedule of nodes either
because how 2 floating nodes should be ordered is not computed and
recorded.

> So far, I found that PhaseIdealLoop::_nodes[IDX]  can be any of 3 different values.
>
>   1.  NULL, which means IDX is dead.
>   2.  A CFG node with the lowest bit set.  Assigned by set_ctrl.
>   3.  IdealLoopTree*, when this node is the head of a loop.
>
> Do I understand this data-structure right?  So PhaseIdealLoop doesn’t have “BasicBlocks” and it uses _nodes to mark where a node belongs to?

Yes, so for instance if you need to know what loop a floating node is
part of, you first retrieve its control with get_ctrl() and then the
loop that the control node if part of with get_loop().

> I understand that (legal->is_Start() && !early->is_Root()) is a legit assertion,  I believe I mess up the ideal graph somewhere and cause this fiasco.
> Could you  give me a pointer which node is broken? Or, could you share me with some hints how to debug this kind of problem?

That:

> idom[3]  760  If  ===  522  559  [[ 1604  486 ]] P=0.999999, C=-1.000000 !jvms: Handler::parseURL @ bci:88
> idom[4]  522  Region  ===  522  799  800  [[ 522  531  253  254  680  760 ]]  !jvms: String::coder @ bci:3 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75

and

> idom[22]  531  If  ===  522  559  [[ 940  261 ]] P=0.999999, C=-1.000000 !jvms: String::coder @ bci:14 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
> idom[23]  522  Region  ===  522  799  800  [[ 522  531  253  254  680  760 ]]  !jvms: String::coder @ bci:3 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75

Doesn't seem right. Both If have Region 522 as control input. That's not
legal. There should only be one control use for 522.

Roland.