validator: goes into infinite loop when a block branches to itself and nothing else about spirv-tools HOT 8 CLOSED

The OpCapability Shader is essential to forcing the infinite loop.

from spirv-tools.

It seems to happen when you branch with an OpBranch instead of OpBranchConditional. I had a unit test for this scenario but it only tested the sane case :).

Looking into it now.

from spirv-tools.

Adding some logging, it's only showing up in the post-dom calculation. It looks like the undefined_dom value is 3 instead of 5 like it is for the (forward) dom calculation. Might be my bug in how I did the augmentation. :-(
I'm gonna quit for the night and come at this fresh tomorrow. If you can see it quickly then great. :-)

from spirv-tools.

That's probably because the post-dom tree only contains one node (+2 pseudo nodes).

from spirv-tools.

Ah, right.
Thinking about it offline, I guess the problem is that the exit pseudo node isn't connected to the loop node, but should be (directly or indirectly). I think we only connect the exit node to nodes that end with OpReturn and others that don't end in branches? If so this might just need a "reachable-in-reverse" concept from an exit node.

from spirv-tools.

Yes, that's the problem. When trying to do the intersection of the dominators of predecessors to a given node, we go through the "predecessors". But one of the predecessors in the post-dom calculation is not reachable from the pseudo-exit node, even in the augmented CFG. So we end up dereferencing idoms[] which default-constructs a block_detail struct and that gives us a dominator member of 0 and a postorder_index member of 0 and so finger1 and finger2 are garbage.

Earlier your code had the "must be reachable" condition when selecting a predecessor to look at (initializing the "res" variable), but I removed it when I switched the algorithm over to the "augmented CFG". That's a mistake.

from spirv-tools.

Looking at this further, I can cause the infinite loop in the forward flow / dominator calculation with the following input:

               OpCapability Shader
               OpMemoryModel Logical GLSL450
       %void = OpTypeVoid
          %2 = OpTypeFunction %void
       %bool = OpTypeBool
          %4 = OpConstantFalse %bool
          %5 = OpFunction %void None %2
          %6 = OpLabel
               OpReturn
          %7 = OpLabel
               OpLoopMerge %8 %9 None
               OpBranch %9
          %9 = OpLabel
               OpBranchConditional %4 %7 %8
          %8 = OpLabel
               OpReturn
               OpFunctionEnd

In this case every block after the entry block is unreachable. And block %8 ends in an OpReturn, so it gets on the predecessor list of the pseudo-exit block even though it is never visited in the DFS.

I'll think on a solution. Either we need to include the reachability test in the selection of the next predecessor to process, or somehow add extra edges from/to the pseudo-entry/pseudo-exit nodes to ensure the postorder traversal reaches all the basic blocks.

from spirv-tools.

oh kay. Where are we:

• I changed the dominance calculation to use an "augmented CFG" because I wanted to be able to calculated dominance relations even among nodes that are unreachable. For example, I want this for things like #276 I still want that.
• To be able to do that, it is sufficient if the DFS used in dominance calculations to visit all the nodes in the CFG. And so we add a pseudo-entry node to connect to the entry block, and any disconnected part of the CFG. (Analogous for pseudo-exit node)
• But the pseudo-entry node only points to nodes without predecessors, and the pseudo-exit node is pointed to by nodes without successors.
• But even when defined this way, the augmented CFG can still have isolated clusters of nodes in strongly connected components. That's a clue. This is not a problem as long as these clusters are not reachable by either the pseudo-entry or pseudo-exit nodes.
• The problem comes when we have a structure in this augmented CFG which is reachable from one end but not the other. That's what's causing the infinite loops. In the first case posted above, the postdom calculation fails because there's a cluster of nodes reachable from the pseudo-entry node but not the pseudo-exit node. In the second case posted above, there's a cluster of nodes reachable from the psuedo-exit node but not the pseudo-entry node.
• Given that I want to have dominators and postdominators across all nodes in the graph, I have to fix the successor/predecessor lists to the pseudo-entry and pseudo-exit nodes so that each node in the regular CFG is reachable from both ends of the augmented CFG.
• SO I think the fix is to compute those succ/pred lists more carefully in libspirv::Function::RegisterFunctionEnd

from spirv-tools.