Connectivity graph leads to invalid connections that are flagged as an error #2689
Description
There's an underlying incorrectness in the way connectivity is modeled that leads to invalid errors. But these errors may be fine since there should be an error but just not the error that was flagged.
Connectivity is currently specified such that all bundles/channels for a switchbox are single nodes in a graph. That means when we define the valid connectivity such as in AIE2TargetModel::isLegalTileConnection in the lib/Dialect/AIE/IR/AIETargetModel.cpp, it treats each port in the switchbox as a single node in a graph. This works ok when connections come from a neighbor to that port, and then that port is routed to another port such as:
tile(0,3) east0 -> tile(1,3) west0 -> tile(1,3) north1 -> tile(1,4) south1
Here, tile(1,3)'s west0 port is a slave that then connects to the north1 port as a master.
However, an alternate connection is possible, such as:
tile(0,3) east0 -> tile(1,3) west0 -> tile(1,3) south3 -> tile(1,3) north1 -> tile(1,4) south1
Here, south3 is a port that is treated as a single node. As such, a graph could be made as above since there is a valid connection between west0 -> south3 and south3 -> north1. However, what is not indicated is that south3 here is a master and a slave and those two roles are distinct ports in the hardware. In order for the above connection to be valid, we would also need the following:
tile(1,2) north3 -> tile(1,2) north3
It is unlikely the current software search algorithm recognizes the need for this and therefore would not create this extra connection. However, the reason this does not come up as an issue is because the Djikstra's algorithm used in pathfinder will never choose this option since it's always more expensive. So in reality, we would never encounter it even if the current structure of the graph allows it.
Where a valid error does come up is with the definition of dma as a single node in the graph. For something like trace which only has valid connection to a limited set of ports (only south direction, not east, west or north), if I wanted to connect trace to the east port, it can accomplish this in the following way:
trace0 -> dma0 -> east0
This is because trace0 cannot route to the east0 port but it can route to dma0. That is specifically dma s2mm0. Likewise, dma0 can route to east0 but that dma is actually mm2s0. Because it doesn't distinguish between s2mm0 and mm2s0, it treats this as a single node, much like how master and slave for the south0 port is treated as the same thing.
This connection is normally never chosen because it should be cheaper to route south rather than east due to this extra hop or the use of the dma0 node, but if all north-south connections are used up, then it will try to go east and it will think it can do this via this erroneous hop to the dma0 node in the graph. The correct error should be that the route is not possible, but instead, an error will be flagged where dma0 is used in two connections (the main dma0 connection that used up the north-south stream connections, and the trace0->dma0->east0 connection). It's unclear if the scenario could occur where it chooses this connection when no other dma0 use is present and thereby allowing it, but at the moment, that doesn't seem likely. As such, while this is a fundamental flaw in the modeling of the connectivity graph, it is treated as a "do no fix" because it will either never be chosen (as in the first example of the use of the south0 port) or an error will be asserted to prevent it from being true, even if that error doesn't accurately represent the "real" error.