Repository: siliconcompiler/siliconcompiler

Issue:
Flowgraph race condition when setting up nodes
### Version

0.29.0

### On which OS did this happen?

Linux

### On which Python version did this happen?

Python 3.11

### Reproduction Steps

I'm using proprietary code so I can't share the manifest. I have a graph that looks like below. The behavior happens on `clean` runs, with `/build` directory removed for extra insurance. 

![Image width:50%](https://github.com/user-attachments/assets/bdc7c2db-76ac-4e1b-9565-518c4771f4f5)

`xrun/compile` is a task that receives files from other nodes as `input` and generates a single file as `output`.  Its setup function looks something like this:

```python

def setup(chip):
    setup_tools(chip)

    step = chip.get("arg", "step")
    index = chip.get("arg", "index")
    tool, task = get_tool_task(chip, step, index)
    # ...
    chip.add("tool", tool, "task", task, "output", os.path.join(chip.getworkdir(step=step, index=index), "compiled.lib"), step=step, index=index)
    chip.set( "tool", tool, "task", task, "input", list(input_provides(chip, step, index).keys()), step=step, index=index)
    # ...
```


### Expected Behavior

I'm expecting node `compile_top_tb` to receive two files, one from `compile_ip2` and another one from `compile_uvm`.

### Actual Behavior

Sometimes, `compile_top_tb` receives the file only from `compile_uvm`, even though the flow graph shows the dependency between `compile_ip2` and `compile_top_tb` also.  

I added some prints in the `setup` function and displayed the input nodes and the files received from each node. 
```text
| INFO    | custom_job | -----                | - | Setting up node compile_uvm0 with xrun/compile
| WARNING | custom_job | -----                | - | Nodes: []
| INFO    | custom_job | -----                | - | Setting up node compile_common_ip with xrun/compile
| WARNING | custom_job | -----                | - | Nodes: []
| INFO    | custom_job | -----                | - | Setting up node compile_ip10 with xrun/compile
| WARNING | custom_job | -----                | - | Nodes: [('compile_common_ip', '0')]
| WARNING | custom_job | -----                | - | Input: ~/sc/build/mypkg/custom_job/compile_common_ip/0/compiled.lib
| INFO    | custom_job | -----                | - | Setting up node compile_top_tb0 with xrun/compile
| WARNING | custom_job | -----                | - | Nodes: [('compile_ip2', '0'), ('compile_uvm', '0')]
| WARNING | custom_job | -----                | - | Input: ~/sc/build/mypkg/custom_job/compile_uvm/0/compiled.lib
| INFO    | custom_job | -----                | - | Setting up node compile_ip20 with xrun/compile
| WARNING | custom_job | -----                | - | Nodes: [('compile_common_ip', '0'), ('compile_ip1', '0')]
| WARNING | custom_job | -----                | - | Input: ~/sc/build/mypkg/custom_job/compile_common_ip/0/compiled.lib
| WARNING | custom_job | -----                | - | Input: ~/sc/build/mypkg/custom_job/compile_ip1/0/compiled.lib
| INFO    | custom_job | -----                | - | Checking manifest before running.
```

Based on the log, you can see that node `compile_top_tb` has two input nodes, but receives only one file form `compile_uvm`. 

I suspect the problem is related to the order the nodes are being `setup`. Based on the log, we call `setup` for `compile_top_tb` before `compile_ip2`, this means that `compile_ip2` have not yet registered the output files to the "schema".

Hints from issue comments:
@gadfort: @Ciprian167 thanks, took a bit to reproduce, but I think I have it fixed.

As an aside, ideally you would not use abspaths in the input/output keys. A post processing step would be able to ensure the resultant files are in the `outputs/` directory, allowing the scheduler to handle the IOs.
@Ciprian167: That was fast! Thanks for the support and hints, @gadfort.  @Ciprian167: > [@Ciprian167](https://github.com/Ciprian167) thanks, took a bit to reproduce, but I think I have it fixed.
> 
> As an aside, ideally you would not use abspaths in the input/output keys. A post processing step would be able to ensure the resultant files are in the `outputs/` directory, allowing the scheduler to handle the IOs.

Maybe this is not the place but, a follow up on this comment. I'm not providing abspaths in the input and output keys directly. The tasks are working with/on libraries, and when I'm registering a file to a library I'm using relative paths. The abspath is begin used when I call `register_source`. Here's an example:

```python
import os
import siliconcompiler

import src.lib1.lib1 as lib1
import src.lib2.lib2 as lib2


def setup():
    lib = siliconcompiler.Library("prim", package="prim", auto_enable=True)
    lib.register_source(name="prim", path=os.path.abspath(os.path.dirname(__file__)))

    lib.add("input", "rtl", "verilog", "prim.v")
    lib.add("input", "rtl", "verilog", "mod1.v")
    lib.add("input", "rtl", "verilog", "mod2.v")
    lib.add("input", "elab", "href", "config/href.txt")

    lib.use(lib1)
    lib.use(lib2)

    return lib
```

Is this the intended usage? Also, I don't see anything in the `inputs/ouputs/ dirs. Would they get populated when I use libraries as well? @Ciprian167: FIY, I tried setting the `copy` parameter for the library the following way:

Right in the library's setup function:
```python
lib.set("input", "rtl", "systemverilog", True, field='copy')
lib.set("input", "rtl", "verilog", True, field='copy')
```
In the task itself like:
```python
chip.set("library", design_lib, "input", "rtl", "systemverilog", True, field='copy')
chip.set("library", design_lib, "input", "rtl", "verilog", True, field='copy')
```
where `design_lib` is the library being processed. 

None of these seem to generate the output you describe. @gadfort: @Ciprian167 
I meant in the task driver:
```
chip.add("tool", tool, "task", task, "output", "compiled.lib", step=step, index=index)
chip.set( "tool", tool, "task", task, "input", <name>, step=step, index=index)
```

If you need to receive the same file from different nodes, they can be enumerated as:
```
chip.set( "tool", tool, "task", task, "input", "compiled.<step0><index>.lib", step=step, index=index)
chip.set( "tool", tool, "task", task, "input", "compiled.<step1><index>.lib", step=step, index=index)
chip.set( "tool", tool, "task", task, "input", "compiled.<step2><index>.lib", step=step, index=index)
```

Solution patch:
diff --git a/siliconcompiler/flowgraph.py b/siliconcompiler/flowgraph.py
index 652a4f4eb..3ef97093f 100644
--- a/siliconcompiler/flowgraph.py
+++ b/siliconcompiler/flowgraph.py
@@ -205,18 +205,36 @@ def _get_flowgraph_execution_order(chip, flow, reverse=False):
             else:
                 ex_map.setdefault((istep, iindex), set()).add((step, index))
 
+    rev_ex_map = {}
+    for node, edges in ex_map.items():
+        for step, index in edges:
+            rev_ex_map.setdefault((step, index), set()).add(node)
+
     # Collect execution order of nodes
     if reverse:
         order = [set(_get_flowgraph_exit_nodes(chip, flow))]
     else:
         order = [set(_get_flowgraph_entry_nodes(chip, flow))]
 
+    visited = set()
     while True:
         next_level = set()
-        for step, index in order[-1]:
-            if (step, index) in ex_map and \
-               not any([(step, index) in v for v in ex_map.values()]):
-                next_level.update(ex_map.pop((step, index)))
+        next_visited = set()
+        for step, index in sorted(order[-1]):
+            if (step, index) not in rev_ex_map:
+                # No edges so assume inputs are okay
+                inputs_valid = True
+            else:
+                inputs_valid = all([node in visited for node in rev_ex_map[(step, index)]])
+
+            if inputs_valid:
+                next_visited.add((step, index))
+                if (step, index) in ex_map:
+                    next_level.update(ex_map.pop((step, index)))
+            else:
+                next_level.add((step, index))
+
+        visited.update(next_visited)
 
         if not next_level:
             break
@@ -233,7 +251,7 @@ def _get_flowgraph_execution_order(chip, flow, reverse=False):
 
     exec_order.reverse()
 
-    return exec_order
+    return [sorted(level) for level in exec_order]
 
 
 def get_executed_nodes(chip, flow):


Test patch:
diff --git a/tests/core/test_flowgraph.py b/tests/core/test_flowgraph.py
index db90e96c4..61da9d25b 100644
--- a/tests/core/test_flowgraph.py
+++ b/tests/core/test_flowgraph.py
@@ -1,6 +1,7 @@
-from siliconcompiler import Chip
-from siliconcompiler.flowgraph import get_nodes_from
+from siliconcompiler import Chip, Flow
+from siliconcompiler.flowgraph import get_nodes_from, _get_flowgraph_execution_order
 from siliconcompiler.targets import freepdk45_demo
+from siliconcompiler.tools.builtin import nop
 
 
 def test_get_nodes_from():
@@ -39,3 +40,103 @@ def test_get_nodes_from_with_to():
     assert ('dfm.metal_fill', '0') in nodes
     assert ('write.gds', '0') not in nodes
     assert ('write.views', '0') not in nodes
+
+
+def test_exec_order():
+    flow = Flow('test_flow')
+    flow.node('test_flow', 'exec0', nop)
+    flow.node('test_flow', 'exec1', nop)
+    flow.node('test_flow', 'exec2', nop)
+    flow.node('test_flow', 'exec3', nop)
+    flow.node('test_flow', 'exec4', nop)
+
+    flow.edge('test_flow', 'exec0', 'exec1')
+    flow.edge('test_flow', 'exec0', 'exec2')
+    flow.edge('test_flow', 'exec1', 'exec2')
+    flow.edge('test_flow', 'exec2', 'exec3')
+    flow.edge('test_flow', 'exec4', 'exec3')
+
+    chip = Chip('test')
+    chip.use(flow)
+
+    order = _get_flowgraph_execution_order(chip, 'test_flow')
+    assert len(order) == 4
+    assert order[0] == [('exec0', '0'), ('exec4', '0')]
+    assert order[1] == [('exec1', '0')]
+    assert order[2] == [('exec2', '0')]
+    assert order[3] == [('exec3', '0')]
+
+
+def test_exec_order_reverse():
+    flow = Flow('test_flow')
+    flow.node('test_flow', 'exec0', nop)
+    flow.node('test_flow', 'exec1', nop)
+    flow.node('test_flow', 'exec2', nop)
+    flow.node('test_flow', 'exec3', nop)
+    flow.node('test_flow', 'exec4', nop)
+
+    flow.edge('test_flow', 'exec0', 'exec1')
+    flow.edge('test_flow', 'exec0', 'exec2')
+    flow.edge('test_flow', 'exec1', 'exec2')
+    flow.edge('test_flow', 'exec2', 'exec3')
+    flow.edge('test_flow', 'exec4', 'exec3')
+
+    chip = Chip('test')
+    chip.use(flow)
+
+    order = _get_flowgraph_execution_order(chip, 'test_flow', reverse=True)
+    assert len(order) == 4
+    assert order[0] == [('exec3', '0')]
+    assert order[1] == [('exec2', '0'), ('exec4', '0')]
+    assert order[2] == [('exec1', '0')]
+    assert order[3] == [('exec0', '0')]
+
+
+def test_exec_order_linear():
+    flow = Flow('test_flow')
+    flow.node('test_flow', 'exec0', nop)
+    flow.node('test_flow', 'exec1', nop)
+    flow.node('test_flow', 'exec2', nop)
+    flow.node('test_flow', 'exec3', nop)
+    flow.node('test_flow', 'exec4', nop)
+
+    flow.edge('test_flow', 'exec0', 'exec1')
+    flow.edge('test_flow', 'exec1', 'exec2')
+    flow.edge('test_flow', 'exec2', 'exec3')
+    flow.edge('test_flow', 'exec3', 'exec4')
+
+    chip = Chip('test')
+    chip.use(flow)
+
+    order = _get_flowgraph_execution_order(chip, 'test_flow')
+    assert len(order) == 5
+    assert order[0] == [('exec0', '0')]
+    assert order[1] == [('exec1', '0')]
+    assert order[2] == [('exec2', '0')]
+    assert order[3] == [('exec3', '0')]
+    assert order[4] == [('exec4', '0')]
+
+
+def test_exec_order_with_index():
+    flow = Flow('test_flow')
+    flow.node('test_flow', 'exec0', nop)
+    flow.node('test_flow', 'exec1', nop, index='0')
+    flow.node('test_flow', 'exec1', nop, index='1')
+    flow.node('test_flow', 'exec1', nop, index='2')
+    flow.node('test_flow', 'exec2', nop)
+
+    flow.edge('test_flow', 'exec0', 'exec1', head_index='0')
+    flow.edge('test_flow', 'exec0', 'exec1', head_index='1')
+    flow.edge('test_flow', 'exec0', 'exec1', head_index='2')
+    flow.edge('test_flow', 'exec1', 'exec2', tail_index='0')
+    flow.edge('test_flow', 'exec1', 'exec2', tail_index='1')
+    flow.edge('test_flow', 'exec1', 'exec2', tail_index='2')
+
+    chip = Chip('test')
+    chip.use(flow)
+
+    order = _get_flowgraph_execution_order(chip, 'test_flow')
+    assert len(order) == 3
+    assert order[0] == [('exec0', '0')]
+    assert order[1] == [('exec1', '0'), ('exec1', '1'), ('exec1', '2')]
+    assert order[2] == [('exec2', '0')]