Fangrui Song 46bb3789ef [ScheduleDAG] Avoid duplicate worklist entries in ComputeDepth/ComputeHeight. NFC (#192023) ...

The old loop pushed every not-current predecessor in one sweep, so on
diamond-shaped DAGs a predecessor could be pushed while still on the
stack. Measured on clang -O2 -c sqlite3.i with the old algorithm
instrumented: ComputeDepth had 10.8% duplicate pushes (21.4% of calls
hit the issue).

Rewrite as an iterative post-order DFS that pushes one predecessor at a
time and breaks.

2026-04-22 22:40:32 -07:00

22 KiB

Raw Permalink Blame History

View Raw