[LICM] Ignore AA tags on conditional stores in scalar promotion.

Project: llvm/llvm-project | Language: C++ | Concepts: compiler-internals, memory-management, refactoring | Difficulty: senior
Link: https://github.com/llvm/llvm-project/pull/218031

The problem

When LLVM's Loop Invariant Code Motion (LICM) pass performs scalar promotion, it tries to move stores out of loops. However, it was incorrectly using Alias Analysis (AA) metadata tags for aliasing checks even on stores that are only conditionally executed inside the loop. This is unsound: AA tags are only valid for operations that actually execute at runtime, but the promoted store is always executed (unconditional) after the loop. This could lead to incorrect optimization decisions and miscompilations.

Why it's non-trivial

A naive fix would just strip AA tags from the new store, but the alias analysis used to decide whether promotion is safe was still considering the tags from the original, conditional store. This subtlety means that just removing tags from the output isn't enough: the analysis itself must ignore AA tags for stores that aren't guaranteed to execute.

The approach

1. Add a new API to AliasSetTracker to add stores without AA tags:

+  LLVM_ABI void addWithoutAATags(StoreInst *SI);

This adds a new method to AliasSetTracker so callers can explicitly add a store to the alias set, ignoring any AA tags.

2. Implement the new method:

+void AliasSetTracker::addWithoutAATags(StoreInst *SI) {
+  assert(!isStrongerThanMonotonic(SI->getOrdering()) &&
+         "Can't handle release stores here");
+  addMemoryLocation(MemoryLocation::get(SI).getWithoutAATags(),
+                    AliasSet::ModAccess);
+}

This method asserts that the store isn't a release (strong ordering), then strips the AA tags from the memory location before adding it to the alias set.

3. Update the scalar promotion candidate collection to use the new method for conditional stores:

-      AST.add(I);
+      if (StoreInst *SI = dyn_cast<StoreInst>(I);
+          SI && !SafetyInfo->isGuaranteedToExecute(*SI, DT, L)) {
+        // ... explanation ...
+        AST.addWithoutAATags(SI);
+      } else {
+        AST.add(I);
+      }

Now, when collecting stores that are candidates for promotion, if the store is not guaranteed to execute on every iteration (i.e., it's conditional), the code uses addWithoutAATags so the analysis ignores AA tags for aliasing checks. Only stores that always execute keep their tags for analysis.

4. Move monotonicity checks earlier:

+      if (isStrongerThanMonotonic(SI->getOrdering()))
+        return false;

This ensures that only stores/loads with at most monotonic ordering are considered for promotion, matching the assertion in addWithoutAATags.

5. Add a regression test:

A new test in scalar-promote.ll exercises a loop with conditional stores with AA tags, ensuring the transformation is now correct.

From the review thread

No notable review discussion on this PR.

Takeaways

• Alias analysis metadata (like AA tags) must only be used for operations that are guaranteed to execute. Using them for speculatively executed or unconditional stores can lead to unsound optimizations.
• When refactoring analysis code, ensure that the safety conditions for using metadata are enforced at both the transformation and analysis phases. Stripping tags from the output is not enough if the analysis still uses them.
• APIs should make it explicit when metadata is ignored. Introducing methods like addWithoutAATags makes the intent clear and helps prevent subtle bugs.