quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
448 stars 73 forks source link

Programs with control flow instructions are not compiled correctly #911

Closed MarquessV closed 5 months ago

MarquessV commented 5 months ago

This contrived program implements a fixed-count loop using Quil's classical control flow instructions:

DECLARE ro BIT
DECLARE shot_count INTEGER[1]
LABEL @START
MEASURE 0 ro[0]
SUB shot_count[0] 1
JUMP-UNLESS @END shot_count[0]
JUMP @START
LABEL @END

When we compile this program with quilc, we get:

DECLARE ro BIT
DECLARE shot_count INTEGER

SUB shot_count[0] 1
MEASURE 0 ro[0]
JUMP-WHEN @BLK-715 shot_count[0]
JUMP @END
LABEL @END
HALT                                               

The JUMP-UNLESS instruction gets inverted into a JUMP-WHEN instruction with a new target specified, but that target has no associated label in the program, making it an invalid target to jump to.

Simplified Variation

After seeing the above result, I tried simplifying the program by inverting the JUMP-WHEN instruction myself:

DECLARE ro BIT
DECLARE shot_count INTEGER[1]
LABEL @START
MEASURE 0 ro[0]
SUB shot_count[0] 1
JUMP-WHEN @START shot_count[0]

Unfortunately, quilc still produces an incorrect result:

DECLARE ro BIT
DECLARE shot_count INTEGER

SUB shot_count[0] 1
MEASURE 0 ro[0]
JUMP-WHEN @BLK-713 shot_count[0]
JUMP @BLK-662
LABEL @BLK-662
HALT

In this case, quilc adds a target without an associated label and adds an extraneous jump and label to the program.