Notes/future work - Githubissues

Some notes I wrote this morning. Not really an issue, but I don't know where else to put it.

Future work, in no particular order:

Register allocation for user-specified variables and the temporary objects. Should have an option for classical vs qubit RA, because these should happen at very different stages of the compilation process.
The mapper should be decomposed into sub-passes.
The mapper must be made control-flow aware, with SWAP gate networks to make mappings consistent between (sub)blocks.
All the old passes must either be updated or be replaced with new implementations to use the new IR. In the end, ir/new_to_old.cc should become dead code.
Creation of a pass that optimizes control-flow after structure decomposition, with at least the following tasks:
- dead code removal;
- collapsing empty blocks that only contain a goto; and
- block reordering to avoid unnecessary unconditional goto instructions.
Creation of a CC-specific pass that ensures validity of instruction conditions (after structure decomposition) and fixes them if need be. Assuming that cregs map to ALU registers and bregs map to shared memory:
- goto instruction conditions may only use ALU registers, so any bregs used must first be fetched from shared memory;
- quantum gate conditions may only use one or two bregs with a supported boolean operation, anything more complex must be if-converted;
- classical gate conditions are not supported, so these must be if-converted.
Specification of functions and their instruction decomposition in the platform. Currently old_to_new just makes something up w.r.t. functions according to what CC-light/the old IR supported, and doesn't populate any of the instruction decomposition IR nodes.
Creation of a function/expression decomposition pass based on the above information. That is, a pass that converts expression trees to instructions operating on registers, introducing temporary objects for intermediate values.
Creation of passes for expression optimization:
- things like !(a == b) --> a != b and !!a --> a;
- constant propagation (libqasm only does trivial things that it knows about during semantic analysis, and of course not even this runs after decompositions make a mess of things);
- common subexpression elimitation;
- etc.
Ability to specify available data types and registers in the platform. Currently old_to_new just infers qubit q[num_qubit], int32 creg[num_cregs], bit breg[num_bregs - num_qubits], and a real data type for gate angles, but all this is completely generalized in the new IR (and the passes I wrote should support the full range of what the new IR supports).
ir::BlockBase needs a way to specify the duration of the block explicitly, or alternatively the final "skip" must be implicit. Right now this is inferred from when all instructions in it complete (see ir::get_duration_of_block()), but this prevents inter-block scheduling from being possible, and also makes things weird in structure decomposition (I think the schedule should remain valid, but it's creating skips that I don't fully understand, and any skip between a control-flow statement and the instruction before it is lost because in the resulting basic-block form it cannot be represented/is inferred).
There is now a ql.compile() function in the API that takes a cQASM file and infers everything from that (including platform via an annotation in the file). There is no explicit test for it, but it's used by test_structure_decomposition (for example usage). The logical next (and final) step in making the API an optional thing is making the qutechopenql module executable, with some command-line parsing for setting global and pass options, optional explicit specification of the platform/compiler configuration files, and/or explicit insertion of passes.

Suggested eventual pass list for CC:

High-level circuit optimization if desirable at some point.
dec.Instructions to decompose higher-level gates like CNOTs and SWAPs into CZ.
Register allocation for qubit variables and temporaries/ancillas, if used explicitly or in gate decompositions of some kind.
Mapping and circuit optimization if desirable at some point.
Low-level circuit optimization if desirable at some point.
sch.ListSchedule (resource-constrained quantum circuit scheduling).
dec.Instructions to decompose CZs into single-qubit parking and flux gates.
Optionally, there can be a CC-specific pass here that already converts the quantum gates to sequencer instructions, or this can be postponed to code generation at the end.

(only classical stuff from here on, circuit schedule must remain intact)
dec.Structure to decompose structured control-flow into basic block form.
CC-specific instruction condition validation/converstion (see above).
dec.Structure to decompose if blocks generated by the above if conversion logic (the conditions here should already be correct).
Control-flow optimization for the blocks created by the above.
Expression optimization (things like !(a == b) and such).
Decomposition of functions into instructions.
Common subexpression elimination.
Register allocation for classical variables and temporaries.
CC-specific code generation

Hi,

I would like this to be part somehow of the repository!

Groet,

Hans van Someren

Op 15 jul. 2021 om 18:11 heeft jvanstraten @.***> het volgende geschreven:

Some notes I wrote this morning. Not really an issue, but I don't know where else to put it.

Future work, in no particular order:

Register allocation for user-specified variables and the temporary objects. Should have an option for classical vs qubit RA, because these should happen at very different stages of the compilation process.
The mapper should be decomposed into sub-passes.
The mapper must be made control-flow aware, with SWAP gate networks to make mappings consistent between (sub)blocks.
All the old passes must either be updated or be replaced with new implementations to use the new IR. In the end, ir/new_to_old.cc should become dead code.
Creation of a pass that optimizes control-flow after structure decomposition, with at least the following tasks:
- dead code removal;
- collapsing empty blocks that only contain a goto; and
- block reordering to avoid unnecessary unconditional goto instructions.
Creation of a CC-specific pass that ensures validity of instruction conditions (after structure decomposition) and fixes them if need be. Assuming that cregs map to ALU registers and bregs map to shared memory:
- goto instruction conditions may only use ALU registers, so any bregs used must first be fetched from shared memory;
- quantum gate conditions may only use one or two bregs with a supported boolean operation, anything more complex must be if-converted;
- classical gate conditions are not supported, so these must be if-converted.
Specification of functions and their instruction decomposition in the platform. Currently old_to_new just makes something up w.r.t. functions according to what CC-light/the old IR supported, and doesn't populate any of the instruction decomposition IR nodes.
Creation of a function/expression decomposition pass based on the above information. That is, a pass that converts expression trees to instructions operating on registers, introducing temporary objects for intermediate values.
Creation of passes for expression optimization:
- things like !(a == b) --> a != b and !!a --> a;
- constant propagation (libqasm only does trivial things that it knows about during semantic analysis, and of course not even this runs after decompositions make a mess of things);
- common subexpression elimitation;
- etc.
Ability to specify available data types and registers in the platform. Currently old_to_new just infers qubit q[num_qubit], int32 creg[num_cregs], bit breg[num_bregs - num_qubits], and a real data type for gate angles, but all this is completely generalized in the new IR (and the passes I wrote should support the full range of what the new IR supports).
ir::BlockBase needs a way to specify the duration of the block explicitly, or alternatively the final "skip" must be implicit. Right now this is inferred from when all instructions in it complete (see ir::get_duration_of_block()), but this prevents inter-block scheduling from being possible, and also makes things weird in structure decomposition (I think the schedule should remain valid, but it's creating skips that I don't fully understand, and any skip between a control-flow statement and the instruction before it is lost because in the resulting basic-block form it cannot be represented/is inferred).
There is now a ql.compile() function in the API that takes a cQASM file and infers everything from that (including platform via an annotation in the file). There is no explicit test for it, but it's used by test_structure_decomposition (for example usage). The logical next (and final) step in making the API an optional thing is making the qutechopenql module executable, with some command-line parsing for setting global and pass options, optional explicit specification of the platform/compiler configuration files, and/or explicit insertion of passes.

Suggested eventual pass list for CC:

High-level circuit optimization if desirable at some point.
dec.Instructions to decompose higher-level gates like CNOTs and SWAPs into CZ.
Register allocation for qubit variables and temporaries/ancillas, if used explicitly or in gate decompositions of some kind.
Mapping and circuit optimization if desirable at some point.
Low-level circuit optimization if desirable at some point.
sch.ListSchedule (resource-constrained quantum circuit scheduling).
dec.Instructions to decompose CZs into single-qubit parking and flux gates.
Optionally, there can be a CC-specific pass here that already converts the quantum gates to sequencer instructions, or this can be postponed to code generation at the end.

(only classical stuff from here on, circuit schedule must remain intact)

dec.Structure to decompose structured control-flow into basic block form.
CC-specific instruction condition validation/converstion (see above).
dec.Structure to decompose if blocks generated by the above if conversion logic (the conditions here should already be correct).
Control-flow optimization for the blocks created by the above.
Expression optimization (things like !(a == b) and such).
Decomposition of functions into instructions.
Common subexpression elimination.
Register allocation for classical variables and temporaries.
CC-specific code generation

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_QE-2DLab_OpenQL_issues_424&d=DwMCaQ&c=XYzUhXBD2cD-CornpT4QE19xOJBbRy-TBPLK0X9U2o8&r=kNdT9ewT6pQdYFkBLR_5-ZqsrSTk7k5Hdd7MSC_Vnzg&m=fzm3ndE9hTYvoq85pR451A1WFYCwP0gMsEpa8q3I9LE&s=StdF9u9IbZZzj9tFamCZbA4UOU6I1if0EhHp5CYi_VM&e=, or unsubscribehttps://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_notifications_unsubscribe-2Dauth_AEDTBNUDJYBBKG5VFZBHM7DTX4CDXANCNFSM5AN3YHHA&d=DwMCaQ&c=XYzUhXBD2cD-CornpT4QE19xOJBbRy-TBPLK0X9U2o8&r=kNdT9ewT6pQdYFkBLR_5-ZqsrSTk7k5Hdd7MSC_Vnzg&m=fzm3ndE9hTYvoq85pR451A1WFYCwP0gMsEpa8q3I9LE&s=Uvc2vDDpV-uWAxGSKbdRviq9PdDICQ5FfaR0iMAWp2E&e=.

QuTech-Delft / OpenQL

Notes/future work #424