[naga] PendingArraySize::Expression breaks compaction

[jimblandy]

The introduction of PendingArraySize in #6654 didn't adequately update the compaction algorithm, making it possible for unused expressions and types to leak. I'm not sure this is a problem in practice, but the algorithm is definitely wrong now.

PendingArraySize was introduced to correctly model WGSL's rules around array type equivalence. WGSL treats arrays differently depending on whether their lengths are const expressions, override expressions consisting of a single identifier, or more general override expressions. In light of WGSL's requirements, PendingArraySize seems like the right way to represent modules.

However, the introduction of PendingArraySize::Expression was the first time that types could refer to expressions. Expressions can refer to types in a few ways, too. This means that it is possible to have cycles between Module::types and Module::global_expressions. The compaction algorithm previously assumed that such cycles were impossible, allowing one to first decide which expressions were used, and then retain the types that those expressions needed. But once cycles are possible, expression and type liveness need to be considered simultaneously.

The way to see that things have definitely gone awry is to look at the following code added to compact::compact (link):

for (_, ty) in module.types.iter() {
    if let crate::TypeInner::Array {
        size: crate::ArraySize::Pending(crate::PendingArraySize::Expression(size_expr)),
        ..
    } = ty.inner
    {
        module_tracer.global_expressions_used.insert(size_expr);
    }
}

This essentially treats all PendingArraySize::Expression handles as live by assumption, meaning that they'll be retained even if the override-sized array type itself is unused. This is a leak.

Any fix will somehow entail traversing global expressions and types together, which is a pretty big change, unfortunately.

This probably has implications for handle validation as well: the check_dep code wants to ensure our arena contents are acyclic.

cc @teoxoy @kentslaney

[kentslaney]

Should we be rolling back #6654? I don't know the git commands off the top of my head

[jimblandy]

@kentslaney I don't think we need to roll it back. This isn't a show-stopper, it's just something we should deal with.

[kentslaney]

ok, I'll look into this

[teoxoy]

Any fix will somehow entail traversing global expressions and types together, which is a pretty big change, unfortunately.

Yeah this sounds like the way to go. I tried making things better without understanding the full requirements today (for #6787) and ultimately my attempt didn't work.

[teoxoy]

I wonder if we can get away with saying that no expression can refer to an override-sized array and check this in the validator.

[jimblandy]

This probably has implications for handle validation as well: the check_dep code wants to ensure our arena contents are acyclic.

I filed #6793 for this validation issue.

[jimblandy]

I wonder if we can get away with saying that no expression can refer to an override-sized array and check this in the validator.

This would require not just checking the Handle<Type>s that appear in Expression variants, but the types those types refer to. But since override-sized arrays can't be used in many contexts (@kentslaney added the CREATION_RESOLVED flag to check this), we could just assume that they don't appear deeper in the type.

But one of the principles of the validator is that handle validation runs first, so that the rest of the validator can just assume that whatever handles it runs into are okay. We used to sort of check handles in the midst of everything else, and of course we forgot to do it all the time.

Being cycle-free, well, I'm not positive where this guarantee is taken advantage of. But assuming the absence of cycles where they might actually be present is an absolutely classic kind of bug, in every variety of programming, and I think this shows that people sort of generally don't anticipate cycles, whether they should know better or not. So I think it's good for handle validation to just settle the question once and for all, to allow rest of the validator to be naive and common-sensey.

And I think that means that we shouldn't be depending on type validation to establish the absence of cycles.

[kentslaney]

Thanks for your patience, I took yesterday mostly off. Just to read back my current understanding:

This is resolved from a practical standpoint by the two compacting passes already in the code base. In the first one, the override-sized array type gets removed for not being used and in the second the expression gets removed for not being used. I don't think there's anything that's nested more than that.

The issue is that the current compacting setup orders the tracing based on a one-directional dependency assumption that's no longer true. Ideally, the example given should be solved in a single pass.

The other issue is caused by the same problem, but has different implications. Practically, we know the variants don't have any bidirectional dependancies since types can't be used in array size override expressions. That being said, we should validate that they're acyclic anyway since this is the most obvious time something has changed and it's a convenient guarantee.

[jimblandy]

Oh, no problem - it's great to have someone contributing to this area, I think most people are scared off. 😀

The issue is that the current compacting setup orders the tracing based on a one-directional dependency assumption that's no longer true. Ideally, the example given should be solved in a single pass.

Right. In #6800 I changed handle validation to check Module::types and Module::global_expressions in a single pass. Compaction tracing would need to do something similar, but in reverse. I have to admit that #6800 was tricky for me (hence all the comments), so I think a similar change to compaction will be even more challenging.

(Calling something "challenging" makes it sound like a good thing; "error-prone" might be more honest.)

[kentslaney]

I've only skimmed your #6800 solution, but you're right, it sounds similar to my current thinking for this issue. My current plan for this one, using the guarantee of cycle-free arenas to avoid stack overflow:

1. have two pointers walk down the reversed type/expression arenas
2. starting with type, arbitrarily: (if the type under the pointer is marked as used or 3 called) and it points to an expression...
   a. in front of the expression pointer: mark it as used
   b. behind the expression pointer: trace the expressions forwards until it's in front of the expression pointer while marking expressions as used; for any types used along the way and not already marked as used, recurse to 3.
3. flipped, copy/pasted: (if the expression under the pointer is marked as used or 2 called) and it points to a type...
   a. in front of the type pointer: mark it as used
   b. behind the type pointer: trace the types forwards until it's in front of the type pointer while marking expressions as used; for any types used along the way and not already marked as used, recurse to 2.
4. repeat from 2 until both pointers are done iterating

We can simplify this if we assume that the expressions are well ordered since they're not merged like types are (ie. expression A referring to a type referring to expression B has A > B). A similar assumption is made in naga/src/compact/expressions.rs.

1. for any type marked as used, mark its expressions as used
2. for any expression marked as used and referencing a type, walk the type's dependency tree, marking the types and their referenced expressions as used

┌───────────┐ ┌───────────┐
│Expressions│ │   Types   │
│           │ │           │
│        covered by │     │
│          step 1   │     │
│      ◄────┬─┬─────┘     │
│           │ │           │
│           │ │           │
│     │  covered by       │
│     │    step 2         │
│     └─────┬─┬────►│     │
│           │ │     │     │
│      ◄────┼─┼─────┘     │
│           │ │           │
└───────────┘ └───────────┘