DPL: topological sort cycle in shift legalizer with multi-height cells (DPL-0400)

[oharboe]

Untar and run bug2_cells_incorrectly_ordered.tar.gz

Requires the sibling bad_optional_access fix to be applied first.

Error

Detailed placement improvement.
[INFO DPL-0320] Collected 1276 fixed cells.
[INFO DPL-0318] Collected 2 single height cells.
[INFO DPL-0319] Collected 2 multi-height cells spanning 62 rows.
[INFO DPL-0310] Assigned 2 cells into segments.  Movement in X-direction is 0.000000
[INFO DPL-0310] Assigned 2 cells into segments.  Movement in X-direction is 35506.000000, movement in Y-direction is 69559.000000.
[ERROR DPL-0400] Detailed improvement internal error: Cells incorrectly ordered during shifting.

Description

improve_placement fails with DPL-0400 Cells incorrectly ordered during shifting on designs with multi-height cells. Hidden behind the bad_optional_access crash (see sibling issue). Reproduces after applying the fix for that crash. Reported in #9862 on ICCAD Contest 2025 Problem C benchmarks (ASAP7).

Whittled to: 4 instances (2 single-height, 2 multi-height SRAMs at same X position), 1 net, 51KB archive.

Root cause

In legalize_shift.cxx, the topological sort builds a dependency graph from ALL row segments. Multi-height cells appear in segments across many rows (62 rows for these SRAMs). When a single-height cell sits inside the row span of two multi-height cells, the ordering differs per row:

• In the SRAM's bottom row segment: [single-height, SRAM_A, SRAM_B]
• In a higher row segment: [SRAM_A, SRAM_B, single-height]

This creates a 3-node cycle: single → SRAM_A → SRAM_B → single, making the topological sort fail.

Proposed fix

Only add ordering edges from a cell's bottom (primary) row. Multi-height cells contribute edges only from the segment that corresponds to their bottom Y coordinate.

// In legalize_shift.cxx, inside the segment iteration loop:
const int rowId = mgr.getSegment(i)->getRowId();
const DbuY rowBottom = arch_->getRow(rowId)->getBottom();
// ...
// Only add an edge if this row is the bottom row for both cells.
if (prev->getBottom() != rowBottom || curr->getBottom() != rowBottom) {
  continue;
}

Verified

Both fixes tested on the full mempool_tile_wrap (182k cells) and NV_NVDLA_partition_c (167k cells) designs — improve_placement completes without errors.

Suggested Solution

No response

Additional Context

No response

[stefanottili]

Please test with a centered floor plan, it would be sad to break it again.
See #6704

[oharboe]

Please test with a centered floor plan, it would be sad to break it again. See #6704

If there is no test case, expect it to break.

[stefanottili]

There is a testcase, but it has not been added to the OR CI.
And it might be better to create a smaller one with multi-height cells.

[oharboe]

There is a testcase, but it has not been added to the OR CI. And it might be better to create a smaller one with multi-height cells.

Implement it in bazel-orfs and bazelisk test ... will automatically do it in CI, with no effort from the overworked OpenROAD CI team.

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 21 days if no further activity occurs. Remove the Stale label or comment to keep it open.

[gudeh]

Hi @oharboe, I was tracking the issues related to this one but I am not sure I was able to fully understand what happens.

The design you provided here finishes nicely if the two macros are set as FIXED, instead of PLACED. Maybe the real issue is just to provide a way for DPL be protected against this "user error".

[oharboe]

Sorry, dont really know what is going on here....