Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Transform JuvixReg into SSA form #2560

Closed
lukaszcz opened this issue Dec 10, 2023 · 0 comments · Fixed by #2646
Closed

Transform JuvixReg into SSA form #2560

lukaszcz opened this issue Dec 10, 2023 · 0 comments · Fixed by #2646
Assignees
Milestone

Comments

@lukaszcz
Copy link
Collaborator

lukaszcz commented Dec 10, 2023

  • Implement a transformation of JuvixReg into SSA form.
  • Needed for the translation to Cairo Assembly
  • Since there are no loops within a single function, SSA can be computed by going forward in the code of a function and keeping a map from old variables to new variables, updating the map at each assignment.
  • In JuvixReg, variables are divided into two groups (VarGroup in Reg.Language): VarGroupArgs and VarGroupLocal. Within each group the variables are indexed by integers. The indices need to be recomputed so that each variable is assigned at most once. Variables in VarGroupArgs are never assigned, so we need to consider only local variables (VarGroupLocal).
  • Variables are assigned by instructions which have the _instr*Result field (the field specifies the variable to which the result is assigned).
  • All branches in InstrBranch and InstrCase must assign consistent variable indices to variables live after the instruction (used afterwards). It can be assumed that the top of the value stack is the only live variable assigned in each branch. Perhaps one needs to store the information about the index of the top of the value stack after a branching instruction when translating from JuvixAsm to JuvixReg.
  • Remember to update the live variable information stored in instructions.
@lukaszcz lukaszcz added this to the 0.6.0 milestone Dec 10, 2023
@lukaszcz lukaszcz self-assigned this Feb 12, 2024
lukaszcz added a commit that referenced this issue Feb 20, 2024
* Closes #2560 
* Adds a transformation of JuvixReg into SSA form.
* Adds an "output variable" field to branching instructions (`Case`,
`Branch`) which indicates the output variable to which the result is
assigned in both branches. The output variable corresponds to top of
stack in JuvixAsm after executing the branches. In the SSA
transformation, differently renamed output variables are unified by
inserting assignment instructions at the end of branches.
* Adds tests for the SSA transformation.
* Depends on #2641.
janmasrovira pushed a commit that referenced this issue Feb 20, 2024
* Closes #2560 
* Adds a transformation of JuvixReg into SSA form.
* Adds an "output variable" field to branching instructions (`Case`,
`Branch`) which indicates the output variable to which the result is
assigned in both branches. The output variable corresponds to top of
stack in JuvixAsm after executing the branches. In the SSA
transformation, differently renamed output variables are unified by
inserting assignment instructions at the end of branches.
* Adds tests for the SSA transformation.
* Depends on #2641.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant