rewrite hash function

[Co1lin]

Currently our hash function will give different values for topologically identical circuits, because it involves GUID/pointer address of gates in hash value computation.

[xumingkuan]

Where do we encounter this issue? When we have two topologically identical circuits, which one do we want to keep, and is there a memory leakage problem?

[Co1lin]

In RL, we want to find out the shortest path from the original input circuit to the best circuit discovered by us. On the optimization path, it's very common to see some loops like ... -> A_1 -> B -> ... -> A_2 -> ..., but we are unable to simplify this since hash(A_1) != hash(A_2) though they are topologically identical. It is caused by involving memory address in hash computation while gates in A_2 have different addresses from A_1 because it is obtained by applying transformations to another circuit in which we will create new Op objects.

A simple workaround is converting circuits to strings and then use string hash function to decide whether two circuits are equivalent.

@xumingkuan For quartz (not RL), why we need to involve memory address into hash computation? For BFS, how the current hash function guarantee that there's no loop?

[xumingkuan]

I just read the function size_t Graph::hash(void), which I believe is written by @zikun-li. We do not actually involve memory address in hash computation -- the only memory address involved in the computation is Op::ptr, which is effectively created at

quartz/src/quartz/tasograph/substitution.cpp

Line 668 in 6d5da4c

Gate *gate = context->get_gate(opx->type);

This function returns the same Gate * object for the same GateType object passed in.

We should document this somewhere, but I believe two equivalent Graph objects have the same hash values.

[Co1lin]

@xumingkuan Thank you for your investigation (I didn't get a chance to dig into it)! Then I think in one process, two equivalent graphs should have the same hash values. I will check it later whether I got something seemed contradictory to this.

[zikun-li]

Another issue about the function size_t Graph::hash(void) (not sure if it is related to this) is that it currently does not take constant parameters into consideration. Which means that, if there are two circuits whose topologies are the same but values of some parameter on the same rotation gate are different, then size_t Graph::hash(void) is not able to distinguish them. We need to fix this.