Handle conditionals

[Roland-djee]

This PR addresses the correct handle of conditionals and goes beyond #18.

After quite some meandering, it is a major refactor and implementation of a new class: QirConverter. Its main responsibility is to create and transform the CFG from a QIR program to handle conditionals appropriately. In short, the QirConverter does:

• Create and topologically sort the CFG.
• Apply (or not) a simple optimisation that is to contract linear chains of blocks that are linked by jump instructions.
• Iterate through the CFG blocks and calling the QirParser to generate the corresponding circuit. Previous conditionality management in the QirParser now encumbers the QirConverter. The QirParser is solely responsible for returning a circuit from a given block.
• Guard the blocks appropriately based on Pete's (or John Gavin's ?) algorithm.
• Generating a final circuit where each QIR block is guarded.

Minor new helpful functionalities:

• Maintaining the CFG structure by considering then clauses as resuming the flow of the main circuit.
• Treating jumps as flow continuation.
• Extending the canonical c register for created ssa variables to avoid non-simplicity of circuits.
• Representing the read_result instruction as CopyBitOp.
• Keeping and returning a log of ssa variables as a circuit member ssa_vars.

It also adds another validation test from the RUS example file.

[cqc-alec]

considering else clauses as resuming the flow of the main circuit

I don't quite understand this. Wouldn't the "else" circuitry then be executed unconditionally?

[Roland-djee]

considering else clauses as resuming the flow of the main circuit

I don't quite understand this. Wouldn't the "else" circuitry then be executed unconditionally?

Yes, exactly. If I condition the else circuit (which I did over the last week) I lose the domination tree structure for ssa instructions and I won't be able to generate any QIR. For all circuit examples I have seen so far, the output of true condition branches join the else ones. I know this is not an argument strong enough but if we stick to bits prepared in the 0 state initially, the else clause is the normal instruction flow.

[cqc-alec]

So it seems that in all the QIR test cases here, the else clause actually does nothing. For example, in SimpleConditionalCircuit.ll, we have the following:

define void @main() #0 {
entry:
  call void @__quantum__qis__x__body(%Qubit* null)
  call void @__quantum__qis__x__body(%Qubit* inttoptr (i64 1 to %Qubit*))
  %0 = call i1 @__quantum__qis__read_result__body(%Result* null)
  br i1 %0, label %then, label %else

then:                                             ; preds = %entry
  call void @__quantum__qis__h__body(%Qubit* null)
  call void @__quantum__qis__h__body(%Qubit* inttoptr (i64 1 to %Qubit*))
  br label %continue

else:                                             ; preds = %entry
  br label %continue

continue:                                         ; preds = %else, %then

etc.

But what if instead of

else:                                             ; preds = %entry
  br label %continue

we had something like

else:                                             ; preds = %entry
  call void @__quantum__qis__x__body(%Qubit* null)
  br label %continue

In that case, the X gate should be applied if and only if the condition in

  br i1 %0, label %then, label %else

is false. Is this correctly handled in this implementation?

[Roland-djee]

Is this correctly handled in this implementation?

No. The case you describe above is an if/then/else clause I think. The fact is that these kinds of constructs are possible using pyqir-generator to mimic an if/then clause (ie there is this extra else block before joining to the same output block). Tbh, more sophisticated conditional constructs than if/then would require CFG analysis to satisfy SSA dominance principle.

[Roland-djee]

We need to support arbitrary control flow involving forward branching. For example, we need to support this kind of thing:

recursion-3.pdf

So a rethink is required. The "if-conversion" algorithm [1] could be useful.

[1] https://dl.acm.org/doi/abs/10.1145/567067.567085

Sure. However, I would be interested in running this example in the current implementation to see if it totally breaks it.