[LoopInterchange] Swap preheader contents before rebuilding LCSSA

Project: llvm/llvm-project | Language: C++ | Concepts: refactoring, error-handling, testing-strategy | Difficulty: senior
Link: https://github.com/llvm/llvm-project/pull/218468

The problem

When interchanging nested loops, the loop interchange pass must move reduction PHIs and rebuild LCSSA (Loop-Closed SSA) form. Previously, the pass swapped the contents of the inner and outer preheaders only after these steps. This could leave a reduction seed value (initialized in the inner preheader) stranded below its use, resulting in dominance violations and breaking LCSSA reconstruction.

Why it's non-trivial

A naive fix might simply swap the preheader contents at any point, but the order of operations is crucial: swapping too late means that LCSSA reconstruction sees IR where definitions do not dominate their uses, leading to broken SSA form. The transformation must ensure that all values are defined in blocks that dominate their uses before LCSSA is rebuilt.

The approach

1. Move the preheader swap before LCSSA rebuild

Previously, the code swapped the preheader contents in a separate method (adjustLoopLinks), which was called after LCSSA rebuilding. The fix is to move the swap earlier, directly into adjustLoopBranches, before LCSSA is rebuilt:

+  // Swap the preheader contents before rebuilding LCSSA below, so that a
+  // reduction init defined in the inner preheader is relocated into the new
+  // outer preheader and dominates its use on the reduction PHI's seed edge.
+  swapBBContents(OuterLoop->getLoopPreheader(), InnerLoop->getLoopPreheader());

This ensures that any reduction seed defined in the inner preheader is moved to the correct place before LCSSA is rebuilt, preserving dominance.

2. Remove now-redundant code

With the swap moved, the adjustLoopLinks method became a thin wrapper and was removed:

-void LoopInterchangeTransform::adjustLoopLinks() {
-  // Adjust all branches in the inner and outer loop.
-  adjustLoopBranches();
-
-  // We have interchanged the preheaders so we need to interchange the data in
-  // the preheaders as well. This is because the content of the inner
-  // preheader was previously executed inside the outer loop.
-  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
-  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
-  swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);
-}

This cleans up the code by inlining the logic and removing an unnecessary function.

3. Update call sites to use the new logic

The main transformation now calls adjustLoopBranches() directly:

-  adjustLoopLinks();
+  adjustLoopBranches();

This reflects the refactoring and ensures the correct sequence of operations.

4. Add a regression test

A new test file ensures that the reduction seed is relocated properly and that LCSSA verification passes:

+; RUN: opt < %s -passes=loop-interchange -verify-loop-lcssa -S | FileCheck %s
+; ... test IR omitted for brevity ...

This verifies that the bug is fixed and prevents regressions.

From the review thread

No notable review discussion on this PR.

Takeaways

• Order of transformations matters: When restructuring control flow, always ensure that definitions dominate their uses before rebuilding SSA form or related analyses.
• Refactor when logic becomes redundant: If a helper function becomes a thin wrapper after a change, inline or remove it to keep the codebase clean.
• Add targeted regression tests: When fixing subtle bugs, add tests that would have failed before the fix to catch future regressions.