This is an archive of the discontinued LLVM Phabricator instance.

[riscv] Use classic dataflow for VSETVLI insertion
ClosedPublic

Authored by reames on May 9 2022, 7:17 AM.

Details

Summary

Our current implementation of the InsertVSETVLI dataflow allows phase 3 to arrive at a different block end state than the data flow in phase 1/2 computed. This arises because a block which contains instructions (e.g. load or stores) which don't consume all the incoming bits of the VL/VTYPE can be compatible with multiple incoming states. The algorithm effectively changes the SEW on such instructions, and propagates the prior state forward. As phase 3 uses the block input state for this propagation, but phase 1/2 doesn't, this can result in different block end states.

If we don't correct for it, this discrepancy can result in miscompiles. This was the source of multiple recent changes. However, by now we have fixes for all known correctness issues.

The basic strategy we use is to insert a compensation vsetvli to bring the block state leaving the block back into consistency with the one computed. This is correct, but results in extra vsetvlis being placed at the end of blocks.

This change adjusts the phase 1/2 algorithm to propagate the incoming block state through the block, allowing the compatibility rules to modify the end state. The algorithm may need to run slightly more iterations, but the end result is consistent with what phase 3 does.

The benefit of doing this is two fold.

First, we reverse some of the code quality introductions introduced in the functional fixes.

Second, we simplify the invariants, and allow the strict assertions to be enabled. Several humans, myself included, have found it quite surprising that invariant didn't hold already, and arguably that confusion is the cause of several of our recent miscompiles in this code.

The downside to this patch is that the dataflow may require additional iterations to stabilize. In the worse case, we go from O(Edges) to O(E + UniquePaths) as the incoming state (and thus the outgoing one) can now change once for each path from the entry block.

A couple notes to reviewers:

  • The majority of the code improvements are simply reversing the regressions from D125703.
  • A prior version of this patch switched from optimistic to conservative data flow. I have dropped that entirely, and don't plan to revisit. It turned out my doing so was accidentally fixing the issue in D125703, and I had not realized that.

Diff Detail

Event Timeline

reames created this revision.May 9 2022, 7:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 9 2022, 7:17 AM
reames requested review of this revision.May 9 2022, 7:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 9 2022, 7:17 AM

Looks decent to me. It overlaps with what I have in D125021 and was playing around with locally, but improves on it nicely. Would be good to hear @craig.topper's and @rogfer01's thoughts if possible.

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp
387

This is the last use of /*Strict*/ true - can we follow up on this and get rid of Strict entirely, which was always a patch job?

973

Unintended new line?

reames added inline comments.May 9 2022, 8:00 AM
llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp
387

Definitely! Hadn't noticed that. Less code is always good. :)

973

Yep, will remove before landing.

reames planned changes to this revision.May 11 2022, 12:12 PM

After staring at some generated code for a while, I'm becoming less sure the switch from optimistic to conservative dataflow in this patch is a good idea. I want to give that some more thought, and try separating out only the re-visit logic.

In the meantime, I posted a tactical fix for a miscompile in the current workaround: https://reviews.llvm.org/D125408

Now that the two mutation bugs (PHI, and scalar op) have landed, I think we're approaching correct. We need the tactical fix just posted, but I think once that lands, this review can be reframed as a code quality issue which no longer influences correctness.

I think we still want something like this. Our other option would be to investigate scheduling corrections at more optimal places. I'm going to give that a bit of thought, but my initial reaction is "yuck".

reames updated this revision to Diff 429762.May 16 2022, 10:36 AM
reames retitled this revision from [riscv] Fix data flow for VSETVLI insertion to [riscv] Use classic dataflow for VSETVLI insertion .
reames edited the summary of this revision. (Show Details)

As of now, most of the functional fixes for this data flow algorithm have landed. (D125703 is the sole outstanding one.) This allows a significant reframing and simplification of the patch, see the new commit description.

reames updated this revision to Diff 429771.May 16 2022, 10:39 AM

Correct a stray whitespace diff.

Is enabling strict asserts going to be a separate patch?

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp
973

Any reason for the new blank line here?

Is enabling strict asserts going to be a separate patch?

D125271

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp
973

Nope, thought I'd killed that in the last update. Will remove.

This revision is now accepted and ready to land.May 16 2022, 2:19 PM
This revision was landed with ongoing or failed builds.May 16 2022, 5:06 PM
This revision was automatically updated to reflect the committed changes.