Visiting nodes created during traversal creates weird situations

[haved]

Take the following situation that occurs in the MemoryStateEncoder:

Let's say that the first visited node is the BITS32(4), followed by the highlighted Alloca.
When visited, it creates a MemoryStateJoin that takes the LambdaEntryMemoryStateSplit as one of its inputs.
Since the Entry Split has not been visited yet, the new MemoryStateJoin is placed "behind" the frontier.

Then we get all the way down to the Store, which is replaced by a new Store that take the MemoryStateJoin as input. Because the join has not yet been visited, the replacement Store is also placed "behind" the frontier.

Once the MemoryStateJoin we created finally gets visited, it will cause the replacement Store to be visited, which is the given an additional replacement store, connected to the previous replacement store. The end result is that we get two chained stores instead of one.

The only reason this is not causing test failures in #1303 is that the LambdaEntryMemoryStateSplit happens to be visited before any of the Allocas, due to the internal FIFO frontier. Had the Allocas been top nodes this would have failed.

To avoid issues sneaking in I think it makes sense to use a more direct policy: Nodes created during traversal are never visited (aka. considered visited the moment they are created).

Throughts @caleridas @phate

[haved]

Or I guess even better: the node is not automatically considered visited, but once all its predecessors are visited it gets visited immediately without being returned by next(). We can for example use the Node Id to check if the node was created after the start of traversal.

[caleridas]

Take the following situation that occurs in the MemoryStateEncoder:

Let's say that the first visited node is the `BITS32(4)`, followed by the highlighted `Alloca`. When visited, it creates a `MemoryStateJoin` that takes the `LambdaEntryMemoryStateSplit` as one of its inputs. Since the Entry Split has not been visited yet, the new `MemoryStateJoin` is placed "behind" the frontier.

Then we get all the way down to the Store, which is replaced by a new Store that take the MemoryStateJoin as input. Because the join has not yet been visited, the replacement Store is also placed "behind" the frontier.

Once the MemoryStateJoin we created finally gets visited, it will cause the replacement Store to be visited, which is the given an additional replacement store, connected to the previous replacement store. The end result is that we get two chained stores instead of one.

The only reason this is not causing test failures in #1303 is that the LambdaEntryMemoryStateSplit happens to be visited before any of the Allocas, due to the internal FIFO frontier. Had the Allocas been top nodes this would have failed.

To avoid issues sneaking in I think it makes sense to use a more direct policy: Nodes created during traversal are never visited (aka. considered visited the moment they are created).

Throughts @caleridas @phate

I would argue that this breaks an assumption behind my understanding of what of top down traversal based transformation is allowed to do: it should consider unvisited nodes as "invisible" and not create nodes that hang off unvisited nodes

[phate]

@haved Now, after the refactoring of the traversers is done. Do we have any overview over which passes currently break the assumption of "only dependent on visited nodes". The ones I am currently aware of are:

1. MemoryStateEncoder
2. HLS GammaMerge pass

Any others we need to fix?