Skip to content
Snippets Groups Projects

vkd3d-shader/ir: Introduce a simple CFG structurizer.

Merged Giovanni Mascellani requested to merge giomasce/vkd3d:vesuvio into master

This goes atop !598 (merged) and !603 (merged).

Merge request reports

Merge request pipeline #22122 skipped

Merge request pipeline skipped for 51f13391

Merged by Alexandre JulliardAlexandre Julliard 1 year ago (Feb 6, 2024 10:42pm UTC)

Loading

Activity

Filter activity
  • Approvals
  • Assignees & reviewers
  • Comments (from bots)
  • Comments (from users)
  • Commits & branches
  • Edits
  • Labels
  • Lock status
  • Mentions
  • Merge request status
  • Tracking
  • Giovanni Mascellani changed title from Draft: vkd3d-shader/ir: Introduce a Böhm-Jacopini structurizer. to Draft: vkd3d-shader/ir: Introduce a simple CFG structurizer.

    changed title from Draft: vkd3d-shader/ir: Introduce a Böhm-Jacopini structurizer. to Draft: vkd3d-shader/ir: Introduce a simple CFG structurizer.

  • Conor McCarthy
    Conor McCarthy @cmccarthy started a thread on an outdated change in commit ed8e2b78
2863 2882 return VKD3D_ERROR_OUT_OF_MEMORY;
2864 2883 }
2865 2884
2885 static enum vkd3d_result boehm_jacopini_structurize(struct vkd3d_shader_parser *parser)
2886 {
2887 struct vkd3d_shader_instruction *instructions = NULL;
2888 const struct vkd3d_shader_location no_loc = {0};
2889 size_t ins_capacity = 0, ins_count = 0, i;
2890 unsigned int block_temp_idx = 0;
  • Conor McCarthy
    Conor McCarthy @cmccarthy started a thread on an outdated change in commit ed8e2b78
  • 2950 {
    2951 ERR("Failed to extend instructions.\n");
    2952 goto fail;
    2953 }
    2954
    2955 if (vsir_register_is_label(&ins->src[0].reg))
    2956 {
    2957 if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &no_loc, VKD3DSIH_MOV, 1, 1))
    2958 goto fail;
    2959 dst_param_init_temp_uint(&instructions[ins_count].dst[0], block_temp_idx);
    2960 src_param_init_const_uint(&instructions[ins_count].src[0], label_from_src_param(&ins->src[0]));
    2961 ins_count++;
    2962 }
    2963 else
    2964 {
    2965 if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &no_loc, VKD3DSIH_MOVC, 1, 3))
    • If I understand correctly, this takes the place of phi, and copies to a new temp the result from the branch which was taken. Another way to do this is force the temp dst register indices to be equal in both branches, unless there's an issue with it I'm missing.

    • Mmmh, what you are describing seems more what is happening in materialize_ssa_to_temps(): there SSA registers are converted to TEMP registers, and PHI nodes must be converted to MOV/MOVC because they're not allowed with TEMPs. So in practice that transformation does something like this:

      label l10
      ...
      add sr20, sr18, sr19
      branch l11
      label l11
      phi sr21, l9, sr20, ...
      ...

      is converted to

      label l10
      ...
      add r20, r18, r19
      mov r21, r20
      branch l11
      label l11
      [phi is removed]
      ...

      In other words, not only we're converting PHI to MOV/MOVC, but we're also moving it before than BRANCH (otherwise the predecessor information is lost).

      The structurizer is dispatched after this has already happened, so there are no PHIs nor SSAs in sight. It converts this:

      label l10
      ...
      branch l11

      to something like this:

      # Introduce a fresh TEMP to represent the currently executing block
      r100 = 1
      loop
        switch r100
          ...
          case l(10)
            # Do whatever block l10 is supposed to do
            mov r100, l(11)
          break
          ...
        endswitch
      endloop

      Of course the MOV becomes a MOVC if the BRANCH was conditional. So now the program is structured in the sense of TPF programs, and it can be passed to the CF flattener pass and then to the SPIR-V backend.

    • When I tested materialisation of SSA to TEMP a while ago I didn't use MOVC, so I'm wondering if it's needed only because of the structuriser. For example, this:

      label l1
      ...
      branch sr1, l2, l3
      label l2
      mov sr2, v0.x
      branch l4
      label l3
      mov sr3, v1.x
      branch l4
      label l4
      phi sr5, sr2, l2, sr3, l3

      Becomes:

      label l1
      ...
      branch r0.x, l2, l3
      label l2
      mov r1.x, v0.x
      branch l4
      label l3
      mov r1.x, v1.x
      branch l4
      label l4
    • You need MOVC when there is a conditional BRANCH and the PHI nodes is in one of the two branches, not when it is in the merge block. For example:

      label l1
      ...
      mov sr1, ...
      mov sr2, ...
      branch sr2, l2, l3
      label l2
      phi sr3, sr1, l1, ...
      ...

      In that case, the assignment to r3 (supposedly used to materialize sr3) must be moved to block l1, but must be executed only if control is going to l2. So I convert that to:

      label l1
      ...
      mov r1, ...
      mov r2, ...
      movc r3, r2, r1, r2
      branch r2, l2, l3
      label l2
      ...

      Of course if l3 has PHI nodes too, than I'll have to add MOVC instructions for that as well, this time using the "if false" operands. Does that make sense to you?

    • In that case, can you assign to r3 in l1, then overwrite it later in one flow path but not the other? I suspect this is how phi values are resolved in the hardware, but I haven't looked at the details. Maybe something to consider later, since the current code is fine for testing.

    • I don't know much about how PHI nodes are handled downstream, but I can't assign r3 in l2 or l3, because by the time I'm there I don't know anymore from which block I got control. Here only l1 and l2 are shown, but it is assumed that there are other blocks that jump to l2, otherwise there wouldn't be the need for a PHI node in the first place.

      At any rate, my intention is that this SSA materialization pass should eventually go away, or at least be only used for the few cases in which the CFG structurizer must use a multilevel break to execute a certain BRANCH.

    • Giovanni Mascellani changed this line in version 6 of the diff

      changed this line in version 6 of the diff

    • Please register or sign in to reply
  • Conor McCarthy
    Conor McCarthy @cmccarthy started a thread on an outdated change in commit f9b4535c
  • 2665 if (reg->idx[i].rel_addr)
    2666 materialize_ssa_to_temps_process_src_param(parser, reg->idx[i].rel_addr);
    2667 }
    2668
    2669 static void materialize_ssa_to_temps_process_dst_param(struct vkd3d_shader_parser *parser, struct vkd3d_shader_dst_param *dst)
    2670 {
    2671 materialize_ssa_to_temps_process_reg(parser, &dst->reg);
    2672 }
    2673
    2674 static void materialize_ssa_to_temps_process_src_param(struct vkd3d_shader_parser *parser, struct vkd3d_shader_src_param *src)
    2675 {
    2676 materialize_ssa_to_temps_process_reg(parser, &src->reg);
    2677 }
    2678
    2679 static bool materialize_ssa_to_temps_synthesize_mov(struct vkd3d_shader_parser *parser,
    2680 struct vkd3d_shader_instruction **instructions, size_t *ins_count, const struct vkd3d_shader_location *loc,
    • Given the complexity of dealing with an unstructured instruction array which represents a CFG, it may work out better to use an intermediate flow graph of one object per block. Code for setting pred/succ and modifying the graph exists in the sm6_rebase branch. Doing this would require changes to !598 (merged) though. Code for emitting the blocks is already upstream, so if we are not going to use them, the dxil module should be patched to emit directly into the parser's array.

    • I guess that at some point it might be advisable to have a more structured representation of the code rather than just a flat array. Maybe the vsir_program thing Henri is pushing for could also allow for a blocked representation. Or maybe the blocking information might be additional data to vsir_program. I'm not yet sure of what I like more there, so I'm waiting a little bit to introduce that. Once the simple structurizer is in it might be a good moment to do some experiments in view of a smarter structurizer.

    • Please register or sign in to reply
  • added 2 commits

    • 34268526 - vkd3d-shader/ir: Materialize SSA registers to temporaries.
    • a320fa11 - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

  • added 27 commits

    • a320fa11...fef30dac - 21 commits from branch wine:master
    • 7be2e3d8 - vkd3d-shader/dxil: Set the register before calling src_param_init_scalar().
    • 7480b76f - vkd3d-shader/spirv: Move bool casting helpers above register loading helpers.
    • f8d38520 - vkd3d-shader/spirv: Support bool TEMP registers.
    • d8efceb2 - vkd3d-shader/ir: Materialize SSA registers to temporaries.
    • 1183ab3b - vkd3d-shader/ir: Handle PHI nodes when materializing SSA registers.
    • 1e2c4426 - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

  • Giovanni Mascellani marked this merge request as ready

    marked this merge request as ready

  • Giovanni Mascellani approved this merge request

    approved this merge request

  • Rebased on master. I noticed a little bug in giomasce/vkd3d@1f536238, which is fixed in !607 (7be2e3d8). Other then that I split a couple of commits for better readability and made some minor style changes.

  • Conor McCarthy
  • Conor McCarthy
  • added 4 commits

    • 3f940e79 - vkd3d-shader/spirv: Support bool TEMP registers.
    • ad27a735 - vkd3d-shader/ir: Materialize SSA registers to temporaries.
    • d3c441f9 - vkd3d-shader/ir: Handle PHI nodes when materializing SSA registers.
    • c83e101a - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

  • Conor McCarthy
    Conor McCarthy @cmccarthy started a thread on an outdated change in commit c83e101a
  • 2888 static enum vkd3d_result simple_structurizer_run(struct vkd3d_shader_parser *parser)
    2889 {
    2890 const unsigned int block_temp_idx = parser->program.temp_count;
    2891 struct vkd3d_shader_instruction *instructions = NULL;
    2892 const struct vkd3d_shader_location no_loc = {0};
    2893 size_t ins_capacity = 0, ins_count = 0, i;
    2894 bool first_label_found = false;
    2895
    2896 if (!reserve_instructions(&instructions, &ins_capacity, parser->program.instructions.count))
    2897 goto fail;
    2898
    2899 for (i = 0; i < parser->program.instructions.count; ++i)
    2900 {
    2901 struct vkd3d_shader_instruction *ins = &parser->program.instructions.elements[i];
    2902
    2903 if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 1))
  • Conor McCarthy approved this merge request

    approved this merge request

  • added 1 commit

    • b0c8cfb4 - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

  • added 46 commits

    • b0c8cfb4...06ddb10c - 40 commits from branch wine:master
    • 310c7bb0 - vkd3d-shader/dxil: Set the register before calling src_param_init_scalar().
    • cfd9083d - vkd3d-shader/spirv: Move bool casting helpers above register loading helpers.
    • 3d8c1f3c - vkd3d-shader/spirv: Support bool TEMP registers.
    • 08cbfda6 - vkd3d-shader/ir: Materialize SSA registers to temporaries.
    • 6cd9c782 - vkd3d-shader/ir: Handle PHI nodes when materializing SSA registers.
    • dfe3c88f - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

  • added 7 commits

    • 541e79de - vkd3d-shader/spirv: Convert the swizzle according to the source bit width.
    • bf00c4ad - vkd3d-shader/dxil: Set the register before calling src_param_init_scalar().
    • 86606b23 - vkd3d-shader/spirv: Move bool casting helpers above register loading helpers.
    • cd4b61ff - vkd3d-shader/spirv: Support bool TEMP registers.
    • 73b6627f - vkd3d-shader/ir: Materialize SSA registers to temporaries.
    • 0a66edf9 - vkd3d-shader/ir: Handle PHI nodes when materializing SSA registers.
    • 0c56ae6c - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

  • Giovanni Mascellani mentioned in merge request !628 (closed)

    mentioned in merge request !628 (closed)

  • added 7 commits

    • 3982b49a - vkd3d-shader/dxil: Set the register before calling src_param_init_scalar().
    • f2e77173 - vkd3d-shader/spirv: Convert the swizzle according to the source bit width.
    • 1dd7bf50 - vkd3d-shader/spirv: Move bool casting helpers above register loading helpers.
    • 22bd52f5 - vkd3d-shader/spirv: Support bool TEMP registers.
    • 2c9c7b19 - vkd3d-shader/ir: Materialize SSA registers to temporaries.
    • 369e8a9f - vkd3d-shader/ir: Handle PHI nodes when materializing SSA registers.
    • cd8973f2 - vkd3d-shader/ir: Introduce a simple control flow graph structurizer.

    Compare with previous version

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