Tetris Legalization

The idea

Global placement ends with cells hovering in continuous positions, overlapping freely. Tetris legalization makes them legal with the simplest scheme that works. Sort all cells, usually left to right by their global x-coordinate. Process them in order; for each cell, scan candidate rows near its desired y, find in each the leftmost legal free interval at or right of the frontier, and commit the cell to the position minimizing its displacement. Because cells are placed in sorted order and each row fills monotonically, bookkeeping is a per-row frontier pointer: the pass runs in near-linear time, and the falling-blocks feel of cells sliding into the next free slot earned the name.

Trade-offs

Speed and reliability are the method's strengths: it always terminates, handles any mess the global placer emits, and is trivial to implement correctly. The weakness is quality: decisions are greedy and irrevocable, so a locally convenient slot for an early cell can force a chain of large displacements later, and wirelength damage concentrates unpredictably. In dense designs the frontier can also drift rightward, smearing the placement. Hence the standard pairing: Tetris (or a sibling) for a fast first legalization, then Abacus-style or window-based refinement to repair the damage.

Where you meet it today

As the quick legalizer inside countless flows and teaching codebases, as the standard 'baseline legalizer' in papers, and conceptually whenever someone needs any-legal-solution-now before optimizing.