Invalid LLVM code from unreachable Q# code

[msoeken]

Describe the bug

Invalid LLVM code is generated in a Q# example with unreachable code.

To Reproduce

Run the following project:

<Project Sdk="Microsoft.Quantum.Sdk/0.15.2103131668-beta">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp5.0</TargetFramework>
    <PlatformTarget>x64</PlatformTarget>
    <QirGeneration>true</QirGeneration>
    <CSharpGeneration>false</CSharpGeneration>
    <IncludeQSharpCorePackages>false</IncludeQSharpCorePackages>
  </PropertyGroup>

  <ItemGroup>
    <PackageReference Include="Microsoft.Quantum.QSharp.Foundation" Version="0.15.2103131668-beta" />
  </ItemGroup>

</Project>

// Program.qs
namespace Example {
    open Microsoft.Quantum.Intrinsic;

    @EntryPoint()
    operation RunProgram() : Unit {
        let _ = Foo();
        return ();
        let _ = Foo();
    }

    internal operation Foo() : Bool {
        return true;
    }
}

// Program.cs
return 0;

Then run clang++ -c qir/project.ll, which yields:

qir/project.ll:19:3: error: instruction expected to be numbered '%2'
  %1 = call i1 @Example__Foo__body()
  ^
1 error generated.

Generated LLVM

%Result = type opaque
%Range = type { i64, i64, i64 }

@ResultZero = external global %Result*
@ResultOne = external global %Result*
@PauliI = constant i2 0
@PauliX = constant i2 1
@PauliY = constant i2 -1
@PauliZ = constant i2 -2
@EmptyRange = internal constant %Range { i64 0, i64 1, i64 -1 }

@Example__RunProgram = alias void (), void ()* @Example__RunProgram__body

define void @Example__RunProgram__body() #0 {
entry:
  %0 = call i1 @Example__Foo__body()
  ret void
  %1 = call i1 @Example__Foo__body()
  ret void
}

define i1 @Example__Foo__body() {
entry:
  ret i1 true
}

attributes #0 = { "EntryPoint" }

System information

• Version: 0.15.2103131668-beta
• macOS 11.2.2

Additional context

This is not an issue because of unreachable Q# code, but due to the instruction %1. Other examples with unreachable code worked well.

[bettinaheim]

@msoeken Do you have an example for what unreachable code it was happy with (since the numbering seems valid to me)? Though the cleanest fix is probably to just trim the unreachable code before generating QIR.

[msoeken]

@bettinaheim When I tried to create an example, the following worked well:

@EntryPoint()
operation RunProgram() : Unit {
  Message("Hello");
  return ();
  Message("World");
}

[bettinaheim]

Ok, This one wouldn't have the numbering then. I am not sure why clang is unhappy with it, but I'll put it on the backlog that we trim unused code (I believe it is currently a warning, but no trimming is done).

[msoeken]

I think that's a good solution. I was just pointing out that the problem is not due to unreachable code in LLVM, but due to the numbering. First I thought that a ret block might be followed by a label, but that's not the case.

[kevinhartman]

I am not sure why clang is unhappy with it.

I believe this is because the ret immediately before is terminal, and so there's a new basic block starting after, which is implicitly assigned temporary %1. So the next assignment needs to use temporary %2 since this numbering is shared.

Reference: https://llvm.org/docs/LangRef.html#identifiers

Unnamed temporaries are numbered sequentially (using a per-function incrementing counter, starting with 0). Note that basic blocks and unnamed function parameters are included in this numbering.

[swernli]

@cesarzc FYI, I confirmed that this problem does still repro on the latest QDK, and I believe the changes in https://github.com/microsoft/qsharp-compiler/pull/941 would be correct for addressing it. However, that PR was rather out of date and I closed it so a fresh one on latest main could be built up. If you are planning on addressing this still, please coordinate with @kevinhartman to ensure you don't end up duplicating any efforts. Thanks!

[kevinhartman]

Sounds good, @swernli! I'll leave that branch around in case it's helpful. These days I work on Qiskit Terra full-time so I'm less inclined to contribute to quantum projects in my leisure. Though please do feel free to tag me if any questions arise!