✨ Eliminate global variables from DD package

[burgholzer]

What's the problem this feature will solve?

The DD package contains a “fine collection” of (non-const) global variables. This includes the terminal nodes for DDs as well as the real number constants for 0., 1., 1./sqrt(2) and the complex number constants zero and one. All of these are defined as (non-const) static variables with global scope. This has a number of drawbacks:

• it is a bad coding practice to have non-const global variables (clang-tidy even warns about it).
• It leads to all kinds of problems with static initialization and the order of initialization (clang-tidy even warns about that)
• It was one of the main reasons why the MQT had problems building under Windows with MSVC. And took quite some while to get working.
• These “constant” entries are never really constant; they are mutable. Not only does this convey the wrong intentions, but it also increases the potential for introducing errors when these entries are erroneously modified.
• Due to these special entities actually being static instances of the respective class, their memory address differs across runs and, in the worst case (without proper care), between translation units.
• Due to these special entities being regular class instances, it is mostly assumed that any pointer member may just be dereferenced (as nullptr should never really occur). While this might seem beneficial at first, it promotes not using the member functions of the respective classes that safeguard the access and rather directly manipulating the dereferenced instances. Especially since we make use of unaligned pointers, this can be quite dangerous.
• Minor: all the data members of these special entities (such as ref count, next pointer, etc.) are never actually used. So it is kind of a waste to allocate them.

Describe the solution you'd like

This list of undesirable behavior is arguably quite long. So what could be done about it?
Since we are heavily dealing with pointer types, there is one rather straight forward solution: replace these global (non-)constants with clever uses of nullptr.

For DD terminal nodes, that is fairly straightforward. Up until now, a terminal node was a pointer to a global static Node that had variable index -1. The successors of that node were never accessed and any check for a terminal either compared addresses with the pointer to the terminal node or checked the variable index. This kind of usage of the variable index necessitated a signed type for that variable and, hence, halved the maximal number of qubits that could be supported by the package from 255 to 128.
The notion of a terminal can simply be replaced by the nullptr without any apparent downsides.

• Checking whether a node is a terminal remains a memory address comparison. It now, would just be a simple nullptr check. This should really be a one to one replacement.
• After that change, the data type of the variable index might be switched to an unsigned one, so that more qubits become available as part of the package. This might require some more changes in the code as I would suspect that there are quite some checks in the code base that have the form ˋif(p->v == -1)ˋ. These should be adjusted accordingly to benefit from the enhanced qubit range.

For the real number constants, the story is not so easy. The main problem here is that there is not a single, but three different constants that are being used (0., 1., and 1/sqrt(2)). Thus, these constants can’t simply all be replaced by using nullptr. Furthermore, the value of these entries are actually used in computations. However, there is a potential solution for that:
We already make use of the LSB of pointers to numbers to indicate that they are negative. Why not turn that up a notch and make use of the available scratch space in the lower bits of the pointers? (Due to alignment reasons, the lower three bits of any valid pointer are zero, which leaves 3 bits for hiding some stuff in pointers). The following hinges on one assumption: nullptr lives at address 0x0. Instead of creating global (non-)constants, the nullptr and its least significant three bits can be used to encode these special values:

• As before, the least significant bit encodes the sign of the number.
• 0x0 encodes 0.
• 0x2 encodes 1.
• 0x4 encodes 1/sqrt(2)
• This leaves room for one more number to encode. Here, it might make a lot of sense to use 0.5 (which is then encoded as 0x6). The number 0.5 is currently unconditionally added to the real number table and never collected. Might as well make it a constant.
• Checking for a particular constant remains as easy as before and is a simple pointer comparison.
• Checking wether a given pointer points to any constant is as simple as masking out the three least significant bits and comparing to 0x0.
• Getting the value for a constant number can be efficiently handled by a size 8 lookup table that is based on the three least significant bits of a pointer.
• The big question is: how high is the overhead of having to add an additional if condition in the access function to the value of a number (for checking whether the number is a constant). And, can this overhead sometimes be avoided if it is clear that none of the entries is a constant? This has to be benchmarked an investigated.

The good thing is: these two changes are independent from one another and can happen in parallel (or the complex number change might not happen at all).

Tasks

Preview Give feedback

1. Eliminate the global DD node terminals ♻️ Eliminate DD terminal nodes #381
2. Eliminate the global constant numbers
3. Change the signedness of the variable index type in DD nodes ♻️ Eliminate DD terminal nodes #381