Skip to content
Snippets Groups Projects

Loop unrolling, part 2 (conditional jumps).

Merged Victor Chiletto requested to merge vitorhnn/vkd3d:loop-unrolling-pt2-submit into master

The idea is to substitute break and continue with stores to broken and continued variables, and to move all instructions after these jumps to if (!broken) and if (!continued) checks. continued gets reset after each iteration, and we check broken after each iteration to stop early if it's been set to true.

Some notes:

Copy prop parent state chaining is used to "emulate" something like this:

if (!broken)
{
    // ...loop parts go here.
    if (!broken)
    {
        // another loop iteration goes here.
    }
}

while keeping if nesting to a minimum:

if (!broken)
{
    // ...one iteration.
}
if (!broken)
{
    // another iteration.
    // since its copy prop state parent is the previous iteration
    // to copy prop, this is as if it was nested inside the previous iteration
}

Unrolling with conditionals needs each loop part to be split, mostly because for loops with continues are very annoying:

// from for.shader_test
[unroll] for (i = 0; i < 10; i++)
{
    x += i;
    if (tex > 0.5 && i == 5)
        break;
    if (tex > -0.5 && i >= 7)
        continue;
    x -= 1;
}

Since neither d3dbc nor tpf have jumps, our way of compiling continues is to copy the loop iter block (in this example, i++) to before each continue; in pseudo-IR:

loop
{
    if (!(i < 10))
    {
        break;
    }

    x += 1;

    if (tex > 0.5 && i == 5)
    {
        break;
    }
    if (tex > -0.5 && i >= 7)
    {
        i++;
        continue;
    }
    x -= 1;
    i++;
}

This doesn't work for unrolling, because i gets invalidated in the branch, and therefore its value doesn't get substituted in future iterations of the loop.

What unrolling does instead is to push the iter block to the beginning of the next iteration. We can't do this without splitting each loop block off, which I've decided to do with a separate node type which later gets resolved to our current loop nodes if the loop isn't unrolled.


3/8 is required as otherwise copy prop would invalidate all variables that are modified in the loop. !748 (closed) worked around this by copying all instructions from the head of the loop's parent block to the loop itself and applying copy prop to these instructions, which is incorrect for loops nested inside other blocks with loop induction variables set outside their parent blocks (see the example below)


2/8 and 3/8 are required because of shaders like:

float a : register(c0);

float4 main() : sv_target
{
    int i = 0;
    if (a > 0)
    {
        [unroll]
        for (; i < 10; ++i);

        return float4(i, a, 2.0, 3.0);
    }

    return float4(0.0, a, 3.0, 4.0);
}

Without 2/8, once copy prop is stopped at the loop node we would lose all the copy prop state as the stack unwinds.


Prior discussions at !748 (closed) and !786 (merged).

Edited by Victor Chiletto

Merge request reports

Merge request pipeline #35844 skipped

Merge request pipeline skipped for ed6061df

Merged by Henri VerbeetHenri Verbeet 4 months ago (Dec 12, 2024 4:47pm 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
  • Victor Chiletto changed the description

    changed the description

  • Does "unresolved loop" need to be a whole separate IR type?

    Do we need to store the cond separately, or just the iter? As I understand the whole problem is basically that unrolling has special awareness of blocks that are uniformly executed at loop end, whose uniformity we lose knowledge of if we convert them early. But that doesn't mean we need the separate cond, does it?

    • The thing I dislike about this is the index (time) manipulation. This is necessary for copy-prop and it's essentially why I wrote that comment.

      I assume the index manipulation here works, but it's not easy to read and it feels fragile. What I'd like to see is copy-prop (and really anything that's going to modify the instruction stream) stop depending on index manipulation.

      That means we need a different solution for !487 (merged). This is hard.

      • One idea is to keep track of per-component states per load instruction. This is not terrible, but the fundamental problem that you're dealing with pointers in the instruction stream but can also change the instruction stream is unfortunate.

      • Another idea, which I just had and I'm not actually sure I hate, is... move the swizzles to just after the load instructions. This is legal because of SSA, and by moving we guarantee for copy-prop's sake that we can just reach through the swizzle the way we did before !487 (merged).

      • Along the same lines, when encountering a load we could look through the "uses" list at that point in time for swizzles. This would require extending hlsl_src to also contain a back-pointer to the containing node, but that seems reasonable and wouldn't be difficult.

      This is probably something that I'll have to attack after this patch is upstream. I'd like to hear Francisco and Giovanni's thoughts though.

      The other big ask I have is that it'd be nice to arrange this a bit differently, basically like:

      • incrementally save state
      • then get rid of the clone / find_unrollable_loop()
      • then delay resolving loops
      • then add conditional jump support

      I can live with reviewing this patch series as-is though.

    • Author Contributor

      I've rearranged the commits as suggested.

    • Please register or sign in to reply
  • Victor Chiletto added 474 commits

    added 474 commits

    • fc222aed...8a3fe9cd - 467 commits from branch wine:master
    • 47c86487 - vkd3d-shader/hlsl: Explicitly track the copy propagation state stack.
    • a8faaadf - vkd3d-shader/hlsl: Allow copy propagation to be stopped early.
    • 0973a586 - vkd3d-shader/hlsl: Run copy prop incrementally during loop unrolling.
    • ac645284 - vkd3d-shader/hlsl: Do not clone the entire program for loop unrolling.
    • b68a1c17 - vkd3d-shader/hlsl: Remove loop_unrolling_find_unrollable_loop.
    • 6192c69f - vkd3d-shader/hlsl: Partially defer continue resolution.
    • 0e18a86b - vkd3d-shader/hlsl: Unroll loops with conditional jumps.

    Compare with previous version

  • Francisco Casas requested review from @fcasas

    requested review from @fcasas

  • Francisco Casas
  • Francisco Casas
  • Francisco Casas
  • Francisco Casas
  • Francisco Casas
    • Resolved by Victor Chiletto

      I have spent about a day reviewing this and so far I have only inspected in detail from 1/7 to 5/7, even though I left a couple of superficial comments for 6/7 and 7/7.

      The changes from 1/7 to 5/7 look good to me, even if they only provide performance benefits on their own. It will take me some more time to understand 6/7 and 7/7 and have an opinion about those, but since these patches are quite dense, my opinion is that these should be moved to a part 3.

      Edited by Francisco Casas
  • Francisco Casas removed review request for @fcasas

    removed review request for @fcasas

  • Victor Chiletto added 190 commits

    added 190 commits

    • 0e18a86b...e3838340 - 183 commits from branch wine:master
    • 3d0921ea - vkd3d-shader/hlsl: Explicitly track the copy propagation state stack.
    • 096eed65 - vkd3d-shader/hlsl: Allow copy propagation to be stopped early.
    • d2f75050 - vkd3d-shader/hlsl: Run copy prop incrementally during loop unrolling.
    • 9cce8787 - vkd3d-shader/hlsl: Do not clone the entire program for loop unrolling.
    • d7aa65e1 - vkd3d-shader/hlsl: Remove loop_unrolling_find_unrollable_loop.
    • 049ecb8a - vkd3d-shader/hlsl: Partially defer continue resolution.
    • 04deab1b - vkd3d-shader/hlsl: Unroll loops with conditional jumps.

    Compare with previous version

  • Francisco Casas
  • Victor Chiletto added 70 commits

    added 70 commits

    • 04deab1b...9619582d - 63 commits from branch wine:master
    • 416c75c2 - vkd3d-shader/hlsl: Explicitly track the copy propagation state stack.
    • d7017738 - vkd3d-shader/hlsl: Allow copy propagation to be stopped early.
    • a6d7f1b9 - vkd3d-shader/hlsl: Run copy prop incrementally during loop unrolling.
    • ed8711de - vkd3d-shader/hlsl: Do not clone the entire program for loop unrolling.
    • 32a92747 - vkd3d-shader/hlsl: Remove loop_unrolling_find_unrollable_loop.
    • 59b33fed - vkd3d-shader/hlsl: Partially defer continue resolution.
    • 62fda182 - vkd3d-shader/hlsl: Unroll loops with conditional jumps.

    Compare with previous version

  • Francisco Casas approved this merge request

    approved this merge request

  • Elizabeth Figura
    Elizabeth Figura @zfigura started a thread on an outdated change in commit a6d7f1b9
  • 6457 6457 lower_ir(ctx, lower_index_loads, body);
    6458 6458 }
    6459 6459
    6460 void hlsl_run_const_passes(struct hlsl_ctx *ctx, struct hlsl_block *body)
    6460 static void run_const_passes_with_state(struct hlsl_ctx *ctx, struct hlsl_block *block,
    6461 struct copy_propagation_state *state, unsigned int *index)
    6461 6462 {
    6463 unsigned int current_index;
    6464 size_t scopes_depth;
    6462 6465 bool progress;
    6463 6466
    6464 lower_ir(ctx, lower_matrix_swizzles, body);
    6467 lower_ir(ctx, lower_matrix_swizzles, block);
    • We should put more thought into what passes really need to be run as part of this function, and especially what passes really need to be run on every iteration of a loop.

      Lowering passes don't. Lowering passes are only ever done once. We do need at least some for evaluating static expressions (at least, I think? This deserves some investigation) but we shouldn't need them to be run every iteration of loop unrolling. Splitting (which is a form of lowering) also shouldn't be repeated.

      In fact, I'd be tempted to even go as far as to run only what we need—or what we can write tests to prove we need—in order to save processing time. It's probably not too hard to prove that all of these "folding" passes should be included in the set.

      [Also a tangential thought: should we combine all of our lowering passes together à la vsir_program_lower_instructions()?]

    • Oh, it seems we had contradictory opinions here. I asked Victor to make passes go through this single function so that we don't have to put more thought on which passes need to be run for loop unrolling and static evaluation and which don't.

      !1053 (comment 87499)

      My point of view is that running passes that are not necessary shouldn't be very expensive (less so compared with copy-prop), since they would just go through the code in linear time without touching anything, and that sounded like a good price to pay to avoid having to test for every pass if it is necessary in loop unrolling or not, and to avoid having to remember to check for this every time we introduce/modify a pass.

      Edited by Francisco Casas
    • I'm not going to take for granted that any compiler pass is cheap. I haven't done any benchmarking, but typically it's the sort of thing that more highly developed compilers care about, so I'm inclined to be more cautious.

      Perhaps moreover it's a matter of declarativity here. We should do what we actually need to do here, which is folding so that we can properly determine when a loop is broken early—and not anything else.

    • Victor Chiletto changed this line in version 5 of the diff

      changed this line in version 5 of the diff

    • Author Contributor

      I've changed this back to loop_unrolling_simplify and reduced the passes to just copy prop + constant folding.

    • Please register or sign in to reply
  • Elizabeth Figura
    Elizabeth Figura @zfigura started a thread on an outdated change in commit a6d7f1b9
  • 9619 9647 struct hlsl_block tmp_dst, *jump_block;
    9620 9648 struct hlsl_ir_jump *jump = NULL;
    9621 9649
    9650 copy_propagation_push_scope(ctx, &state);
    9651
    9622 9652 if (!hlsl_clone_block(ctx, &tmp_dst, &loop->body))
    9623 return false;
    9624 list_move_before(&loop->node.entry, &tmp_dst.instrs);
    9625 hlsl_block_cleanup(&tmp_dst);
    9653 goto fail;
    9626 9654
    9627 hlsl_run_const_passes(ctx, block);
    9655 run_const_passes_with_state(ctx, &tmp_dst, &state, &index);
    9628 9656
    9629 if ((jump = loop_unrolling_find_jump(loop_parent, &loop->node, &jump_block)))
    9657 if ((jump = loop_unrolling_find_jump(&tmp_dst, &jump_block)))
    • Comment on lines -9629 to +9657

      It isn't worth splitting at this point, but, if I understand correctly, this is an independent fix, right? We should have been looking for a jump in the loop body in the first place, not in the whole (cloned) program? Or is there some reason we need this to be tied to this commit that I'm not noticing?

    • Author Contributor

      This didn't search the entire program previously, just the block that contains the loop, but still, the reason it doesn't search the loop body is that there is no loop body as it unrolled directly into the loop's parent block.

    • This didn't search the entire program previously, just the block that contains the loop,

      Sure, but that block could have a jump in a different, unrelated loop, that's not part of this one.

      Oh wait, no, it couldn't, because we don't descend into loops. Right.

      (Side note: what we do need to do, that we don't do currently, is look for a continue (but not a break!) inside of a switch. It's currently broken and I think this patch series doesn't make it worse, but it'd be good to fix sooner than later.)

      but still, the reason it doesn't search the loop body is that there is no loop body as it unrolled directly into the loop's parent block.

      Right, okay.

    • Author Contributor

      (Side note: what we do need to do, that we don't do currently, is look for a continue (but not a break!) inside of a switch. It's currently broken and I think this patch series doesn't make it worse, but it'd be good to fix sooner than later.)

      As we've discussed on IRC, prior to SM6 continues weren't allowed inside switches, so we're fine (for now)

    • Please register or sign in to reply
  • Elizabeth Figura
    Elizabeth Figura @zfigura started a thread on an outdated change in commit a6d7f1b9
  • 9633 if (jump_block != loop_parent)
    9662 if (jump_block != &tmp_dst)
    9634 9663 {
    9635 9664 if (loop->unroll_type == HLSL_IR_LOOP_FORCE_UNROLL)
    9636 9665 hlsl_error(ctx, &jump->node.loc, VKD3D_SHADER_ERROR_HLSL_FAILED_FORCED_UNROLL,
    9637 9666 "Unable to unroll loop, unrolling loops with conditional jumps is currently not supported.");
    9638 return false;
    9667 hlsl_block_cleanup(&tmp_dst);
    9668 goto fail;
    9639 9669 }
    9640 9670
    9641 list_move_slice_tail(&tmp_dst.instrs, &jump->node.entry, list_prev(&loop_parent->instrs, &loop->node.entry));
    9642 hlsl_block_cleanup(&tmp_dst);
    9671 hlsl_block_init(&dump);
    9672 list_move_slice_tail(&dump.instrs, &jump->node.entry, list_tail(&tmp_dst.instrs));
    9673 hlsl_block_cleanup(&dump);
    • Comment on lines +9671 to +9673

      Something to put on the non-existent todo list (add a comment?): this isn't really specific to loop unrolling; it's a form of DCE that probably deserves to be more general. (E.g. it affects loops that aren't unrolled.) It probably should either be part of the folding passes we run every iteration (if we can prove it matters) or it should be left off until after unrolling.

      In fact, I say todo, but given the comment below, if we can afford to not worry about deleting these nodes yet, that would be ideal.

    • Author Contributor

      This is just a specialized form of remove_unreachable_code, the difference being that loop unrolling needs to know the type of the unconditional jump to decide if it should stop unrolling or not.

    • Eh, right, we already have that, not sure if I forgot about that or I confused myself.

      Either way, though, do we actually need to worry about deleting these instructions right now? 8/9 removes this code, so I'm not sure I see why it's here...

    • Author Contributor

      Sadly we do, otherwise we can delete entire programs away:

      float4 main() : sv_target
      {
          int i;
          for (i = 0; i < 4; ++i);
      
          i *= 2;
      
          return i;
      }

      becomes

      ps_5_0
      break
      ret

      8/9 handles jumps completely differently, transforming them into branches and relying on copy prop + trivial branch removal, so that's why this code is removed there.

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