Comments (8)
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.
Related Issues (20)
- Wrong validation error when using RTA in SPV1.4? HOT 2
- Request: allow SpirvToolsEliminateDeadInputComponents() to strip non-trailing members from blocks HOT 2
- SpirvToolsEliminateDeadInputComponents() doesn't seem to be trimming array size down HOT 1
- spirv-val false positive error HOT 6
- Compilation error in validate_atomics.cpp HOT 2
- Using opt C API makes no change to shader HOT 1
- v2024.1 flatpak build fails: validation_state.cpp error: ‘BlockMatchSamplerQCOM’ is not a member of ‘spv::Decoration’ HOT 2
- How to add a new OpName with DescriptorSet and Binding HOT 2
- spirv-opt fma folding causes large performance degradation on Adreno HOT 6
- how to remove the OpVariable inst??
- Implicit LOD functions can be supported when compute shader derivatives are supported HOT 6
- How to compile on arm platform HOT 3
- Disallows TypeManager::GetId on non unique types
- Slang produces spv that works on win/linux but not with MoltenVk
- Incorrect codegen when there is redundant `float16_t` conversion HOT 1
- spirv-opt: loop unroll pass with shader produces spirv-val failure
- Generator comment in spirv-dis output is failing to look up name from spir-v.xml HOT 5
- Inability to use system versions of dependencies. HOT 1
- spirv-tools build is failing for gcc 12.4 HOT 4
- SPIRV-Tools-toolsTargets.cmake references spirv-objdump but the file does not exist HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from spirv-tools.