Looping control flow program causes heap exhaustion for some ISAs

[MarquessV]

This control flow program causes quilc to crash when compiling for the built-in bristlecone ISA:

LABEL @START-LOOP
CCNOT 0 1 2
JUMP @START-LOOP

> pbpaste | quilc --isa bristlecone
Heap exhausted during garbage collection: 48 bytes available, 80 requested.
Gen  Boxed Unboxed   LgBox LgUnbox  Pin       Alloc     Waste        Trig      WP GCs Mem-age
fatal error encountered in SBCL pid 36773(tid 0x1004cc240):
GC invariant lost, file "gencgc.c", line 473

This appears to be related to the bristlecone ISA as this program compiles fine for the other built-in ISAs.

[macrologist]

Trying this with a greedy rewiring type seems to at least finish (though it is quite slow).

echo 'PRAGMA INITIAL_REWIRING "GREEDY";LABEL @START-LOOP;CCNOT 0 1 2;JUMP @START-LOOP' | quilc -isa bristlecone

PRAGMA INITIAL_REWIRING "GREEDY"
JUMP @START_LOOP                        # Entering/exiting rewiring: (#(0 6 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71) . #(0 6 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71))
LABEL @BLK-916                          # Entering rewiring: #(0 6 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71)
JUMP @START_LOOP                        # Exiting rewiring: #(0 6 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71)
LABEL @START_LOOP                       # Entering rewiring: #(0 6 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71)
RZ(-1.6533062179011382) 6
RX(pi/2) 6
RZ(-pi/2) 6
RZ(-0.32221729481514494) 1
RX(pi/2) 1
RZ(3*pi/2) 1
CZ 6 1
RZ(-pi/2) 1
RX(pi/2) 1
RZ(pi/2) 1
RZ(-pi/2) 6
RX(pi/2) 6
RZ(pi/2) 6
CZ 6 1
RZ(0.3066798219034011) 6
RX(pi/2) 6
RZ(0.8356226910613698) 6
RX(-pi/2) 6
RZ(1.1296856759837395) 6
CZ 6 0
RZ(pi/2) 6
RX(pi/2) 6
RZ(3*pi/4) 6
RX(-pi/2) 6
RZ(-0.37047021413063197) 6
RZ(-pi/2) 1
RX(pi/2) 1
RZ(4.684223955203036) 1
CZ 6 1
RZ(-0.8695917128961883) 6
RX(pi/2) 6
RZ(1.2568016745110173) 6
RX(-pi/2) 6
RZ(3.8741653060224968) 6
RZ(-1.4235478302030269) 0
RX(pi/2) 0
RZ(pi/2) 0
CZ 6 0
RZ(-pi/2) 0
RX(pi/2) 0
RZ(pi/2) 0
RZ(-pi/2) 6
RX(pi/2) 6
RZ(pi/2) 6
CZ 6 0
RZ(-pi/2) 6
RX(pi/2) 6
RZ(1.4235478302030273) 6
RZ(-2.410539356116933) 1
RX(pi/2) 1
RZ(3*pi/2) 1
CZ 1 6
RZ(-pi/2) 1
RX(pi/2) 1
RZ(pi/4) 1
RX(-pi/2) 1
RZ(pi/2) 1
RZ(5*pi/4) 6
CZ 1 6
RZ(-3*pi/2) 1
RX(pi/2) 1
RZ(3*pi/2) 1
RZ(pi) 6
RZ(-2.40902000115709) 0
RX(pi/2) 0
RZ(1.8847909790787776) 0
RX(-pi/2) 0
RZ(-0.33073439976807384) 0
JUMP @BLK-916                           # Exiting rewiring: #(6 1 0 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71)

I'll look into it.

[macrologist]

@MarquessV I have made a PR that offers a partial answer to this particular woe.

Rebuilding quilc with the above mentioned branch will include support for a pragma that allows the programmer to experiement with rewiring swap insertion search strategies, which is where I found the hang-up to occur during debugging.

You will be able to do something like the following:

echo 'PRAGMA REWIRING_SEARCH "GREEDY_QUBIT";LABEL @START-LOOP;CCNOT 0 1 2;JUMP @START-LOOP' | quilc -isa bristlecone

which should 🤞 give you improved performance with the bristlecone chip. Moreover, the new pragma ought to add one more tool to your bag when trying to compile across different chips.

Let me know if you get a chance to rebuild and test.

[stylewarning]

Merged now. Issue closed?