GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
cesarzc/ssa-panic

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_codegen/src

compiler/qsc_codegen/src/qir.rs

635lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod instruction_tests;
6
7#[cfg(test)]
8mod tests;
9
10use qsc_data_structures::target::TargetCapabilityFlags;
11use qsc_lowerer::map_hir_package_to_fir;
12use qsc_partial_eval::{partially_evaluate, ProgramEntry};
13use qsc_rca::PackageStoreComputeProperties;
14use qsc_rir::{
15 passes::check_and_transform,
16 rir::{self, ConditionCode},
17 utils::get_all_block_successors,
18};
19
20fn lower_store(package_store: &qsc_frontend::compile::PackageStore) -> qsc_fir::fir::PackageStore {
21 let mut fir_store = qsc_fir::fir::PackageStore::new();
22 for (id, unit) in package_store {
23 let package = qsc_lowerer::Lowerer::new().lower_package(&unit.package);
24 fir_store.insert(map_hir_package_to_fir(id), package);
25 }
26 fir_store
27}
28
29/// converts the given sources to QIR using the given language features.
30pub fn hir_to_qir(
31 package_store: &qsc_frontend::compile::PackageStore,
32 capabilities: TargetCapabilityFlags,
33 compute_properties: Option<PackageStoreComputeProperties>,
34 entry: &ProgramEntry,
35) -> Result<String, qsc_partial_eval::Error> {
36 let fir_store = lower_store(package_store);
37 fir_to_qir(&fir_store, capabilities, compute_properties, entry)
38}
39
40pub fn fir_to_qir(
41 fir_store: &qsc_fir::fir::PackageStore,
42 capabilities: TargetCapabilityFlags,
43 compute_properties: Option<PackageStoreComputeProperties>,
44 entry: &ProgramEntry,
45) -> Result<String, qsc_partial_eval::Error> {
46 let mut program = get_rir_from_compilation(fir_store, compute_properties, entry, capabilities)?;
47 check_and_transform(&mut program);
48 Ok(ToQir::<String>::to_qir(&program, &program))
49}
50
51fn get_rir_from_compilation(
52 fir_store: &qsc_fir::fir::PackageStore,
53 compute_properties: Option<PackageStoreComputeProperties>,
54 entry: &ProgramEntry,
55 capabilities: TargetCapabilityFlags,
56) -> Result<rir::Program, qsc_partial_eval::Error> {
57 let compute_properties = compute_properties.unwrap_or_else(|| {
58 let analyzer = qsc_rca::Analyzer::init(fir_store);
59 analyzer.analyze_all()
60 });
61
62 partially_evaluate(fir_store, &compute_properties, entry, capabilities)
63}
64
65/// A trait for converting a type into QIR of type `T`.
66/// This can be used to generate QIR strings or other representations.
67pub trait ToQir<T> {
68 fn to_qir(&self, program: &rir::Program) -> T;
69}
70
71impl ToQir<String> for rir::Literal {
72 fn to_qir(&self, _program: &rir::Program) -> String {
73 match self {
74 rir::Literal::Bool(b) => format!("i1 {b}"),
75 rir::Literal::Double(d) => {
76 if (d.floor() - d.ceil()).abs() < f64::EPSILON {
77 // The value is a whole number, which requires at least one decimal point
78 // to differentiate it from an integer value.
79 format!("double {d:.1}")
80 } else {
81 format!("double {d}")
82 }
83 }
84 rir::Literal::Integer(i) => format!("i64 {i}"),
85 rir::Literal::Pointer => "i8* null".to_string(),
86 rir::Literal::Qubit(q) => format!("%Qubit* inttoptr (i64 {q} to %Qubit*)"),
87 rir::Literal::Result(r) => format!("%Result* inttoptr (i64 {r} to %Result*)"),
88 }
89 }
90}
91
92impl ToQir<String> for rir::Ty {
93 fn to_qir(&self, _program: &rir::Program) -> String {
94 match self {
95 rir::Ty::Boolean => "i1".to_string(),
96 rir::Ty::Double => "double".to_string(),
97 rir::Ty::Integer => "i64".to_string(),
98 rir::Ty::Pointer => "i8*".to_string(),
99 rir::Ty::Qubit => "%Qubit*".to_string(),
100 rir::Ty::Result => "%Result*".to_string(),
101 }
102 }
103}
104
105impl ToQir<String> for Option<rir::Ty> {
106 fn to_qir(&self, program: &rir::Program) -> String {
107 match self {
108 Some(ty) => ToQir::<String>::to_qir(ty, program),
109 None => "void".to_string(),
110 }
111 }
112}
113
114impl ToQir<String> for rir::VariableId {
115 fn to_qir(&self, _program: &rir::Program) -> String {
116 format!("%var_{}", self.0)
117 }
118}
119
120impl ToQir<String> for rir::Variable {
121 fn to_qir(&self, program: &rir::Program) -> String {
122 format!(
123 "{} {}",
124 ToQir::<String>::to_qir(&self.ty, program),
125 ToQir::<String>::to_qir(&self.variable_id, program)
126 )
127 }
128}
129
130impl ToQir<String> for rir::Operand {
131 fn to_qir(&self, program: &rir::Program) -> String {
132 match self {
133 rir::Operand::Literal(lit) => ToQir::<String>::to_qir(lit, program),
134 rir::Operand::Variable(var) => ToQir::<String>::to_qir(var, program),
135 }
136 }
137}
138
139impl ToQir<String> for rir::ConditionCode {
140 fn to_qir(&self, _program: &rir::Program) -> String {
141 match self {
142 rir::ConditionCode::Eq => "eq".to_string(),
143 rir::ConditionCode::Ne => "ne".to_string(),
144 rir::ConditionCode::Sgt => "sgt".to_string(),
145 rir::ConditionCode::Sge => "sge".to_string(),
146 rir::ConditionCode::Slt => "slt".to_string(),
147 rir::ConditionCode::Sle => "sle".to_string(),
148 }
149 }
150}
151
152impl ToQir<String> for rir::Instruction {
153 fn to_qir(&self, program: &rir::Program) -> String {
154 match self {
155 rir::Instruction::Add(lhs, rhs, variable) => {
156 binop_to_qir("add", lhs, rhs, *variable, program)
157 }
158 rir::Instruction::Ashr(lhs, rhs, variable) => {
159 binop_to_qir("ashr", lhs, rhs, *variable, program)
160 }
161 rir::Instruction::BitwiseAnd(lhs, rhs, variable) => {
162 simple_bitwise_to_qir("and", lhs, rhs, *variable, program)
163 }
164 rir::Instruction::BitwiseNot(value, variable) => {
165 bitwise_not_to_qir(value, *variable, program)
166 }
167 rir::Instruction::BitwiseOr(lhs, rhs, variable) => {
168 simple_bitwise_to_qir("or", lhs, rhs, *variable, program)
169 }
170 rir::Instruction::BitwiseXor(lhs, rhs, variable) => {
171 simple_bitwise_to_qir("xor", lhs, rhs, *variable, program)
172 }
173 rir::Instruction::Branch(cond, true_id, false_id) => {
174 format!(
175 " br {}, label %{}, label %{}",
176 ToQir::<String>::to_qir(cond, program),
177 ToQir::<String>::to_qir(true_id, program),
178 ToQir::<String>::to_qir(false_id, program)
179 )
180 }
181 rir::Instruction::Call(call_id, args, output) => {
182 call_to_qir(args, *call_id, *output, program)
183 }
184 rir::Instruction::LogicalAnd(lhs, rhs, variable) => {
185 logical_binop_to_qir("and", lhs, rhs, *variable, program)
186 }
187 rir::Instruction::LogicalNot(value, variable) => {
188 logical_not_to_qir(value, *variable, program)
189 }
190 rir::Instruction::LogicalOr(lhs, rhs, variable) => {
191 logical_binop_to_qir("or", lhs, rhs, *variable, program)
192 }
193 rir::Instruction::Mul(lhs, rhs, variable) => {
194 binop_to_qir("mul", lhs, rhs, *variable, program)
195 }
196 rir::Instruction::Icmp(op, lhs, rhs, variable) => {
197 icmp_to_qir(*op, lhs, rhs, *variable, program)
198 }
199 rir::Instruction::Jump(block_id) => {
200 format!(" br label %{}", ToQir::<String>::to_qir(block_id, program))
201 }
202 rir::Instruction::Phi(args, variable) => phi_to_qir(args, *variable, program),
203 rir::Instruction::Return => " ret void".to_string(),
204 rir::Instruction::Sdiv(lhs, rhs, variable) => {
205 binop_to_qir("sdiv", lhs, rhs, *variable, program)
206 }
207 rir::Instruction::Shl(lhs, rhs, variable) => {
208 binop_to_qir("shl", lhs, rhs, *variable, program)
209 }
210 rir::Instruction::Srem(lhs, rhs, variable) => {
211 binop_to_qir("srem", lhs, rhs, *variable, program)
212 }
213 rir::Instruction::Store(_, _) => unimplemented!("store should be removed by pass"),
214 rir::Instruction::Sub(lhs, rhs, variable) => {
215 binop_to_qir("sub", lhs, rhs, *variable, program)
216 }
217 }
218 }
219}
220
221fn logical_not_to_qir(
222 value: &rir::Operand,
223 variable: rir::Variable,
224 program: &rir::Program,
225) -> String {
226 let value_ty = get_value_ty(value);
227 let var_ty = get_variable_ty(variable);
228 assert_eq!(
229 value_ty, var_ty,
230 "mismatched input/output types ({value_ty}, {var_ty}) for not"
231 );
232 assert_eq!(var_ty, "i1", "unsupported type {var_ty} for not");
233
234 format!(
235 " {} = xor i1 {}, true",
236 ToQir::<String>::to_qir(&variable.variable_id, program),
237 get_value_as_str(value, program)
238 )
239}
240
241fn logical_binop_to_qir(
242 op: &str,
243 lhs: &rir::Operand,
244 rhs: &rir::Operand,
245 variable: rir::Variable,
246 program: &rir::Program,
247) -> String {
248 let lhs_ty = get_value_ty(lhs);
249 let rhs_ty = get_value_ty(rhs);
250 let var_ty = get_variable_ty(variable);
251 assert_eq!(
252 lhs_ty, rhs_ty,
253 "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
254 );
255 assert_eq!(
256 lhs_ty, var_ty,
257 "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
258 );
259 assert_eq!(var_ty, "i1", "unsupported type {var_ty} for {op}");
260
261 format!(
262 " {} = {op} {var_ty} {}, {}",
263 ToQir::<String>::to_qir(&variable.variable_id, program),
264 get_value_as_str(lhs, program),
265 get_value_as_str(rhs, program)
266 )
267}
268
269fn bitwise_not_to_qir(
270 value: &rir::Operand,
271 variable: rir::Variable,
272 program: &rir::Program,
273) -> String {
274 let value_ty = get_value_ty(value);
275 let var_ty = get_variable_ty(variable);
276 assert_eq!(
277 value_ty, var_ty,
278 "mismatched input/output types ({value_ty}, {var_ty}) for not"
279 );
280 assert_eq!(var_ty, "i64", "unsupported type {var_ty} for not");
281
282 format!(
283 " {} = xor {var_ty} {}, -1",
284 ToQir::<String>::to_qir(&variable.variable_id, program),
285 get_value_as_str(value, program)
286 )
287}
288
289fn call_to_qir(
290 args: &[rir::Operand],
291 call_id: rir::CallableId,
292 output: Option<rir::Variable>,
293 program: &rir::Program,
294) -> String {
295 let args = args
296 .iter()
297 .map(|arg| ToQir::<String>::to_qir(arg, program))
298 .collect::<Vec<_>>()
299 .join(", ");
300 let callable = program.get_callable(call_id);
301 if let Some(output) = output {
302 format!(
303 " {} = call {} @{}({args})",
304 ToQir::<String>::to_qir(&output.variable_id, program),
305 ToQir::<String>::to_qir(&callable.output_type, program),
306 callable.name
307 )
308 } else {
309 format!(
310 " call {} @{}({args})",
311 ToQir::<String>::to_qir(&callable.output_type, program),
312 callable.name
313 )
314 }
315}
316
317fn icmp_to_qir(
318 op: ConditionCode,
319 lhs: &rir::Operand,
320 rhs: &rir::Operand,
321 variable: rir::Variable,
322 program: &rir::Program,
323) -> String {
324 let lhs_ty = get_value_ty(lhs);
325 let rhs_ty = get_value_ty(rhs);
326 let var_ty = get_variable_ty(variable);
327 assert_eq!(
328 lhs_ty, rhs_ty,
329 "mismatched input types ({lhs_ty}, {rhs_ty}) for icmp {op}"
330 );
331
332 assert_eq!(var_ty, "i1", "unsupported output type {var_ty} for icmp");
333 format!(
334 " {} = icmp {} {lhs_ty} {}, {}",
335 ToQir::<String>::to_qir(&variable.variable_id, program),
336 ToQir::<String>::to_qir(&op, program),
337 get_value_as_str(lhs, program),
338 get_value_as_str(rhs, program)
339 )
340}
341
342fn binop_to_qir(
343 op: &str,
344 lhs: &rir::Operand,
345 rhs: &rir::Operand,
346 variable: rir::Variable,
347 program: &rir::Program,
348) -> String {
349 let lhs_ty = get_value_ty(lhs);
350 let rhs_ty = get_value_ty(rhs);
351 let var_ty = get_variable_ty(variable);
352 assert_eq!(
353 lhs_ty, rhs_ty,
354 "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
355 );
356 assert_eq!(
357 lhs_ty, var_ty,
358 "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
359 );
360 assert_eq!(var_ty, "i64", "unsupported type {var_ty} for {op}");
361
362 format!(
363 " {} = {op} {var_ty} {}, {}",
364 ToQir::<String>::to_qir(&variable.variable_id, program),
365 get_value_as_str(lhs, program),
366 get_value_as_str(rhs, program)
367 )
368}
369
370fn simple_bitwise_to_qir(
371 op: &str,
372 lhs: &rir::Operand,
373 rhs: &rir::Operand,
374 variable: rir::Variable,
375 program: &rir::Program,
376) -> String {
377 let lhs_ty = get_value_ty(lhs);
378 let rhs_ty = get_value_ty(rhs);
379 let var_ty = get_variable_ty(variable);
380 assert_eq!(
381 lhs_ty, rhs_ty,
382 "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
383 );
384 assert_eq!(
385 lhs_ty, var_ty,
386 "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
387 );
388 assert_eq!(var_ty, "i64", "unsupported type {var_ty} for {op}");
389
390 format!(
391 " {} = {op} {var_ty} {}, {}",
392 ToQir::<String>::to_qir(&variable.variable_id, program),
393 get_value_as_str(lhs, program),
394 get_value_as_str(rhs, program)
395 )
396}
397
398fn phi_to_qir(
399 args: &[(rir::Operand, rir::BlockId)],
400 variable: rir::Variable,
401 program: &rir::Program,
402) -> String {
403 assert!(
404 !args.is_empty(),
405 "phi instruction should have at least one argument"
406 );
407 let var_ty = get_variable_ty(variable);
408 let args = args
409 .iter()
410 .map(|(arg, block_id)| {
411 let arg_ty = get_value_ty(arg);
412 assert_eq!(
413 arg_ty, var_ty,
414 "mismatched types ({var_ty} [... {arg_ty}]) for phi"
415 );
416 format!(
417 "[{}, %{}]",
418 get_value_as_str(arg, program),
419 ToQir::<String>::to_qir(block_id, program)
420 )
421 })
422 .collect::<Vec<_>>()
423 .join(", ");
424
425 format!(
426 " {} = phi {var_ty} {args}",
427 ToQir::<String>::to_qir(&variable.variable_id, program)
428 )
429}
430
431fn get_value_as_str(value: &rir::Operand, program: &rir::Program) -> String {
432 match value {
433 rir::Operand::Literal(lit) => match lit {
434 rir::Literal::Bool(b) => format!("{b}"),
435 rir::Literal::Double(d) => {
436 if (d.floor() - d.ceil()).abs() < f64::EPSILON {
437 // The value is a whole number, which requires at least one decimal point
438 // to differentiate it from an integer value.
439 format!("{d:.1}")
440 } else {
441 format!("{d}")
442 }
443 }
444 rir::Literal::Integer(i) => format!("{i}"),
445 rir::Literal::Pointer => "null".to_string(),
446 rir::Literal::Qubit(q) => format!("{q}"),
447 rir::Literal::Result(r) => format!("{r}"),
448 },
449 rir::Operand::Variable(var) => ToQir::<String>::to_qir(&var.variable_id, program),
450 }
451}
452
453fn get_value_ty(lhs: &rir::Operand) -> &str {
454 match lhs {
455 rir::Operand::Literal(lit) => match lit {
456 rir::Literal::Integer(_) => "i64",
457 rir::Literal::Bool(_) => "i1",
458 rir::Literal::Double(_) => "f64",
459 rir::Literal::Qubit(_) => "%Qubit*",
460 rir::Literal::Result(_) => "%Result*",
461 rir::Literal::Pointer => "i8*",
462 },
463 rir::Operand::Variable(var) => get_variable_ty(*var),
464 }
465}
466
467fn get_variable_ty(variable: rir::Variable) -> &'static str {
468 match variable.ty {
469 rir::Ty::Integer => "i64",
470 rir::Ty::Boolean => "i1",
471 rir::Ty::Double => "f64",
472 rir::Ty::Qubit => "%Qubit*",
473 rir::Ty::Result => "%Result*",
474 rir::Ty::Pointer => "i8*",
475 }
476}
477
478impl ToQir<String> for rir::BlockId {
479 fn to_qir(&self, _program: &rir::Program) -> String {
480 format!("block_{}", self.0)
481 }
482}
483
484impl ToQir<String> for rir::Block {
485 fn to_qir(&self, program: &rir::Program) -> String {
486 self.0
487 .iter()
488 .map(|instr| ToQir::<String>::to_qir(instr, program))
489 .collect::<Vec<_>>()
490 .join("\n")
491 }
492}
493
494impl ToQir<String> for rir::Callable {
495 fn to_qir(&self, program: &rir::Program) -> String {
496 let input_type = self
497 .input_type
498 .iter()
499 .map(|t| ToQir::<String>::to_qir(t, program))
500 .collect::<Vec<_>>()
501 .join(", ");
502 let output_type = ToQir::<String>::to_qir(&self.output_type, program);
503 let Some(entry_id) = self.body else {
504 return format!(
505 "declare {output_type} @{}({input_type}){}",
506 self.name,
507 if self.call_type == rir::CallableType::Measurement {
508 // Measurement callables are a special case that needs the irreversable attribute.
509 " #1"
510 } else {
511 ""
512 }
513 );
514 };
515 let mut body = String::new();
516 let mut all_blocks = vec![entry_id];
517 all_blocks.extend(get_all_block_successors(entry_id, program));
518 for block_id in all_blocks {
519 let block = program.get_block(block_id);
520 body.push_str(&format!(
521 "{}:\n{}\n",
522 ToQir::<String>::to_qir(&block_id, program),
523 ToQir::<String>::to_qir(block, program)
524 ));
525 }
526 assert!(
527 input_type.is_empty(),
528 "entry point should not have an input"
529 );
530 format!("define {output_type} @ENTRYPOINT__main() #0 {{\n{body}}}",)
531 }
532}
533
534impl ToQir<String> for rir::Program {
535 fn to_qir(&self, _program: &rir::Program) -> String {
536 let callables = self
537 .callables
538 .iter()
539 .map(|(_, callable)| ToQir::<String>::to_qir(callable, self))
540 .collect::<Vec<_>>()
541 .join("\n\n");
542 let profile = if self.config.is_base() {
543 "base_profile"
544 } else {
545 "adaptive_profile"
546 };
547 let body = format!(
548 include_str!("./qir/template.ll"),
549 callables, profile, self.num_qubits, self.num_results
550 );
551 let flags = get_module_metadata(self);
552 body + "\n" + &flags
553 }
554}
555
556/// Create the module metadata for the given program.
557/// creating the `llvm.module.flags` and its associated values.
558fn get_module_metadata(program: &rir::Program) -> String {
559 let mut flags = String::new();
560
561 // push the default attrs, we don't have any config values
562 // for now that would change any of them.
563 flags.push_str(
564 r#"
565!0 = !{i32 1, !"qir_major_version", i32 1}
566!1 = !{i32 7, !"qir_minor_version", i32 0}
567!2 = !{i32 1, !"dynamic_qubit_management", i1 false}
568!3 = !{i32 1, !"dynamic_result_management", i1 false}
569"#,
570 );
571
572 let mut index = 4;
573
574 // If we are not in the base profile, we need to add the capabilities
575 // associated with the adaptive profile.
576 if !program.config.is_base() {
577 // loop through the capabilities and add them to the metadata
578 // for values that we can generate.
579 for cap in program.config.capabilities.iter() {
580 let name = match cap {
581 TargetCapabilityFlags::QubitReset => "qubit_resetting",
582 TargetCapabilityFlags::IntegerComputations => "classical_ints",
583 TargetCapabilityFlags::FloatingPointComputations => "classical_floats",
584 TargetCapabilityFlags::BackwardsBranching => "backwards_branching",
585 _ => continue,
586 };
587 flags.push_str(&format!(
588 "!{} = !{{i32 {}, !\"{}\", i1 {}}}\n",
589 index, 1, name, true
590 ));
591 index += 1;
592 }
593
594 // loop through the capabilities that are missing and add them to the metadata
595 // as not supported.
596 let missing = TargetCapabilityFlags::all().difference(program.config.capabilities);
597 for cap in missing.iter() {
598 let name = match cap {
599 TargetCapabilityFlags::QubitReset => "qubit_resetting",
600 TargetCapabilityFlags::IntegerComputations => "classical_ints",
601 TargetCapabilityFlags::FloatingPointComputations => "classical_floats",
602 TargetCapabilityFlags::BackwardsBranching => "backwards_branching",
603 _ => continue,
604 };
605 flags.push_str(&format!(
606 "!{} = !{{i32 {}, !\"{}\", i1 {}}}\n",
607 index, 1, name, false
608 ));
609 index += 1;
610 }
611
612 // Add the remaining extension capabilities as not supported.
613 // We can't generate these values yet so we just add them as false.
614 let unmapped_capabilities = [
615 "classical_fixed_points",
616 "user_functions",
617 "multiple_target_branching",
618 ];
619 for capability in unmapped_capabilities {
620 flags.push_str(&format!(
621 "!{} = !{{i32 {}, !\"{}\", i1 {}}}\n",
622 index, 1, capability, false
623 ));
624 index += 1;
625 }
626 }
627
628 let mut metadata_def = String::new();
629 metadata_def.push_str("!llvm.module.flags = !{");
630 for i in 0..index - 1 {
631 metadata_def.push_str(&format!("!{i}, "));
632 }
633 metadata_def.push_str(&format!("!{}}}\n", index - 1));
634 metadata_def + &flags
635}
636