internal/gen: generated code doesn't allow aliasing #129
Labels
bug
Something isn't working
Comments
|
Aside: reminds me of this mmcloughlin/ec3#83. The EFD contains lots of examples of formulas that don't work under aliasing. The logic to fix up those formulas was pretty gnarly. https://github.com/mmcloughlin/ec3/blob/3948e750fa5e745b6f160c22d5b8fab3dc6436e7/efd/op3/alias.go Thankfully in this case it should be much easier. |
This was referenced Oct 31, 2021
mmcloughlin
added a commit
that referenced
this issue
Nov 1, 2021
Updates the variable allocator to handle the case where the input and output are aliased, that is they refer to the same underlying object. The change to the allocator itself is relatively small, but accompanied with an extended suite of property-based allocation tests run on randomly generated programs: * every operand has a name * names used are exactly: input, output, temporaries * input not written to * input and output not live at same time (required for aliasing) * live operands have unique names * executing the program gives the right result To support these tests two new packages were added: * acc/eval: interpreter for acc programs based on variable names * acc/rand: random generator for acc programs As a final integration test, the fp25519 example now contains a test for aliased execution. Updates #129
Merged
mmcloughlin
added a commit
that referenced
this issue
Nov 2, 2021
The variable allocator currently raises an assertion error if it encounters a write to an operand without an allocation. Allocation is done like liveness analysis: the instructions are processed in reverse and variables are allocated as they are read, freed when they're written to. Therefore this assertion would trigger if the operand is never read after it's written. Therefore, this would only happen for a _redundant_ chain which computes a value it never needs. Clearly this isn't ideal, but it does seem to happen for some algorithms. It seems best that the allocator doesn't crash in these cases. This PR updates the allocation logic to handle this case. In practice if this happens the variable would be immediately allocated and freed. Updates #129 #133 #136
mmcloughlin
added a commit
that referenced
this issue
Nov 2, 2021
Adds an integration test designed to confirm we can produce correct code for all the target exponents in the results list. Specifically, for every target exponent and every algorithm in the ensemble, we confirm the resulting chain can be converted to an addition chain program, allocated variables, and interpreted to give the expected result. This test makes use of the new test execution timer added in #135, so it will only execute tests for the exponents it has time for. Updates #129
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For example, the first two operations of a P-521 chain are
which will break if z = x.
The text was updated successfully, but these errors were encountered: