GCC Code Coverage Report

Directory: ./
File: Transformations/PhaseOptimisation.cpp
Date: 2022-10-15 05:10:18
Warnings: 4 unchecked decisions!
Exec Total Coverage
Lines: 112 116 96.6%
Functions: 5 6 83.3%
Branches: 131 216 60.6%
Decisions: 21 32 65.6%
Line Branch Decision Exec Source
1 // Copyright 2019-2022 Cambridge Quantum Computing
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "PhaseOptimisation.hpp"
16
17 #include "Transform.hpp"
18
19 namespace tket {
20
21 namespace Transforms {
22
23 static void recursive_smash_CX_PhaseGadgets(
24 Circuit &circ, Vertex &vert, VertexList &bin, bool &success);
25
26 13 Transform smash_CX_PhaseGadgets() {
27 13 return Transform([](Circuit &circ) {
28 13 bool success = false;
29 13 VertexList bin;
30
7/8
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 336 times.
✓ Branch 6 taken 13 times.
✓ Branch 8 taken 336 times.
✓ Branch 9 taken 13 times.
✓ Branch 11 taken 13 times.
✓ Branch 12 taken 13 times.
 362 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
31
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 recursive_smash_CX_PhaseGadgets(circ, v, bin, success);
32 }
33
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 circ.remove_vertices(
34 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
35 13 return success;
36
1/2
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
 26 });
37 }
38
39 336 static void recursive_smash_CX_PhaseGadgets(
40 Circuit &circ, Vertex &vert, VertexList &bin, bool &success) {
41
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 317 times.
2/2
✓ Decision 'true' taken 121 times.
✓ Decision 'false' taken 215 times.
 336 if (circ.get_OpType_from_Vertex(vert) == OpType::PhaseGadget) {
42
3/4
✓ Branch 1 taken 121 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 102 times.
✓ Branch 4 taken 19 times.
0/1
? Decision couldn't be analyzed.
 121 for (unsigned e = 0; e < circ.n_in_edges(vert); e++) {
43
1/2
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.
 102 Edge in_e = circ.get_nth_in_edge(vert, e);
44
1/2
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.
 102 Edge out_e = circ.get_nth_out_edge(vert, e);
45
1/2
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.
 102 Vertex prev_vert = circ.source(in_e);
46
5/6
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
✓ Branch 4 taken 70 times.
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 70 times.
2/2
✓ Decision 'true' taken 32 times.
✓ Decision 'false' taken 102 times.
 134 if (circ.get_OpType_from_Vertex(prev_vert) == OpType::CX &&
47
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
 32 circ.get_source_port(in_e) == 1) {
48
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 Vertex next_vert = circ.target(out_e);
49
5/6
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 31 times.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 30 times.
✓ Branch 6 taken 2 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 33 times.
 63 if (circ.get_OpType_from_Vertex(next_vert) == OpType::CX &&
50
3/4
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 30 times.
✓ Branch 4 taken 1 times.
 31 circ.get_target_port(out_e) == 1) {
51
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 Edge linker = circ.get_nth_in_edge(next_vert, 0);
52
4/6
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 29 times.
✓ Branch 7 taken 1 times.
2/2
✓ Decision 'true' taken 29 times.
✓ Decision 'false' taken 1 times.
 30 if (linker == circ.get_nth_out_edge(prev_vert, 0)) {
53 29 success = true;
54
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 circ.remove_edge(linker);
55
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 port_t new_port = circ.n_in_edges(vert);
56
1/2
✓ Branch 3 taken 29 times.
✗ Branch 4 not taken.
 29 circ.add_edge({prev_vert, 0}, {vert, new_port}, EdgeType::Quantum);
57
1/2
✓ Branch 3 taken 29 times.
✗ Branch 4 not taken.
 29 circ.add_edge({vert, new_port}, {next_vert, 0}, EdgeType::Quantum);
58
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 29 VertexList to_detach = {prev_vert, next_vert};
59
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 bin.push_back(prev_vert);
60
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 bin.push_back(next_vert);
61
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 circ.remove_vertices(
62 to_detach, Circuit::GraphRewiring::Yes,
63 Circuit::VertexDeletion::No);
64 29 e--; // continue to add any more from the current port
65 29 }
66 }
67 }
68 }
69 // Fix up the qubit count for the phase gadget we inserted.
70 std::vector<Expr> v_params =
71
2/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 19 times.
✗ Branch 6 not taken.
 19 circ.get_Op_ptr_from_Vertex(vert)->get_params();
72
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 circ.dag[vert].op =
73
2/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
 38 get_op_ptr(OpType::PhaseGadget, v_params, circ.n_in_edges(vert));
74 19 }
75 336 }
76
77 8 static bool align_phases_all(Circuit &circ) {
78 8 bool success = false;
79 8 VertexList bin;
80
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 VertexVec vertices = circ.vertices_in_order();
81
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 auto index = boost::get(boost::vertex_index, circ.dag);
82
2/2
✓ Branch 5 taken 214 times.
✓ Branch 6 taken 8 times.
2/2
✓ Decision 'true' taken 214 times.
✓ Decision 'false' taken 8 times.
 222 for (const Vertex &v : vertices) {
83
3/4
✓ Branch 1 taken 214 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 198 times.
2/2
✓ Decision 'true' taken 16 times.
✓ Decision 'false' taken 198 times.
 214 if (circ.get_OpType_from_Vertex(v) == OpType::PhaseGadget) {
84 std::map<Vertex, std::map<port_t, port_t>>
85 16 parent_to_port_map; // maps ports on initial phase to ports on each
86 // parent
87
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 EdgeVec i_edges = circ.get_in_edges(v);
88 16 unsigned n_qubits = i_edges.size();
89
2/2
✓ Branch 4 taken 61 times.
✓ Branch 5 taken 16 times.
2/2
✓ Decision 'true' taken 61 times.
✓ Decision 'false' taken 16 times.
 77 for (EdgeVec::iterator e = i_edges.begin(); e != i_edges.end(); ++e) {
90 61 Edge ed = *e;
91 61 Vertex source = boost::source(ed, circ.dag);
92
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 OpType type = circ.get_OpType_from_Vertex(source);
93
7/8
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 31 times.
✓ Branch 3 taken 123 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 93 times.
✓ Branch 6 taken 30 times.
✓ Branch 7 taken 93 times.
✓ Branch 8 taken 61 times.
0/1
? Decision couldn't be analyzed.
 154 while (!(type == OpType::PhaseGadget || is_initial_q_type(type))) {
94
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 ed = circ.get_last_edge(source, ed);
95 93 source = boost::source(ed, circ.dag);
96
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 type = circ.get_OpType_from_Vertex(source);
97 }
98
7/10
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 31 times.
✓ Branch 4 taken 30 times.
✓ Branch 6 taken 31 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 31 times.
✓ Branch 10 taken 30 times.
✓ Branch 11 taken 31 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 31 times.
 61 if (is_initial_q_type(type) || circ.get_source_port(ed) > n_qubits) {
99 30 continue;
100 }
101 std::map<Vertex, std::map<port_t, port_t>>::iterator par =
102
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 parent_to_port_map.find(source);
103
2/2
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 23 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 23 times.
 31 if (par == parent_to_port_map.end()) {
104 8 std::map<port_t, port_t> port_map;
105
3/6
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
 8 port_map.insert({circ.get_target_port(*e), circ.get_source_port(ed)});
106
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 parent_to_port_map.insert({source, port_map});
107 8 } else {
108
1/2
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
 46 par->second.insert(
109
2/4
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
 46 {circ.get_target_port(*e), circ.get_source_port(ed)});
110 }
111 }
112 // build replacement as disconnected graph
113
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 Circuit phase_replacement;
114 16 std::map<port_t, Vertex> port_to_input;
115 16 std::map<port_t, Vertex> port_to_output;
116 16 std::map<port_t, bool> port_remaining;
117
2/2
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 16 times.
2/2
✓ Decision 'true' taken 61 times.
✓ Decision 'false' taken 16 times.
 77 for (port_t p = 0; p < n_qubits; p++) {
118
1/2
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
 61 Vertex in = phase_replacement.add_vertex(OpType::Input);
119
1/2
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
 61 Vertex out = phase_replacement.add_vertex(OpType::Output);
120
2/4
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 61 times.
✗ Branch 6 not taken.
 61 phase_replacement.boundary.insert({Qubit(p), in, out});
121
1/2
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
 61 port_to_input.insert({p, in});
122
1/2
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
 61 port_to_output.insert({p, out});
123
1/2
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
 61 port_remaining.insert({p, true});
124 }
125
1/2
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 32 Vertex gadget = phase_replacement.add_vertex(
126
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 phase_replacement.get_Op_ptr_from_Vertex(v));
127 // collect incoming edges by parent and add where preference is possible
128 typedef std::function<bool(
129 std::pair<Vertex, std::map<port_t, port_t>>,
130 std::pair<Vertex, std::map<port_t, port_t>>)>
131 Comp;
132 std::set<std::pair<Vertex, std::map<port_t, port_t>>, Comp> sorted_p2p(
133 parent_to_port_map.begin(), parent_to_port_map.end(),
134 ✗ [&](std::pair<Vertex, std::map<port_t, port_t>> const &a,
135 std::pair<Vertex, std::map<port_t, port_t>> const &b) {
136
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (a.second.size() == b.second.size()) {
137 ✗ return index[a.first] < index[b.first];
138 }
139 ✗ return a.second.size() > b.second.size();
140
1/2
✓ Branch 5 taken 16 times.
✗ Branch 6 not taken.
 32 });
141
3/4
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 8 times.
✓ Branch 9 taken 16 times.
0/1
? Decision couldn't be analyzed.
 24 for (std::pair<Vertex, std::map<port_t, port_t>> par : sorted_p2p) {
142 8 for (std::map<port_t, port_t>::iterator port_pair = par.second.begin();
143
2/2
✓ Branch 3 taken 31 times.
✓ Branch 4 taken 8 times.
 39 port_pair != par.second.end(); ++port_pair) {
144
2/4
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 31 times.
✗ Branch 5 not taken.
1/2
✓ Decision 'true' taken 31 times.
✗ Decision 'false' not taken.
 31 if (port_remaining[port_pair->second]) {
145
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 phase_replacement.add_edge(
146
1/2
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
 31 {port_to_input[port_pair->first], 0},
147 31 {gadget, port_pair->second}, EdgeType::Quantum);
148
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 phase_replacement.add_edge(
149 31 {gadget, port_pair->second},
150
1/2
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
 31 {port_to_output[port_pair->first], 0}, EdgeType::Quantum);
151
1/2
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
 31 port_remaining[port_pair->second] = false;
152
1/2
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
 31 port_to_input.erase(port_pair->first);
153 }
154 }
155 8 }
156 // add edges for remaining ports
157 16 port_t spare_port = 0;
158 16 for (std::map<port_t, Vertex>::iterator in = port_to_input.begin();
159
2/2
✓ Branch 2 taken 30 times.
✓ Branch 3 taken 16 times.
 46 in != port_to_input.end(); ++in) {
160
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 30 times.
0/1
? Decision couldn't be analyzed.
 30 while (!port_remaining[spare_port]) spare_port++;
161
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 phase_replacement.add_edge(
162 30 {in->second, 0}, {gadget, spare_port}, EdgeType::Quantum);
163
1/2
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 30 phase_replacement.add_edge(
164
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 {gadget, spare_port}, {port_to_output[in->first], 0},
165 30 EdgeType::Quantum);
166 30 spare_port++;
167 }
168 // substitute into circuit
169 Subcircuit sub = {
170
4/8
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 16 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 16 times.
✗ Branch 12 not taken.
 32 {circ.get_in_edges(v)}, {circ.get_all_out_edges(v)}, {v}};
171
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 bin.push_back(v);
172
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 circ.substitute(phase_replacement, sub, Circuit::VertexDeletion::No);
173 16 success = true;
174 16 }
175 }
176
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 circ.remove_vertices(
177 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
178 8 return success;
179 8 }
180
181
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 Transform align_PhaseGadgets() { return Transform(align_phases_all); }
182
183 } // namespace Transforms
184
185 } // namespace tket
186