Skip to content
Snippets Groups Projects

vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.

Merged Francisco Casas requested to merge fcasas/vkd3d:copyprop_loop into master

copy_propagation_transform_object_load() currently retrieves true, which indicates that there was progress, even if the input dereference remains the same.

This can happen repeatedly if an uninitialized object is copied onto itself, as in the tests added in this patch. This results on the compilation getting stuck on an endless loop.

This patch checks if the deref didn't change, to retrieve false in that case.

Merge request reports

Loading
Loading

Activity

Filter activity
  • Approvals
  • Assignees & reviewers
  • Comments (from bots)
  • Comments (from users)
  • Commits & branches
  • Edits
  • Labels
  • Lock status
  • Mentions
  • Merge request status
  • Tracking
  • Francisco Casas mentioned in merge request !54 (merged)

    mentioned in merge request !54 (merged)

  • added 1 commit

    • 4f700f83 - vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.

    Compare with previous version

    • I have several immediate thoughts on this:

      (1) Q: Why does this only affect object loads? A: Because only object loads grab the deref directly instead of just referring to the LOAD instruction. Q: But don't regular loads have the same problem? A: No, because a sequence like

      2: var 3: var = @2 4: var

      gets turned into

      ... 4: @2

      (modulo replicate swizzle, which I think we have a pass to remove), and we can't ever turn that back into "4: var" because var was written in the previous instruction.

      In theory the same restriction should be what's preventing object loads from being affected, but that's not really feasible, is it...

      Still, we should have tests for that case. We should also have tests for assignment-to-self where swizzles are involved, probably including both swizzles that have "loops" (e.g. "var.xy = var.xz") and those that don't (e.g. "var.xy = var.yx").

      I also feel like there's some way that we should be able to remember why this only matters for object loads. Maybe we can write a code comment to the effect of the above. But it's also possible that we should be handling this not in copy_propagation_transform_object_load() but rather in copy_propagation_record_store(), even though that requires peeking at the RHS. Not sure about that one.

      (2) We're going to need to get rid of these assignments anyway, though. Consider the last test, which still fails—I assume because we're left with object load/stores in the IR and we can't translate those to sm4.

      So I'd advocate for doing this in a pass before copy-prop. We don't actually need copy-prop to achieve it, we just want to look for stores whose rhs is a load from the same variable.

      We could leave an "assert(!hlsl_derefs_are_equal())" in copy-prop though.

      (3) Why does that test require sm5? For that matter, can't we write it so that it uses a sample rather than a load, and that way it can work on sm1 as well.

    • Author Developer

      (1) Q: Why does this only affect object loads? A: Because only object loads grab the deref directly instead of just referring to the LOAD instruction. Q: But don't regular loads have the same problem? A: No, because a sequence like

      2: var 3: var = @2 4: var

      gets turned into

      ... 4: @2 (modulo replicate swizzle, which I think we have a pass to remove), and we can't ever turn that back into "4: var" because var was written in the previous instruction.

      Yes, regular loads only return "true" if the instruction itself is removed and srcs to it are replaced, and since the number of instructions is finite, this can only happen a finite number of times. The swizzle created by copy_propagation_transform_load() is indeed removed by the remove_trivial_swizzles() pass, if it is trivial.

      In theory the same restriction should be what's preventing object loads from being affected, but that's not really feasible, is it...

      Object loads don't replace the instruction itself and instead just seek for replacements for their inner derefs, and sometimes these replacement derefs can be the same deref (albeit, naturally coming from a different instruction).

      Still, we should have tests for that case. We should also have tests for assignment-to-self where swizzles are involved, probably including both swizzles that have "loops" (e.g. "var.xy = var.xz") and those that don't (e.g. "var.xy = var.yx").

      Okay, I will add some on another branch where I am working with swizzles.

      I also feel like there's some way that we should be able to remember why this only matters for object loads. Maybe we can write a code comment to the effect of the above. But it's also possible that we should be handling this not in copy_propagation_transform_object_load() but rather in copy_propagation_record_store(), even though that requires peeking at the RHS. Not sure about that one.

      Okay, I will add a comment. Hmm, I can't think of a simple way of solving this in copy_propagation_record_store(), but maybe I haven't thought it enough.

      (2) We're going to need to get rid of these assignments anyway, though. Consider the last test, which still fails—I assume because we're left with object load/stores in the IR and we can't translate those to sm4.

      The endless loop seems to happen when there are uninitialized objects such as in the first test (or in the second test for now, because we are lacking more support for object components) because copy-prop indeed can't get rid of these assignments.

      If a shader ends up with references to uninitialized objects it should not compile, but we can only check for those after copy propagation (or we will get false positives), in the validate_static_object_references pass.

      The last test fails for now because it also requires more support for object components; when this patch is added on top of my master6 branch the test passes.

      (3) Why does that test require sm5? For that matter, can't we write it so that it uses a sample rather than a load, and that way it can work on sm1 as well.

      Only sm >= 5 supports objects as struct members, so I decided to use Load to save it from defining a sampler.

    • Author Developer

      Oh sorry, I skipped this part:

      So I'd advocate for doing this in a pass before copy-prop. We don't actually need copy-prop to achieve it, we just want to look for stores whose rhs is a load from the same variable.

      Yes, but I am not sure yet if self-assignments are the only way in which the derefs can be equal. The solution proposed by Giovanni could also do the trick if non-static object references are also a requirement for this problem.

      We could leave an "assert(!hlsl_derefs_are_equal())" in copy-prop though.

      Yes, it would make sense to do this if we use that approach.

    • (2) We're going to need to get rid of these assignments anyway, though. Consider the last test, which still fails—I assume because we're left with object load/stores in the IR and we can't translate those to sm4.

      The endless loop seems to happen when there are uninitialized objects such as in the first test (or in the second test for now, because we are lacking more support for object components) because copy-prop indeed can't get rid of these assignments.

      Eh, right... I guess the way we do copy-prop we're probably not going to end up running into this case unless the object was never initialized? I don't feel comfortable that's always going to be true, though, and I don't like depending on that in the future.

    • Please register or sign in to reply
    • I don't think that checking for variable identity is the right thing to do, it feels more a workaround for the symptom. The underlying issue seems to me that object variables actually come in two types: the real uniform object, that is split in a dedicated pass, and all the other object variables that behave rather as pointers to the real objects. The HLSL language is rather terrible when it conflates these two concepts, which is the reason why we need the splitting pass. Here we just have to acknowledge the same distinction: it makes sense to propagate a load from an object variable when that variable is a real object, i.e., a uniform variable.

      In other words, I'd rather fix this bug using:

          if (!load->src.var->is_uniform)
          {
              TRACE("Ignoring load from non-uniform object variable %s\n", load->src.var->name);
              return false;
          }

      in copy_propagation_transform_object_load(), instead of checking for variable identity.

    • Author Developer

      After giving it some thought, I think this is an elegant solution!

    • Author Developer

      This made me realize we probably want to check for the variables being uniform in validate_static_object_references(), so that the first test passes and we don't reach: Aborting due to not yet implemented feature: Load from non-uniform resource variable. or Aborting due to not yet implemented feature: Object copy. and the first tests fails correctly with an hlsl_error() instead of an hlsl_fixme().

    • I'm afraid I disagree with this analysis quite strongly. While we can do copy-prop this way, there's fundamentally no reason why we can't copy-prop from a temporary object variable, making this code look questionable already. Worse, I think it's a lot less clear why this prevents an infinite loop, compared to Francisco's initial approach.

    • In my understanding, the fundamental reason why we cannot propagate from a temporary object is that temporary objects do not really exist. They are just a static kind of pointer. The only objects that exist really, AFAIU the language, are those represented by a uniform variable (which is later given a register type and number). All other object variables must be resolved at compilation time to a uniform object, or the program is to be rejected. From this point of view the thing that is meaningful to track is the underlying real uniform object, and once you adopt this point of view the bug just isn't there any more.

      Actually, that would probably be an argument for moving the !is_uniform check to copy_propagation_record_store(). The copy propagation tables themselves should contain no record of a store coming from a temporary object variable, for the reason above.

      Suspecting that you won't agree with me anyway, I guess you're the one to decide, and I agree that solving the bug in the way I don't like is still better than not solving it at all.

    • In my understanding, the fundamental reason why we cannot propagate from a temporary object is that temporary objects do not really exist. They are just a static kind of pointer. The only objects that exist really, AFAIU the language, are those represented by a uniform variable (which is later given a register type and number). All other object variables must be resolved at compilation time to a uniform object, or the program is to be rejected. From this point of view the thing that is meaningful to track is the underlying real uniform object, and once you adopt this point of view the bug just isn't there any more.

      Well... eh. From my perspective, there's nothing fundamentally wrong with saying that temporary objects exist. We have an obligation to get rid of them all by the time we're emitting SM1 or SM4, but that's just a restriction of the byte code. If we had a format that could deal with temporary objects—like, say, SM6, which we'll probably emit one of these days!—that whole axiom would go out the window.

      Suspecting that you won't agree with me anyway, I guess you're the one to decide, and I agree that solving the bug in the way I don't like is still better than not solving it at all.

      I'm sorry, I don't mean to frustrate by arguing. Plus, in general, if there's a disagreement I'd rather resolve it before putting my foot down—or, failing that, to at least understand the disagreement, and ideally reduce it down to a stylistic preference.

    • Author Developer

      Alright, the possibility of temporary objects in SM6 argument is good enough.

      If it wasn't for it I would be more inclined for Giovanni's approach, albeit, I suspect that adding the !is_uniform check on copy_propagation_record_store() would preempt some static references to be resolved.

      I will revert to the previous approach.

    • Please register or sign in to reply
  • Francisco Casas added 3 commits

    added 3 commits

    • f8c17c4b - vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.
    • 37ec87f1 - tests: Test uninitialized object references.
    • baec250e - vkd3d-shader/hlsl: Validate that referenced objects are uniform.

    Compare with previous version

  • Author Developer

    The new version avoids infinite loops using Giovanni's solution, and also validates that object references are uniform.

  • Giovanni Mascellani approved this merge request

    approved this merge request

    • Code looks fine, though your commit message says "This patch preempts this by avoiding propagating object loads when the variable is a real object (i.e., a uniform variable) which cannot have a replacement", while unless I am missing something the opposite is true: object loads are propagated only when coming from an uniform object.

    • Author Developer

      Oh, right, that is a typo. I just fixed it.

    • Please register or sign in to reply
  • Francisco Casas added 3 commits

    added 3 commits

    • 4767e000 - vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.
    • 71ce8679 - tests: Test uninitialized object references.
    • 19966563 - vkd3d-shader/hlsl: Validate that referenced objects are uniform.

    Compare with previous version

  • Francisco Casas added 3 commits

    added 3 commits

    • 4f700f83 - vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.
    • 10830798 - tests: Test uninitialized object references.
    • 2080073b - vkd3d-shader/hlsl: Validate that referenced objects are uniform.

    Compare with previous version

  • Francisco Casas added 22 commits

    added 22 commits

    • 2080073b...3fbe2726 - 19 commits from branch wine:master
    • 0cfcbdb3 - vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.
    • 90722020 - tests: Test uninitialized object references.
    • b59457d7 - vkd3d-shader/hlsl: Validate that referenced objects are uniform.

    Compare with previous version

  • Author Developer

    Rebased on top of master.

    It is worth noting that the last patch currently conflicts with !54 (merged)'s patch

    vkd3d-shader/hlsl: Validate that non-uniform objects are not referenced.
  • Giovanni Mascellani unapproved this merge request

    unapproved this merge request

  • Author Developer

    Update:

    As we discussed on IRC, the bug that this MR tries to solve is a symptom of a more severe underlying problem in copy-propagation, specifically, the use and replace of hlsl_derefs in copy_propagation_transform_object_load().

    Zeb pointed out this problem and suggested the following example (with a, b, and c objects):

    a = b;
    b = c;
    ret = Tex2D(a);

    were if ret = Tex2D(a); gets replaced into ret = Tex2D(b); before copy-prop replaces b with its uniform copy, it could happen that the third line ends up as text2D(c).

    This actually happens using the master branch to compile the following shader:

    Texture2D t_good, t_bad;
    
    float4 main() : sv_target
    {
        Texture2D a, b[1];
    
        // This is basically a `b[0] = t_good` but so that the copy-prop is delayed
        int4 co = {0, 0, 0, 0};
        b[(int) co.x + (int) co.y] = t_good;
    
        a = b[0];
        b[0] = t_bad;
        return a.Load(int3(0, 0, 0));
    }

    were t_bad is loaded instead of t_good.

    So probably Giovanni's solution, with some modifications, is the correct solution (as comparing deref shouldn't be solving this underlying issue).

  • Francisco Casas added 51 commits

    added 51 commits

    • b59457d7...d14f42be - 49 commits from branch wine:master
    • 49113823 - tests: Test correct copy-prop object replacement.
    • e0c275d7 - vkd3d-shader/hlsl: Avoid infinite loop in copy propagation.

    Compare with previous version

  • Author Developer

    Giovanni's solution again, which consists in only allowing to replace derefs if they point to a uniform variable.

    I added the tgood/tbad test and it passes it, but the recently merged !51 (merged) was required.

    For simplicity I will send the uninitialized object references tests in another MR.

    • This really deserves an explanation in the code.

      Note also that what makes this work is not so much that the load src is uniform (and hence "real") but that it's constant. In fact, more broadly, we can safely copy-prop an object load if the load var doesn't change between the prior load and this resource instruction. We don't have the infrastructure right now to do that with all variables (we could if we wanted to, but it's probably not worthwhile—doing it with uniforms alone should probably be enough?)

      We could, hence, check for HLSL_MODIFIER_CONST on the variable instead of is_uniform. That would, notably, require that we create uniforms with a constant data type, which we don't currently. I dunno if it's worth changing that yet, but there is a bit of a "least surprise" element here.

    • This really deserves an explanation in the code.

      Yes, a comment is not a bad idea here.

      Note also that what makes this work is not so much that the load src is uniform (and hence "real") but that it's constant. In fact, more broadly, we can safely copy-prop an object load if the load var doesn't change between the prior load and this resource instruction. We don't have the infrastructure right now to do that with all variables (we could if we wanted to, but it's probably not worthwhile—doing it with uniforms alone should probably be enough?)

      I think I agree, but this feels more subtle (for example, you have to be sure of what happens when you have a constant object initialized to a mutable one, which is later mutated, and be sure that the right thing happens). So I would avoid it until we have an indication that is required for feature parity with native.

      OTOH, I think that the current implementation is still somewhat problematic. I couldn't write an actual failing example, but I am concerned by something like:

      a = b;
      b = c;
      d = a;

      Here d is supposed to be equal to the uniform b, but if you skip the first load of b during the first pass you end up pointing to the uniform c, in basically the same way as Zeb's example. I don't think this MR fixed that, because it is only concerned with object loads (and there there aren't). So either you do the check also for "regular" loads, or (better, I think) you don't even store a non-uniform object in the copy propagation state, with something like this patch (on top of this MR):

      diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c
      index fa96ca4b..bab17c21 100644
      --- a/libs/vkd3d-shader/hlsl_codegen.c
      +++ b/libs/vkd3d-shader/hlsl_codegen.c
      @@ -927,12 +927,6 @@ static bool copy_propagation_transform_object_load(struct hlsl_ctx *ctx,
           /* Only HLSL_IR_LOAD can produce an object. */
           load = hlsl_ir_load(value->node);
       
      -    if (!load->src.var->is_uniform)
      -    {
      -        TRACE("Ignoring load from non-uniform object variable %s\n", load->src.var->name);
      -        return false;
      -    }
      -
           hlsl_cleanup_deref(deref);
           hlsl_copy_deref(ctx, deref, &load->src);
       
      @@ -975,7 +969,20 @@ static void copy_propagation_record_store(struct hlsl_ctx *ctx, struct hlsl_ir_s
               unsigned int writemask = store->writemask;
       
               if (store->rhs.node->data_type->type == HLSL_CLASS_OBJECT)
      +        {
      +            struct hlsl_ir_load *load;
      +
                   writemask = VKD3DSP_WRITEMASK_0;
      +
      +            /* Only HLSL_IR_LOAD can produce an object. */
      +            load = hlsl_ir_load(store->rhs.node);
      +            if (!load->src.var->is_uniform)
      +            {
      +                TRACE("Ignoring store of non-uniform object variable %s\n", load->src.var->name);
      +                copy_propagation_invalidate_variable_from_deref(ctx, var_def, lhs, store->writemask);
      +                return;
      +            }
      +        }
               copy_propagation_set_value(var_def, start, writemask, store->rhs.node);
           }
           else
    • Author Developer

      I don't think the problem is currently happening with regular stores/loads, because when we do a replacement, we are removing the whole instruction (and replacing all subsequent references to it), so there is not the possibility of copy-prop doing an incorrect replacement for the instruction being replaced a second time.

      Writing directly

      a = b;
      b = c;
      d = a;

      could be misleading, since on regular stores what we have on the rhs is an hlsl_src, a reference to another node, so it would be more accurate to write it as:

      1 : load (b)
      2 : a = @1;
      3 : load (c)
      4 : b = @3;
      5 : load (a)
      6 : d = @5;

      which would be transformed to

      1 : load (b)
      2 : a = @1;
      3 : load (c)
      4 : b = @3;
      5 : <deleted>
      6 : d = @1;
    • Yes, you're right, I got confused.

    • Please register or sign in to reply
  • Note also that what makes this work is not so much that the load src is uniform (and hence "real") but that it's constant. In fact, more broadly, we can safely copy-prop an object load if the load var doesn't change between the prior load and this resource instruction. We don't have the infrastructure right now to do that with all variables (we could if we wanted to, but it's probably not worthwhile—doing it with uniforms alone should probably be enough?)

    I think I agree, but this feels more subtle (for example, you have to be sure of what happens when you have a constant object initialized to a mutable one, which is later mutated, and be sure that the right thing happens). So I would avoid it until we have an indication that is required for feature parity with native.

    I think we can probably assume that variables act like variables and not pointers ;-)

    OTOH, I think that the current implementation is still somewhat problematic. I couldn't write an actual failing example, but I am concerned by something like:

    Normal variables work fine, because what we're propagating is not the hlsl_deref but the hlsl_ir_load instruction pointer. That is, we're propagating an SSA pointer to a load that happened at a previous point in time.

    Object loads in resource instructions are special and require this patch, because they shortcut the hlsl_ir_load instruction and use the hlsl_deref directly.

  • added 1 commit

    • f2f8fb04 - vkd3d-shader/hlsl: Avoid infinite loop and invalid derefs in copy-prop.

    Compare with previous version

  • Author Developer

    Added explanatory comment. Does it look good?

  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
Please register or sign in to reply
Loading