[ADCE] Preserve MemorySSA if only debug instructions are removed

[uabelho]

Summary

As we've seen in
https://github.com/llvm/llvm-project/issues/58285
throwing away MemorySSA when only debug instructions are removed can lead
to different code when debug info is present or not present.

This is the second attempt at fixing the problem. The first one was
https://reviews.llvm.org/D145051
which was reverted due to a 15% compile time regression for tramp3d-v4
in NewPM-ReleaseLTO-g.

llvm/lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
struct BlockInfoType {
   /// Post-order numbering of reverse control flow graph.
   unsigned PostOrder;
 
   bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }
 };
 
 struct ADCEChanged {
   bool ChangedAnything = false;
+  bool ChangedNonDebugInstr = false;
   bool ChangedControlFlow = false;
 };
 
 class AggressiveDeadCodeElimination {
   Function &F;
 
   // ADCE does not use DominatorTree per se, but it updates it to preserve the
   // analysis.
if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
       if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII))
         if (!at::getAssignmentInsts(DAI).empty())
           continue;
       // Check if the scope of this variable location is alive.
       if (AliveScopes.count(DII->getDebugLoc()->getScope()))
         continue;
 
       // Fallthrough and drop the intrinsic.
+    } else {
+      Changed.ChangedNonDebugInstr = true;
     }
 
     // Prepare to delete.
     Worklist.push_back(&I);
     salvageDebugInfo(I);
   }
 
   for (Instruction *&I : Worklist)
PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
   auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
   ADCEChanged Changed =
       AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination();
   if (!Changed.ChangedAnything)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
-  if (!Changed.ChangedControlFlow)
+  if (!Changed.ChangedControlFlow) {
     PA.preserveSet<CFGAnalyses>();
+    if (!Changed.ChangedNonDebugInstr) {
+      // Only removing debug instructions does not affect MemorySSA.
+      //
+      // Therefore we preserve MemorySSA when only removing debug instructions
+      // since otherwise later passes may behave differently which then makes
+      // the presence of debug info affect code generation.
+      PA.preserve<MemorySSAAnalysis>();
+    }
+  }
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<PostDominatorTreeAnalysis>();
 
   return PA;
 }
 
 namespace {
 

llvm/test/Transforms/ADCE/preserve-memoryssa-if-only-remove-debug.ll

+; RUN: opt -passes='require<memoryssa>,adce' -o - -S -debug-pass-manager < %s 2>&1 | FileCheck %s
+
+; ADCE should remove the dbg.declare in test1, but it should preserve
+; MemorySSA since it only removed a debug instruction.
+
+; Invalidating MemorySSA when only removing debug instructions may lead
+; to different code with/without debug info present.
+; In
+;  https://github.com/llvm/llvm-project/issues/58285
+; we saw how ADCE removed a dbg.declare, invalidated all analyses, and later
+; DSE behaved in some way. Without the dbg.declare in the input ADCE kept
+; analysis info, and DSE behaved differently.
+
+; CHECK: Running analysis: MemorySSAAnalysis on test1
+; CHECK: Running pass: ADCEPass on test1 (1 instruction)
+; CHECK-NOT: Invalidating analysis: MemorySSAAnalysis on test1
+
+; In test2 ADCE also removes an instruction, but since we remove a non-debug
+; instruction as well we invalidate several analyses, including MemorySSA.
+
+; CHECK: Running analysis: MemorySSAAnalysis on test2
+; CHECK: Running pass: ADCEPass on test2 (2 instructions)
+; CHECK: Invalidating analysis: MemorySSAAnalysis on test2
+; CHECK: Running pass: PrintModulePass
+
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i16 0
+
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i16 0
+
+define i16 @test1() {
+entry:
+  call void @llvm.dbg.declare(metadata ptr undef, metadata !4, metadata !DIExpression()), !dbg !16
+  ret i16 0
+}
+
+define i16 @test2() {
+entry:
+  %dead = add i16 1, 2
+  ret i16 0
+}
+
+; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #0
+
+attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
+
+!llvm.dbg.cu = !{}
+!llvm.module.flags = !{!0, !1, !2, !3}
+
+!0 = !{i32 7, !"Dwarf Version", i32 4}
+!1 = !{i32 2, !"Debug Info Version", i32 3}
+!2 = !{i32 1, !"wchar_size", i32 1}
+!3 = !{i32 7, !"frame-pointer", i32 2}
+!4 = !DILocalVariable(name: "w", scope: !5, file: !6, line: 18, type: !11)
+!5 = distinct !DILexicalBlock(scope: !7, file: !6, line: 18, column: 8)
+!6 = !DIFile(filename: "foo2.c", directory: "/llvm")
+!7 = distinct !DISubprogram(name: "test1", scope: !6, file: !6, line: 14, type: !8, scopeLine: 14, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !10)
+!8 = !DISubroutineType(types: !9)
+!9 = !{}
+!10 = distinct !DICompileUnit(language: DW_LANG_C99, file: !6, producer: "clang version 16.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, globals: !9, splitDebugInlining: false, nameTableKind: None)
+!11 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint64_t", file: !12, line: 60, baseType: !13)
+!12 = !DIFile(filename: "/include/sys/_stdint.h", directory: "")
+!13 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uint64_t", file: !14, line: 108, baseType: !15)
+!14 = !DIFile(filename: "/include/machine/_default_types.h", directory: "")
+!15 = !DIBasicType(name: "unsigned long long", size: 64, encoding: DW_ATE_unsigned)
+!16 = !DILocation(line: 18, column: 8, scope: !5)
 No newline at end of file