New "Incremental Routing" broke detailed routing

[smunaut]

Describe the bug

I'm feeding into OpenROAD some partially routed design (I have a custom OpenDB script that manually routes some signal).

In the DEF at the input you can see for instance :

    - gpio_out[29] ( PIN gpio_out[29] ) ( top_I.ctrl_I pad_uo_out[5] ) + USE SIGNAL
      + FIXED met4 ( 1495460 2436620 ) ( * 2838660 ) M3M4_PR ( 97980 * ) M3M4_PR ( * 2867335 ) M3M4_PR
     ( -850 * ) ;

With an older OpenROAD ( tested 4eceed4759ce048f57a5164253fcc32e688cd8ff just before merging PR #5059 ), it works just fine, that routed net is unchanged at the output and the whole process takes like 15 seconds. ( There really isn't much to route in that test project ! ).

Tested a newer OpenROAD ( all revisions after the merge of that PR, I did a git bisect, none work after that merge ), at the output the net has been changed :

    - gpio_out[29] ( PIN gpio_out[29] ) ( top_I.ctrl_I pad_uo_out[5] ) + USE SIGNAL
      + ROUTED met4 ( 1495460 2436620 ) ( * 2838660 )
      NEW met3 ( 97980 2838660 ) ( 1495460 * )
      NEW met3 ( 97980 2838660 ) ( * 2867335 )
      NEW met3 ( -850 2867335 ) ( 97980 * )
      NEW met3 ( 1495460 2838660 ) M3M4_PR
      NEW met3 ( 97980 2838660 ) M3M4_PR
      NEW met3 ( 97980 2867335 ) M3M4_PR ;

Now, except for the first segment which is on met4, all the other segments are on met3 instead of changing layer after each via !!!

And now the routing process takes around 20 minutes ! That is 80 times slower ! Not 80% slower ... no, 80 times longer, that's just unusable and this is a trivial test project ...

Expected Behavior

Well I expect it to not modify the routing explicitely marked as FIXED in the input and I also expect it to not take forever to do it.

Environment

[WARNING] Your current OpenROAD version is outdated.
It is recommened to pull the latest changes.
If problem persists, file a github issue with the re-producible test case.
kernel: Linux 5.10.0-19-cloud-amd64
os: Debian GNU/Linux 11 (bullseye)
cmake version 3.18.4
-- The CXX compiler identification is GNU 10.2.1
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- OpenROAD version: v2.0-13718-g4eceed475
-- System name: Linux
-- Compiler: GNU 10.2.1
-- Build type: RELEASE
-- Install prefix: /usr/local
-- C++ Standard: 17
-- C++ Standard Required: ON
-- C++ Extensions: OFF
-- The C compiler identification is GNU 10.2.1
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Found Python: /usr/bin/python3.9 (found version "3.9.2") found components: Interpreter 
-- Looking for pthread.h
-- Looking for pthread.h - found
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD - Failed
-- Looking for pthread_create in pthreads
-- Looking for pthread_create in pthreads - not found
-- Looking for pthread_create in pthread
-- Looking for pthread_create in pthread - found
-- Found Threads: TRUE  
-- Performing Test C_COMPILER_SUPPORTS__-Wall
-- Performing Test C_COMPILER_SUPPORTS__-Wall - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wall
-- Performing Test CXX_COMPILER_SUPPORTS__-Wall - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-array-bounds
-- Performing Test C_COMPILER_SUPPORTS__-Wno-array-bounds - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-array-bounds
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-array-bounds - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-nonnull
-- Performing Test C_COMPILER_SUPPORTS__-Wno-nonnull - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-nonnull
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-nonnull - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-maybe-uninitialized
-- Performing Test C_COMPILER_SUPPORTS__-Wno-maybe-uninitialized - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-maybe-uninitialized
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-maybe-uninitialized - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format-overflow
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format-overflow - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format-overflow
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format-overflow - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-variable
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-variable - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-variable
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-variable - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-function
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-function - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-function
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-function - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-write-strings
-- Performing Test C_COMPILER_SUPPORTS__-Wno-write-strings - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-write-strings
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-write-strings - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-sign-compare
-- Performing Test C_COMPILER_SUPPORTS__-Wno-sign-compare - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-sign-compare
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-sign-compare - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-deprecated
-- Performing Test C_COMPILER_SUPPORTS__-Wno-deprecated - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-deprecated
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-deprecated - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-c++11-narrowing
-- Performing Test C_COMPILER_SUPPORTS__-Wno-c++11-narrowing - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-c++11-narrowing
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-c++11-narrowing - Failed
-- Performing Test C_COMPILER_SUPPORTS__-Wno-register
-- Performing Test C_COMPILER_SUPPORTS__-Wno-regisCMake Warning at src/CMakeLists.txt:245 (message):
  spdlog: SPDLOG_FMT_EXTERNAL=ON


CMake Error at src/gpl/CMakeLists.txt:44 (find_package):
  By not providing "Findortools.cmake" in CMAKE_MODULE_PATH this project has
  asked CMake to find a package configuration file provided by "ortools", but
  CMake did not find one.

  Could not find a package configuration file provided by "ortools" with any
  of the following names:

    ortoolsConfig.cmake
    ortools-config.cmake

  Add the installation prefix of "ortools" to CMAKE_PREFIX_PATH or set
  "ortools_DIR" to a directory containing one of the above files.  If
  "ortools" provides a separate development package or SDK, be sure it has
  been installed.


ter - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-register
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-register - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal
-- Performing Test C_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal - Failed
-- Performing Test C_COMPILER_SUPPORTS__-fpermissive
-- Performing Test C_COMPILER_SUPPORTS__-fpermissive - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-fpermissive
-- Performing Test CXX_COMPILER_SUPPORTS__-fpermissive - Success
-- Performing Test C_COMPILER_SUPPORTS__-x
-- Performing Test C_COMPILER_SUPPORTS__-x - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-x
-- Performing Test CXX_COMPILER_SUPPORTS__-x - Failed
-- Performing Test C_COMPILER_SUPPORTS__c++
-- Performing Test C_COMPILER_SUPPORTS__c++ - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__c++
-- Performing Test CXX_COMPILER_SUPPORTS__c++ - Failed
-- Performing Test C_COMPILER_SUPPORTS__-std=c++17
-- Performing Test C_COMPILER_SUPPORTS__-std=c++17 - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-std=c++17
-- Performing Test CXX_COMPILER_SUPPORTS__-std=c++17 - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-but-set-variable
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-but-set-variable - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-but-set-variable
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-but-set-variable - Success
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCL header: /usr/include/tcl/tcl.h
-- Found SWIG: /usr/bin/swig4.0 (found suitable version "4.0.2", minimum required is "4.0")  
-- Found Boost: /usr/lib/x86_64-linux-gnu/cmake/Boost-1.81.0/BoostConfig.cmake (found version "1.81.0")  
-- boost: 1.81.0
-- Found Python3: /usr/include/python3.9 (found version "3.9.2") found components: Development Development.Module Development.Embed 
-- Found ZLIB: /usr/lib/x86_64-linux-gnu/libz.so (found version "1.2.11") 
-- spdlog: 1.8.1
-- Found BISON: /usr/bin/bison (found version "3.7.5") 
-- Found Doxygen: /usr/bin/doxygen (found version "1.9.1") found components: doxygen missing components: dot
-- STA version: 2.5.0
-- STA git sha: ee8d3d0fa23bfbc69f3e936ff884c3d30f5bfb59
-- System name: Linux
-- Compiler: GNU 10.2.1
-- Build type: RELEASE
-- Build CXX_FLAGS: -O3 -DNDEBUG
-- Install prefix: /usr/local
-- Found FLEX: /usr/bin/flex (found version "2.6.4") 
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCL header: /usr/include/tcl/tcl.h
-- Check if compiler accepts -pthread
-- Check if compiler accepts -pthread - yes
-- SSTA: 0
-- Found SWIG: /usr/bin/swig4.0 (found suitable version "4.0.2", minimum required is "3.0")  
-- STA executable: /mnt/pdk/OL2/native/OpenROAD/src/sta/app/sta
-- Configuring incomplete, errors occurred!

To Reproduce

15-openroad-detailedrouting.zip

Added Openlane2 reproducible, should run on its own.

Relevant log output

No response

Screenshots

No response

Additional Context

No response

[osamahammad21]

DRT did not support incremental routing before this PR. So it's a bit inaccurate when you say "new incremental routing broke drt". Let me explain what used to happen before this PR:

• DRT reads all nets.
• The prerouted nets are not seen by the detailed router in the routing process.
• There are only 59 nets with route guides. Those are the only nets that are modified and routed by DRT. The other nets are not touched. As it happens, the FIXED nets do not have global routing guides. That's why they are not changed by the router, not because they are fixed.
• After DRT finishes routing, it updates the ODB nets of the routed 59 nets only. If you check those nets, you would find that there are duplicate segments in the def for their wires. This is because DRT did not clear the routing, but it appended on it.

So as you can see it did not work correctly before this PR. The other problem is that after the PR, DRT does not support FIXED routing. If you want the router to not touch FIXED nets I can work on that. However, the router will end up with nothing to do because for it will not touch the routed nets for the first 3 iterations. Could you specify what is the expected behavior for all nets; routed, fixed, without guides?

[smunaut]

From my (user) PoV, I wrote that issue description as such because "Incremental Routing" (as-in the feature named as such in the title of the branch that was merged that triggered the fault). And "broke drt" as in "broke the DRT step of the flow" because DRT is the step where things go wrong with that branch merged whereas before it would end up doing what I expect.

I'm not sure how to inspect the ODB database directly so I usually look at the DEF that are written at the same time as the ODB to know what's going on. And so I have no idea about routing guides since those are not there.

And what I see is that the route for gpio_out[29] was changed by the DRT step. See what I posted, it's clearly different before/after ... and that wasn't happening before the merge of that branch.

And to be clear, given how those routes are changed, I don't think this is INTENDED behavior, I think something, somewhere ends up corrupting them and that wasn't happening before that branch was merged. Now for all I know the merge just triggers a pre-existing bug somewhere else, I have no idea, all I know is that it worked before and doesn't anymore.

Ideally, what I expect is that if before going through GRT/DRT I have some wires that have FIXED routing and that routing actually completes the requested connections (i.e. it does go and connect everything that's supposed to be connected on that net ), then those wires shouldn't be changed at all. Previously, from what I could see, any net that had any FIXED routing ) wouldn't be changed (even if that routing wasn't complete or didn't ensure connectivity between all the pins) and I can live with that.

[smunaut]

Any news on this ? Any more info you need from our side ?

[maliberty]

No more info is needed for now. This week will be slow as several people at ETH Zurich.