WIP: Prototype of DSE optimizations for -ftrivial-auto-var-init

[vitalybuka]

Summary

I don't want to invest into improving this patch. I will extract useful parts
and send them for review using this one as a benchmark reference.

Coroutines tests do not like pass structure so I disable the to figure out
later.

If you try this patch and find cases which module level DSE should handle,
and this one does not, especially -ftrivial-auto-var-init=patter related, please
share them with me.

[jfb]

Hello! I'm still interested in this, have you been able to make any progress?

[vitalybuka]

Bugfixes

[glider]

Vitaly, can you please rebase the patch?
As far as I can see, you've submitted parts of it already.
(not that I can't resolve the conflicts locally, but keeping it up-to-date may save others some time)

[glider]

llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp

21

error: zero-size array ‘llvm::GUIDS_LOOKUP’

Can you please provide an example of DeadStoreEliminationExpGlobalGUIDListGen.h? The instruction seems insufficient.

28

Ditto.

[glider]

llvm/lib/Transforms/Scalar/DeadStoreEliminationExp.cpp

710

This cast fails in the following case:

%21 = call i64 @probe_kernel_read(i8* nonnull %9, i8* %20, i64 8) #10, !dbg !7740

, where the callee is declared as:

@probe_kernel_read = weak hidden alias i64 (i8*, i8*, i64), i64 (i8*, i8*, i64)* @__probe_kernel_read

When building Android kernel with LTO enabled, the gold plugin crashes on an assertion.

[glider]

llvm/lib/Transforms/Scalar/DeadStoreEliminationExp.cpp

557

An assertion fires here on the Android kernel:

aarch64-linux-android-ld.gold: /usr/local/google/src/llvm-git-monorepo/llvm/lib/IR/ConstantRange.cpp:54: llvm::ConstantRange::ConstantRange(llvm::APInt, llvm::APInt): Assertion `(Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && "Lower == Upper, but they aren't min or max value!"' failed.

For some reason the (APInt, APInt) version of the constructor is being invoked.
Probably PointerSizeInBits should be declared as int32_t here and in findDeadStores()

564

I'm seeing a case in which Range.getLower() is 20179 and LS.getValue() is 0.

[asbirlea]

llvm/include/llvm/Analysis/MemorySSA.h

1109 ↗

(On Diff #206365)

Could changes in this file be landed separately?
They seem unrelated and not in need of review.

[vitalybuka]

llvm/include/llvm/Analysis/MemorySSA.h

1109 ↗

(On Diff #206365)

It's already there r364247, i didn't rebase the patch after submit.

llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp

28

These files should be empty. Raw diff https://reviews.llvm.org/file/data/o6sk6gw2gqs4u4pmodrn/PHID-FILE-s6c6nsofxnqekkcvzdzs/D61879.diff already contains them.
It's ThinLTO replacement experiments. They don't improve results enough, so I didn't bother to create real ThinLTO stuff. Anyway it is not needed for full LTO.

[vitalybuka]

Rebase only

[glider]

llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp

28

$ ninja -j64 check-clang
...
/usr/local/google/src/llvm-git-monorepo/llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp:20:32: error: zero-size array ‘llvm::GUIDS_LOOKUP’
 static const GlobalValue::GUID GUIDS_LOOKUP[] = {
                                ^~~~~~~~~~~~
/usr/local/google/src/llvm-git-monorepo/llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp:26:19: error: zero-size array ‘llvm::GlobalArgumentMemAccess’
 static const char GlobalArgumentMemAccess[] = {
                   ^~~~~~~~~~~~~~~~~~~~~~~

Am I doing something wrong? Looks like empty files aren't enough.
I've fixed the problem by putting "0" into each file, but it's strange it works differently for us.

[vitalybuka]

llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp

28

You must be using LLVM_ENABLE_WERROR?

[vitalybuka]

fix LTO on kernel

[glider]

Vitaly, what's the current status of these patches? What's your plan on submitting them?

[vitalybuka]

Fix https://godbolt.org/z/-PinQP

[glider]

In D61879#1621423, @vitalybuka wrote:

Fix https://godbolt.org/z/-PinQP

Please consider adding a test.

clang/test/CodeGenCXX/member-function-pointer-calls.cpp

 // RUN: %clang_cc1 %s -triple=x86_64-apple-darwin10 -emit-llvm -O3 -fno-experimental-new-pass-manager  -o - | FileCheck %s --check-prefixes=CHECK,CHECK-LEGACY
 // RUN: %clang_cc1 %s -triple=x86_64-apple-darwin10 -emit-llvm -O3 -fexperimental-new-pass-manager  -o - | FileCheck %s --check-prefixes=CHECK,CHECK-NEWPM
 // RUN: %clang_cc1 %s -triple=x86_64-windows-gnu -emit-llvm -o - | FileCheck %s -check-prefix MINGW64
 struct A {
   virtual int vf1() { return 1; }
   virtual int vf2() { return 2; }
 };
 
 int f(A* a, int (A::*fp)()) {
   return (a->*fp)();
 }
 
 // CHECK-LABEL: define i32 @_Z2g1v()
 // CHECK-LEGACY: ret i32 1
-// CHECK-NEWPM: [[A:%.*]] = alloca %struct.A, align 8
-// CHECK-NEWPM: [[TMP:%.*]] = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
-// CHECK-NEWPM: store i32 (...)** bitcast (i8** getelementptr inbounds ({ [4 x i8*] }, { [4 x i8*] }* @_ZTV1A, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** [[TMP]], align 8
 // CHECK-NEWPM: [[RET:%.*]] = call i32 @_ZN1A3vf1Ev(%struct.A* nonnull %a) #2
 // CHECK-NEWPM: ret i32 [[RET]]
 // MINGW64-LABEL: define dso_local i32 @_Z2g1v()
 // MINGW64: call i32 @_Z1fP1AMS_FivE(%struct.A* %{{.*}}, { i64, i64 }* %{{.*}})
 int g1() {
   A a;
   return f(&a, &A::vf1);
 }

clang/test/CodeGenCXX/union-tbaa2.cpp

-// RUN: %clang_cc1 %s -O2 -std=c++11 -triple x86_64-unknown-linux-gnu -target-cpu x86-64 -target-feature +sse4.2 -target-feature +avx -emit-llvm -o - | FileCheck %s
+// RUN: %clang_cc1 %s -O1 -std=c++11 -triple x86_64-unknown-linux-gnu -target-cpu x86-64 -target-feature +sse4.2 -target-feature +avx -emit-llvm -o - | FileCheck %s
 
 // Testcase from llvm.org/PR32056
 
 extern "C" int printf (const char *__restrict __format, ...);
 
 typedef double __m256d __attribute__((__vector_size__(32)));
 
 static __inline __m256d __attribute__((__always_inline__, __nodebug__,

llvm/include/llvm/InitializePasses.h

 void initializeControlHeightReductionLegacyPassPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
 void initializeDSELegacyPassPass(PassRegistry&);
+void initializeDSEELegacyPassPass(PassRegistry &);
 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDelinearizationPass(PassRegistry&);
 void initializeDemandedBitsWrapperPassPass(PassRegistry&);
 void initializeDependenceAnalysisPass(PassRegistry&);
 void initializeDependenceAnalysisWrapperPassPass(PassRegistry&);
 void initializeDetectDeadLanesPass(PassRegistry&);

 void initializeSinkingLegacyPassPass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeSlotIndexesPass(PassRegistry&);
 void initializeSpeculativeExecutionLegacyPassPass(PassRegistry&);
 void initializeSpillPlacementPass(PassRegistry&);
 void initializeStackColoringPass(PassRegistry&);
 void initializeStackMapLivenessPass(PassRegistry&);
 void initializeStackProtectorPass(PassRegistry&);
+void initializeArgumentAccessInfoLegacyPassPass(PassRegistry &);
 void initializeStackSafetyGlobalInfoWrapperPassPass(PassRegistry &);
 void initializeStackSafetyInfoWrapperPassPass(PassRegistry &);
 void initializeStackSlotColoringPass(PassRegistry&);
 void initializeStraightLineStrengthReducePass(PassRegistry&);
 void initializeStripDeadDebugInfoPass(PassRegistry&);
 void initializeStripDeadPrototypesLegacyPassPass(PassRegistry&);
 void initializeStripDebugDeclarePass(PassRegistry&);
 void initializeStripGCRelocatesPass(PassRegistry&);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createControlHeightReductionLegacyPass();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadInstEliminationPass();
       (void) llvm::createDeadStoreEliminationPass();
+      (void) llvm::createDeadStoreEliminationExpPass();
       (void) llvm::createDependenceAnalysisWrapperPass();
       (void) llvm::createDomOnlyPrinterPass();
       (void) llvm::createDomPrinterPass();
       (void) llvm::createDomOnlyViewerPass();
       (void) llvm::createDomViewerPass();
       (void) llvm::createGCOVProfilerPass();
       (void) llvm::createPGOInstrumentationGenLegacyPass();
       (void) llvm::createPGOInstrumentationUseLegacyPass();

llvm/include/llvm/Transforms/Scalar.h

 
 //===----------------------------------------------------------------------===//
 //
 // DeadStoreElimination - This pass deletes stores that are post-dominated by
 // must-aliased stores and are not loaded used between the stores.
 //
 FunctionPass *createDeadStoreEliminationPass();
 
+//===----------------------------------------------------------------------===//
+//
+// DeadStoreEliminationExp - This pass deletes more stores.
+//
+FunctionPass *createDeadStoreEliminationExpPass();
 
 //===----------------------------------------------------------------------===//
 //
 // CallSiteSplitting - This pass split call-site based on its known argument
 // values.
 FunctionPass *createCallSiteSplittingPass();
 
 //===----------------------------------------------------------------------===//

llvm/include/llvm/Transforms/Scalar/DeadStoreEliminationExp.h

+//===- DeadStoreElimination.h - Fast Dead Store Elimination -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a dead store elimination to local allocas.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATIONEXP_H
+#define LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATIONEXP_H
+
+#include "llvm/IR/ConstantRange.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/PassManager.h"
+#include <set>
+
+namespace llvm {
+
+class Function;
+
+class SparseSet {
+public:
+  using T = int64_t;
+  static constexpr T Min = std::numeric_limits<T>::min();
+  static constexpr T Max = std::numeric_limits<T>::max();
+
+private:
+  unsigned PointerSize;
+  // ConstantRange CR;
+
+  SmallVector<T, 10> Intervals;
+
+  friend raw_ostream &operator<<(raw_ostream &, const SparseSet &);
+  friend std::string toString(const SparseSet &);
+  friend SparseSet fromStringSparseSet(const char *&P);
+
+public:
+  explicit SparseSet(unsigned PointerSize, bool Set)
+      : PointerSize(PointerSize) {
+    if (Set)
+      Intervals.push_back(Min);
+  };
+
+  explicit SparseSet(APInt Begin, APInt End)
+      : PointerSize(Begin.getBitWidth()) {
+    T B = Begin.getSExtValue();
+    T E = End.getSExtValue();
+    assert(B < E);
+    Intervals.push_back(B);
+    Intervals.push_back(E);
+  };
+
+  unsigned getBitWidth() const { return PointerSize; }
+  SparseSet difference(const SparseSet &Other) const;
+  SparseSet unionWith(const SparseSet &Other) const;
+  SparseSet intersectWith(const SparseSet &Other) const;
+  bool addCanOverflow(APInt A) const;
+  SparseSet add(APInt A) const;
+
+  SparseSet getFirstRange() const;
+
+  T getLower() const {
+    if (Intervals.empty())
+      return 0;
+    return Intervals.front();
+  }
+
+  T getUpper() const {
+    if (Intervals.empty())
+      return 0;
+
+    return (Intervals.size() % 2 == 0 && Intervals.back() < Max)
+               ? Intervals.back()
+               : Max;
+  }
+
+  bool IsSingleRange() const {
+    return Intervals.size() <= 2;
+  }
+
+  bool contains(const SparseSet &Other) const {
+    return intersectWith(Other) == Other;
+  }
+
+  bool operator==(const SparseSet &Other) const {
+    return Intervals == Other.Intervals && PointerSize == Other.PointerSize;
+  }
+
+  bool operator!=(const SparseSet &Other) const { return !(*this == Other); }
+
+  bool isEmptySet() const { return Intervals.empty(); }
+};
+
+raw_ostream &operator<<(raw_ostream &os, const SparseSet &SS);
+
+struct ArgumentAccessInfo {
+  bool Leak = true;
+  SparseSet CanRead;
+  SparseSet MustWrite;
+
+  ArgumentAccessInfo(unsigned PointerSizeInBits)
+      : CanRead(PointerSizeInBits, true), MustWrite(PointerSizeInBits, false) {}
+};
+using ArgumentMemAccess =
+    std::map<GlobalValue::GUID, std::vector<ArgumentAccessInfo>>;
+
+/// This class implements a dead store elimination to local allocas.
+class DSEEPass : public PassInfoMixin<DSEEPass> {
+  ArgumentMemAccess AAI;
+  std::set<GlobalValue::GUID> GUIDS;
+
+public:
+  DSEEPass();
+  ~DSEEPass();
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATIONEXP_H

llvm/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeSCEVAAWrapperPassPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);
   initializeStackSafetyGlobalInfoWrapperPassPass(Registry);
+  initializeArgumentAccessInfoLegacyPassPass(Registry);
   initializeStackSafetyInfoWrapperPassPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAAWrapperPassPass(Registry);
   initializeScopedNoAliasAAWrapperPassPass(Registry);
   initializeLCSSAVerificationPassPass(Registry);
   initializeMemorySSAWrapperPassPass(Registry);
   initializeMemorySSAPrinterLegacyPassPass(Registry);
 }

llvm/lib/IR/AsmWriter.cpp

if (const auto *Relocate = dyn_cast<GCRelocateInst>(&V))
     printGCRelocateComment(*Relocate);
 
   if (AnnotationWriter)
     AnnotationWriter->printInfoComment(V, Out);
 }
 
 static void maybePrintCallAddrSpace(const Value *Operand, const Instruction *I,
                                     raw_ostream &Out) {
+  if (!Operand)
+    return;
   // We print the address space of the call if it is non-zero.
   unsigned CallAddrSpace = Operand->getType()->getPointerAddressSpace();
   bool PrintAddrSpace = CallAddrSpace != 0;
   if (!PrintAddrSpace) {
     const Module *Mod = getModuleFromVal(I);
     // We also print it if it is zero but not equal to the program address space
     // or if we can't find a valid Module* to make it possible to parse
     // the resulting file even without a datalayout string.

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
 #include "llvm/Transforms/Scalar/BDCE.h"
 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
 #include "llvm/Transforms/Scalar/ConstantHoisting.h"
 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
 #include "llvm/Transforms/Scalar/DCE.h"
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
+#include "llvm/Transforms/Scalar/DeadStoreEliminationExp.h"
 #include "llvm/Transforms/Scalar/DivRemPairs.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/Float2Int.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/GuardWidening.h"
 #include "llvm/Transforms/Scalar/IVUsersPrinter.h"
 #include "llvm/Transforms/Scalar/IndVarSimplify.h"
 #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
   FPM.addPass(InstCombinePass());
   invokePeepholeEPCallbacks(FPM, Level);
 
   // Re-consider control flow based optimizations after redundancy elimination,
   // redo DCE, etc.
   FPM.addPass(JumpThreadingPass());
   FPM.addPass(CorrelatedValuePropagationPass());
   FPM.addPass(DSEPass());
+  if (Level != O1)
+    FPM.addPass(DSEEPass());
   FPM.addPass(createFunctionToLoopPassAdaptor(
       LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap),
       DebugLogging));
 
   for (auto &C : ScalarOptimizerLateEPCallbacks)
     C(FPM, Level);
 
   // Finally, do an expensive DCE pass to catch all the dead code exposed by

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("break-crit-edges", BreakCriticalEdgesPass())
 FUNCTION_PASS("callsite-splitting", CallSiteSplittingPass())
 FUNCTION_PASS("consthoist", ConstantHoistingPass())
 FUNCTION_PASS("chr", ControlHeightReductionPass())
 FUNCTION_PASS("correlated-propagation", CorrelatedValuePropagationPass())
 FUNCTION_PASS("dce", DCEPass())
 FUNCTION_PASS("div-rem-pairs", DivRemPairsPass())
 FUNCTION_PASS("dse", DSEPass())
+FUNCTION_PASS("dsee", DSEEPass())
 FUNCTION_PASS("dot-cfg", CFGPrinterPass())
 FUNCTION_PASS("dot-cfg-only", CFGOnlyPrinterPass())
 FUNCTION_PASS("early-cse", EarlyCSEPass(/*UseMemorySSA=*/false))
 FUNCTION_PASS("early-cse-memssa", EarlyCSEPass(/*UseMemorySSA=*/true))
 FUNCTION_PASS("ee-instrument", EntryExitInstrumenterPass(/*PostInlining=*/false))
 FUNCTION_PASS("make-guards-explicit", MakeGuardsExplicitPass())
 FUNCTION_PASS("post-inline-ee-instrument", EntryExitInstrumenterPass(/*PostInlining=*/true))
 FUNCTION_PASS("gvn-hoist", GVNHoistPass())

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
 
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
   MPM.add(createJumpThreadingPass());         // Thread jumps
   MPM.add(createCorrelatedValuePropagationPass());
   MPM.add(createDeadStoreEliminationPass());  // Delete dead stores
+  if (OptLevel > 1)
+    MPM.add(createDeadStoreEliminationExpPass());
   MPM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
 
   addExtensionsToPM(EP_ScalarOptimizerLate, MPM);
 
   if (RerollLoops)
     MPM.add(createLoopRerollPass());
 
   MPM.add(createAggressiveDCEPass());         // Delete dead instructions
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   PM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
   PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
   PM.add(NewGVN ? createNewGVNPass()
                 : createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.
   PM.add(createDeadStoreEliminationPass());
+  if (OptLevel > 1)
+    PM.add(createDeadStoreEliminationExpPass());
 
   // More loops are countable; try to optimize them.
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());
   if (EnableLoopInterchange)
     PM.add(createLoopInterchangePass());
 
   // Unroll small loops

llvm/lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_library(LLVMScalarOpts
   ADCE.cpp
   AlignmentFromAssumptions.cpp
   BDCE.cpp
   CallSiteSplitting.cpp
   ConstantHoisting.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
+  DeadStoreEliminationExp.cpp
+  DeadStoreEliminationExpGlobal.cpp
   DivRemPairs.cpp
   EarlyCSE.cpp
   FlattenCFGPass.cpp
   Float2Int.cpp
   GuardWidening.cpp
   GVN.cpp
   GVNHoist.cpp
   GVNSink.cpp

llvm/lib/Transforms/Scalar/DeadStoreEliminationExp.cpp

+//===- DeadStoreEliminationExp.cpp - Alloca Dead Store Elimination ---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a dead store elimination to local allocas.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/DeadStoreEliminationExp.h"
+#include "DeadStoreEliminationExpGlobal.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/BinaryByteStream.h"
+#include "llvm/Support/BinaryStreamWriter.h"
+#include "llvm/Support/Compression.h"
+#include "llvm/Support/DebugCounter.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "dsee"
+
+namespace {
+
+// Writes are both StoreInstr and MemIntrinsic.
+
+STATISTIC(NumMemWritesAny, "Number of memory writes");
+STATISTIC(NumMemWrites, "Number of interesting memory writes");
+STATISTIC(NumMemWritesSkipWithAlloca,
+          "Number of writes skipped with entire alloca");
+STATISTIC(NumMemWritesSkip, "Number of skipped writes");
+STATISTIC(NumMemWritesToAnalize, "Number of writes to analyze");
+
+STATISTIC(NumMemWritesDeleted, "Number of deleted writes");
+STATISTIC(NumOtherDeleted, "Number of other deleted instructions");
+
+STATISTIC(NumStoreInstrToShrink, "Number of stores which can be shrinked");
+
+STATISTIC(NumMemIntrinsicToShrink,
+          "Number of intrinsics which can be shrinked");
+STATISTIC(NumMemIntrinsicShrinked, "Number of shrinked intrinsics");
+STATISTIC(NumAllocation, "Number of allocations");
+STATISTIC(NumAlloca, "Number of allocas");
+
+DEBUG_COUNTER(DeadStoreEliminationExp, "dsee-alloca",
+              "Controls which instructions get delete");
+
+/// Rewrite an SCEV expression for a memory access address to an expression that
+/// represents offset from the given alloca.
+class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
+  const Value *AllocaPtr;
+
+public:
+  AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr)
+      : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {}
+
+  const SCEV *visit(const SCEV *Expr) {
+    // Only re-write the expression if the alloca is used in an addition
+    // expression (it can be used in other types of expressions if it's cast to
+    // an int and passed as an argument.)
+    if (!isa<SCEVAddRecExpr>(Expr) && !isa<SCEVAddExpr>(Expr) &&
+        !isa<SCEVUnknown>(Expr))
+      return Expr;
+    return SCEVRewriteVisitor<AllocaOffsetRewriter>::visit(Expr);
+  }
+
+  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+    // FIXME: look through one or several levels of definitions?
+    // This can be inttoptr(AllocaPtr) and SCEV would not unwrap
+    // it for us.
+    if (Expr->getValue() == AllocaPtr)
+      return SE.getZero(Expr->getType());
+    return Expr;
+  }
+};
+
+bool getAccessStart(ScalarEvolution &SE, Value *Addr, const Value *AI,
+                    ConstantRange *Range) {
+  if (!SE.isSCEVable(Addr->getType()))
+    return false;
+  AllocaOffsetRewriter Rewriter(SE, AI);
+  *Range = SE.getUnsignedRange(Rewriter.visit(SE.getSCEV(Addr)))
+               .zextOrTrunc(Range->getBitWidth());
+  return true;
+}
+
+bool NoUnderlyingObject(Value *V) {
+  if (!isa<User>(V) || isa<Constant>(V))
+    return true;
+  Instruction *I = dyn_cast<Instruction>(V);
+  assert(I);
+  switch (I->getOpcode()) {
+  case Instruction::ICmp:
+  case Instruction::FCmp:
+  case Instruction::Call:
+  case Instruction::ExtractElement:
+  case Instruction::InsertElement:
+  case Instruction::ShuffleVector:
+  case Instruction::ExtractValue:
+  case Instruction::InsertValue:
+  case Instruction::LandingPad:
+#define HANDLE_TERM_INST(N, OPC, CLASS) case Instruction::OPC:
+#define HANDLE_MEMORY_INST HANDLE_TERM_INST
+#define HANDLE_BINARY_INST HANDLE_TERM_INST
+#define HANDLE_FUNCLETPAD_INST HANDLE_TERM_INST
+#include "llvm/IR/Instruction.def"
+#undef HANDLE_TERM_INST
+#undef HANDLE_MEMORY_INST
+#undef HANDLE_BINARY_INST
+#undef HANDLE_FUNCLETPAD_INST
+    return true;
+  }
+
+  return false;
+}
+
+bool NeedsEscapedObject(Instruction *I) {
+  assert(I);
+  switch (I->getOpcode()) {
+  case Instruction::ICmp:
+  case Instruction::FCmp:
+  case Instruction::ExtractElement:
+  case Instruction::InsertElement:
+  case Instruction::ShuffleVector:
+  case Instruction::ExtractValue:
+  case Instruction::InsertValue:
+  case Instruction::LandingPad:
+  case Instruction::Store:
+  case Instruction::GetElementPtr:
+  case Instruction::Fence:
+  case Instruction::AtomicCmpXchg:
+  case Instruction::AtomicRMW:
+#define HANDLE_TERM_INST(N, OPC, CLASS) case Instruction::OPC:
+#define HANDLE_BINARY_INST HANDLE_TERM_INST
+#define HANDLE_CAST_INST HANDLE_TERM_INST
+#define HANDLE_FUNCLETPAD_INST HANDLE_TERM_INST
+#include "llvm/IR/Instruction.def"
+#undef HANDLE_TERM_INST
+#undef HANDLE_BINARY_INST
+#undef HANDLE_CAST_INST
+#undef HANDLE_FUNCLETPAD_INST
+    return false;
+  case Instruction::Load:
+  case Instruction::Call:
+    if (I->isLifetimeStartOrEnd() || isa<MemSetInst>(I))
+      return false;
+    return true;
+  }
+  return false;
+  errs() << I->getOpcode() << "\n";
+  errs() << *I << "\n";
+  assert(false);
+  abort();
+}
+
+bool IsReturn(const Instruction *I) {
+  assert(I);
+  if (I->getOpcode() == Instruction::Ret)
+    return true;
+  switch (I->getOpcode()) {
+#define HANDLE_TERM_INST(N, OPC, CLASS) case Instruction::OPC:
+#include "llvm/IR/Instruction.def"
+#undef HANDLE_TERM_INST
+    return false;
+  }
+  assert(false);
+  abort();
+}
+
+void findAllocasForValue(Value *V, SmallVectorImpl<Value *> &Objects,
+                         const DataLayout &DL) {
+  SmallPtrSet<Value *, 4> Visited;
+  SmallVector<Value *, 4> Worklist;
+  Worklist.push_back(V);
+  while (!Worklist.empty()) {
+    V = Worklist.pop_back_val();
+    if (!Visited.insert(V).second)
+      continue;
+
+    Value *U = GetUnderlyingObject(V, DL);
+    if (U != V) {
+      Worklist.push_back(U);
+    } else if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
+      Worklist.push_back(SI->getTrueValue());
+      Worklist.push_back(SI->getFalseValue());
+    } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
+      for (Value *IncValue : PN->incoming_values())
+        Worklist.push_back(IncValue);
+    } else if (CastInst *CI = dyn_cast<CastInst>(V)) {
+      Worklist.push_back(CI->getOperand(0));
+    } else if (!V->hasNUsesOrMore(1) || NoUnderlyingObject(V)) {
+      Objects.push_back(V);
+    } else {
+      errs() << "UNDERLYING ERROR: " << *V << " \n";
+      abort();
+    }
+  }
+}
+
+raw_ostream &operator<<(raw_ostream &os,
+                        const SmallVector<SparseSet::T, 10> &SS) {
+  bool S = false;
+  bool F = true;
+  for (auto P : SS) {
+    if (S) {
+      os << "," << P << ")";
+    } else {
+      if (!F) {
+        F = false;
+        os << ",";
+      }
+      os << "[" << P;
+    }
+    S = !S;
+  }
+  if (S) {
+    uint64_t M = SparseSet::Max;
+    ++M;
+    os << "," << M << ")";
+  }
+  return os;
+}
+
+template <class T, class Fn>
+SmallVector<T, 10> ApplySetFn(const SmallVector<T, 10> &AA,
+                              const SmallVector<T, 10> &BB, Fn fn) {
+  SmallVector<T, 10> R;
+  auto A = AA.begin();
+  auto B = BB.begin();
+
+  bool SA = false;
+  bool SB = false;
+  bool S = false;
+  while (A != AA.end() || B != BB.end()) {
+    T E;
+    if (A != AA.end() && (B == BB.end() || *A < *B)) {
+      SA = !SA;
+      E = *A;
+      ++A;
+    } else if (A == AA.end() || *A > *B) {
+      SB = !SB;
+      E = *B;
+      ++B;
+    } else {
+      E = *A;
+      SA = !SA;
+      ++A;
+      SB = !SB;
+      ++B;
+    }
+    bool NS = fn(SA, SB);
+    if (NS != S) {
+      assert(R.empty() || R.back() < E);
+      R.push_back(E);
+      S = NS;
+    }
+  }
+  return R;
+}
+
+struct MemAccessInfo {
+  MemAccessInfo(unsigned PointerSize)
+      : Load(PointerSize, false), Store(PointerSize, false),
+        Used(PointerSize, false), StoreLater(PointerSize, false) {
+    assert(PointerSize);
+    assert(Used.getBitWidth() == Store.getBitWidth());
+    assert(Used.getBitWidth() == Load.getBitWidth());
+  }
+
+  SparseSet getUsedForDefs() const {
+    assert(Used.getBitWidth() == Store.getBitWidth());
+    assert(Used.getBitWidth() == Load.getBitWidth());
+    auto R = Used.difference(Store).unionWith(Load);
+    assert(Used.getBitWidth() == R.getBitWidth());
+    return R;
+  }
+
+  bool updateUsed(const SparseSet &Range) {
+    assert(Used.getBitWidth() == Range.getBitWidth());
+    SparseSet NewRange = Range.unionWith(Used);
+    bool R = (NewRange != Used);
+    assert(NewRange.getBitWidth() == Used.getBitWidth());
+    Used = NewRange;
+    return R;
+  }
+  void updateLoad(const SparseSet &Range) { Load = Range.unionWith(Load); }
+  void updateStore(const SparseSet &Range) { Store = Range.unionWith(Store); }
+
+  SparseSet updateStoreLater(const SparseSet &Range) {
+    StoreLater = StoreLater.unionWith(Range);
+    return GetStoreLater();
+  }
+  void SetUsed(SparseSet U) {
+    assert(Used.getBitWidth() == U.getBitWidth());
+    Used = U;
+  }
+
+  void SetLoad(SparseSet U) {
+    assert(Load.getBitWidth() == U.getBitWidth());
+    Load = U;
+  }
+  void SetStore(SparseSet U) {
+    assert(Store.getBitWidth() == U.getBitWidth());
+    Store = U;
+  }
+
+  SparseSet GetDead() const { return Store.difference(Used); }
+
+  const SparseSet &GetLoad() const { return Load; }
+  const SparseSet &GetStore() const { return Store; }
+  const SparseSet &GetUsed() const { return Used; }
+
+  SparseSet GetStoreLater() const { return StoreLater.unionWith(Store); }
+
+  SparseSet GetGood() const { return Store.intersectWith(Used); }
+
+  void MakeVolatile() { updateUsed(Store); }
+
+  bool IsDeadStore() const {
+    return !Store.isEmptySet() && GetGood().isEmptySet();
+  }
+
+  bool IsPartiallyDeadStore() const {
+    // return !GetStore().isEmptySet();
+    return !GetDead().isEmptySet();
+  }
+
+private:
+  friend raw_ostream &operator<<(raw_ostream &, const MemAccessInfo &);
+  SparseSet Load;
+  SparseSet Store;
+  SparseSet Used;
+  SparseSet StoreLater;
+};
+
+raw_ostream &operator<<(raw_ostream &os, const MemAccessInfo &MAI) {
+  return os << "L:" << MAI.Load << ";S:" << MAI.Store << ";U:" << MAI.Used
+            << ";SL:" << MAI.StoreLater;
+}
+
+void UpdateUses(std::map<const MemoryAccess *, MemAccessInfo> &Infos) {
+  SmallVector<const MemoryAccess *, 8> WorkList;
+  for (auto &Inf : Infos) {
+    assert(Inf.first);
+    WorkList.push_back(Inf.first);
+  }
+
+  while (!WorkList.empty()) {
+    const MemoryAccess *MA = WorkList.pop_back_val();
+    assert(MA);
+    assert(Infos.count(MA));
+    const MemAccessInfo &Info = Infos.find(MA)->second;
+
+    SparseSet Used = Info.getUsedForDefs();
+
+    // int x = MA->defs_begin();
+    for (const MemoryAccess *Def :
+         make_range(MA->defs_begin(), MA->defs_end())) {
+      if (!Def)
+        continue;
+
+      auto Ins = Infos.emplace(Def, Used.getBitWidth());
+      MemAccessInfo &DefInfo = Ins.first->second;
+
+      LLVM_DEBUG(dbgs() << "PU: " << *MA << "->" << *Def << Used << "\n");
+      if (DefInfo.updateUsed(Used)) {
+        assert(Def);
+        WorkList.push_back(Def);
+      }
+    }
+  }
+}
+
+SparseSet
+UpdateLaterWrites(const Function &F, MemorySSA &MSSA,
+                  std::map<const MemoryAccess *, MemAccessInfo> &Infos) {
+
+  auto &Entry = Infos.find(MSSA.getLiveOnEntryDef())->second;
+  assert(Entry.GetStoreLater().isEmptySet());
+  const SparseSet EmptySet(Entry.GetStore().getBitWidth(), false);
+  // return EmptySet;
+
+  SparseSet R(Entry.GetStore().getBitWidth(), true);
+
+  // Assume missing block is full set.
+  std::map<const BasicBlock *, SparseSet> Sets;
+  SmallVector<const BasicBlock *, 8> WorkList;
+  WorkList.push_back(&F.getEntryBlock());
+  Sets.emplace(WorkList.back(), EmptySet);
+
+  while (!WorkList.empty()) {
+    const BasicBlock *B = WorkList.pop_back_val();
+    SparseSet &SS = Sets.find(B)->second;
+    if (const MemorySSA::DefsList *Defs = MSSA.getBlockDefs(B)) {
+      for (const MemoryAccess &Def : *Defs) {
+        auto I = Infos.find(&Def);
+        if (I != Infos.end()) {
+          const MemAccessInfo &Info = I->second;
+          SS = SS.unionWith(Info.GetStore());
+        }
+      }
+    }
+
+    const Instruction *TInst = B->getTerminator();
+    for (unsigned i = 0; i < TInst->getNumSuccessors(); ++i) {
+      BasicBlock *SB = TInst->getSuccessor(i);
+      auto Ins = Sets.emplace(SB, SS);
+      if (Ins.second) {
+        // First time here.
+        WorkList.push_back(SB);
+        continue;
+      }
+      SparseSet NewS = SS.intersectWith(Ins.first->second);
+      if (NewS != Ins.first->second) {
+        // Not first time but with reduced set.
+        WorkList.push_back(SB);
+        Ins.first->second = NewS;
+      }
+    }
+  }
+
+  for (const auto &S : Sets) {
+    const Instruction *TInst = S.first->getTerminator();
+    if (IsReturn(TInst))
+      R = R.intersectWith(S.second);
+  }
+
+  Entry.updateStoreLater(R);
+  return R;
+}
+
+MemAccessInfo
+processAlloca(bool dbg, const Function &F, const Value &AI,
+              const std::function<bool(Value *V)> &IsExpectedAlloca,
+              const SmallPtrSetImpl<Instruction *> &Instructions,
+              const SmallPtrSetImpl<MemoryAccess *> &Leaks,
+              const SmallPtrSetImpl<MemoryAccess *> &AfterLeaks,
+              const DataLayout &DL, MemorySSA &MSSA, ScalarEvolution &SE,
+              const ArgumentMemAccess &AAA,
+              SmallPtrSetImpl<Instruction *> &NowDeadInsts,
+              DenseMap<Instruction *, MemAccessInfo> &ShrinkStores) {
+  const unsigned PointerSizeInBits = DL.getPointerSizeInBits();
+
+  const SparseSet FullAlloca(PointerSizeInBits, true);
+  const SparseSet EmptyRange(PointerSizeInBits, false);
+
+  if (!MSSA.getLiveOnEntryDef()) {
+    MemAccessInfo MAI(PointerSizeInBits);
+    MAI.SetUsed(FullAlloca);
+    return MAI;
+  }
+
+  std::map<const MemoryAccess *, MemAccessInfo> Infos;
+  for (Instruction *I : Instructions) {
+    MemoryAccess *MA = MSSA.getMemoryAccess(I);
+    if (!MA) {
+      LLVM_DEBUG(MSSA.dump());
+      LLVM_DEBUG(errs() << *I << "\n");
+    }
+    assert(MA);
+    MemAccessInfo &MAI = Infos.emplace(MA, PointerSizeInBits).first->second;
+
+    if (Leaks.find(MA) != Leaks.end()) {
+      MAI.SetUsed(FullAlloca);
+      continue;
+    }
+
+    if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+      assert(IsExpectedAlloca(SI->getPointerOperand()));
+      LocationSize LS = MemoryLocation::get(SI).Size;
+      ConstantRange Range(PointerSizeInBits, false);
+      if (!LS.isPrecise() ||
+          !getAccessStart(SE, SI->getPointerOperand(), &AI, &Range) ||
+          !Range.isSingleElement()) {
+        continue;
+      }
+
+      MAI.SetStore(
+          SparseSet{Range.getLower(), Range.getLower() + LS.getValue()});
+      if (!SI->isSimple())
+        MAI.MakeVolatile();
+      continue;
+    }
+
+    if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+      assert(IsExpectedAlloca(LI->getPointerOperand()));
+      LocationSize LS = MemoryLocation::get(LI).Size;
+      ConstantRange Range(PointerSizeInBits, false);
+      if (!LS.isPrecise() ||
+          !getAccessStart(SE, LI->getPointerOperand(), &AI, &Range) ||
+          !Range.isSingleElement()) {
+        MAI.SetLoad(FullAlloca);
+        continue;
+      }
+
+      MAI.SetLoad(
+          SparseSet{Range.getLower(), Range.getLower() + LS.getValue()});
+      continue;
+    }
+
+    if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
+      assert(IsExpectedAlloca(MTI->getRawSource()) ||
+             IsExpectedAlloca(MTI->getRawDest()));
+
+      if (IsExpectedAlloca(MTI->getRawSource())) {
+        LocationSize LS = MemoryLocation::getForSource(MTI).Size;
+        ConstantRange Range(PointerSizeInBits, false);
+        if (!LS.isPrecise() ||
+            !getAccessStart(SE, MTI->getRawSource(), &AI, &Range) ||
+            !Range.isSingleElement()) {
+          MAI.SetLoad(FullAlloca);
+        } else {
+          MAI.SetLoad(
+              SparseSet{Range.getLower(), Range.getLower() + LS.getValue()});
+        }
+      }
+
+      if (IsExpectedAlloca(MTI->getRawDest())) {
+        LocationSize LS = MemoryLocation::getForDest(MTI).Size;
+        ConstantRange Range(PointerSizeInBits, false);
+        if (!LS.isPrecise() ||
+            !getAccessStart(SE, MTI->getRawDest(), &AI, &Range) ||
+            !Range.isSingleElement()) {
+        } else {
+          MAI.SetStore(
+              SparseSet{Range.getLower(), Range.getLower() + LS.getValue()});
+        }
+      }
+
+      if (MTI->isVolatile())
+        MAI.MakeVolatile();
+
+      continue;
+    }
+
+    if (MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
+      assert(IsExpectedAlloca(MSI->getRawDest()));
+      LocationSize LS = MemoryLocation::getForDest(MSI).Size;
+      ConstantRange Range(PointerSizeInBits, false);
+      if (!LS.isPrecise() ||
+          !getAccessStart(SE, MSI->getRawDest(), &AI, &Range) ||
+          !Range.isSingleElement()) {
+      } else {
+        auto RR = Range.getLower() + LS.getValue();
+        assert(RR.getBitWidth() == Range.getBitWidth());
+        ConstantRange RRR = {Range.getLower(),
+                             Range.getLower() + LS.getValue()};
+        assert(RRR.getBitWidth() == Range.getBitWidth());
+        MAI.SetStore(
+            SparseSet{Range.getLower(), Range.getLower() + LS.getValue()});
+      }
+
+      if (MSI->isVolatile())
+        MAI.MakeVolatile();
+
+      continue;
+    }
+
+    if (CallInst *CI = dyn_cast<CallInst>(I)) {
+      ImmutableCallSite CS(CI);
+      const GlobalValue *Callee = dyn_cast<GlobalValue>(
+          CS.getCalledValue()->stripPointerCastsNoFollowAliases());
+
+      if (!Callee) {
+        MAI.SetLoad(FullAlloca);
+        continue;
+      }
+
+      size_t argN = -1;
+      for (auto &A : make_range(CS.arg_begin(), CS.arg_end())) {
+        ++argN;
+        if (IsExpectedAlloca(A.get())) {
+          // break;
+          ConstantRange Range(PointerSizeInBits, false);
+
+          const Function *F = cast<Function>(Callee);
+          auto I = AAA.find(F->getGUID());
+          if (I == AAA.end() || argN >= I->second.size() ||
+              !getAccessStart(SE, A.get(), &AI, &Range) ||
+              !Range.isSingleElement()) {
+            MAI.SetLoad(FullAlloca);
+            continue;
+          }
+
+          const ArgumentAccessInfo &AAI = I->second[argN];
+
+          if (!I->second[argN].CanRead.isEmptySet()) {
+            SparseSet T = FullAlloca;
+            if (!AAI.CanRead.addCanOverflow(Range.getLower()))
+              T = AAI.CanRead.add(Range.getLower());
+            MAI.updateLoad(T);
+          }
+
+          if (!AAI.MustWrite.isEmptySet()) {
+            SparseSet T = EmptyRange;
+            if (!AAI.MustWrite.addCanOverflow(Range.getLower())) {
+              T = AAI.MustWrite.add(Range.getLower());
+            }
+            MAI.updateStore(T);
+          }
+        }
+      }
+      continue;
+    }
+
+    llvm_unreachable("Unexpected instruction");
+  }
+
+  for (MemoryAccess *MA : Leaks) {
+    auto UoD = dyn_cast<MemoryUseOrDef>(MA);
+    if (!UoD)
+      continue;
+    // if (dbg)
+    //   errs() << *MA << "\n";
+    // Instruction *I = UoD->getMemoryInst()
+    // if (!I || !NeedsEscapedObject(I))
+    //   continue;
+
+    if (Instruction *I = UoD->getMemoryInst())
+      LLVM_DEBUG(dbgs() << "LEAK: " << *I << " ; " << *MA << "\n");
+    else
+      LLVM_DEBUG(dbgs() << "LEAK: ; " << *MA << "\n");
+
+    auto Ins = Infos.emplace(MA, PointerSizeInBits);
+    if (!Ins.second)
+      continue;
+    MemAccessInfo &MAI = Ins.first->second;
+    MAI.SetUsed(FullAlloca);
+  }
+
+  for (MemoryAccess *MA : AfterLeaks) {
+    auto D = dyn_cast<MemoryDef>(MA);
+    if (!D)
+      continue;
+
+    if (Instruction *I = D->getMemoryInst())
+      LLVM_DEBUG(dbgs() << "AFTER_LEAK: " << *I << " ; " << *MA << "\n");
+    else
+      LLVM_DEBUG(dbgs() << "AFTER_LEAK: ; " << *MA << "\n");
+
+    auto It = Infos.find(MA);
+    if (It != Infos.end())
+      It->second.MakeVolatile();
+  }
+
+  Infos.emplace(MSSA.getLiveOnEntryDef(), PointerSizeInBits);
+
+  for (auto &Inf : Infos) {
+    if (Inf.first)
+      LLVM_DEBUG(dbgs() << *Inf.first << "=" << Inf.second << "\n");
+  }
+
+  for (auto &Inf : Infos) {
+    LLVM_DEBUG(dbgs() << "PRE_UPDATE:");
+    if (Inf.first) {
+      if (auto UoD = dyn_cast<MemoryUseOrDef>(Inf.first)) {
+        if (Instruction *I = UoD->getMemoryInst())
+          LLVM_DEBUG(dbgs() << " " << *I);
+      }
+      LLVM_DEBUG(dbgs() << " ; " << *Inf.first);
+    }
+    LLVM_DEBUG(dbgs() << Inf.second << "\n");
+  }
+
+  LLVM_DEBUG(MSSA.dump());
+  UpdateUses(Infos);
+  UpdateLaterWrites(F, MSSA, Infos);
+
+  for (auto &Inf : Infos) {
+    LLVM_DEBUG(dbgs() << "POST_UPDATE:");
+    if (Inf.first) {
+      if (auto UoD = dyn_cast<MemoryUseOrDef>(Inf.first)) {
+        if (Instruction *I = UoD->getMemoryInst())
+          LLVM_DEBUG(dbgs() << " " << *I);
+      }
+      LLVM_DEBUG(dbgs() << " ; " << *Inf.first);
+    }
+    LLVM_DEBUG(dbgs() << Inf.second << "\n");
+  }
+
+  for (auto &Inf : Infos) {
+    if (!Inf.first)
+      continue;
+    auto ttt = dyn_cast<MemoryUseOrDef>(Inf.first);
+    if (!ttt)
+      continue;
+    Instruction *I = ttt->getMemoryInst();
+    if (I)
+      LLVM_DEBUG(dbgs() << "R: " << *I);
+    else
+      LLVM_DEBUG(dbgs() << "R: "
+                        << "nullptr");
+    LLVM_DEBUG(dbgs() << " " << Inf.second << "\n");
+    if (!I || !(isa<StoreInst>(I) || isa<MemIntrinsic>(I)))
+      continue;
+
+    if (Inf.second.IsDeadStore()) {
+      NowDeadInsts.insert(I);
+      continue;
+    }
+
+    if (Inf.second.GetStore().isEmptySet())
+      continue;
+
+    if (!Inf.second.IsPartiallyDeadStore())
+      continue;
+
+    if (!ShrinkStores.try_emplace(I, Inf.second).second && false)
+      llvm_unreachable("Instruction should not be there");
+  }
+
+  return Infos.find(MSSA.getLiveOnEntryDef())->second;
+}
+
+bool IsLeakingCall(const ArgumentMemAccess &AAA, const GlobalValue *Callee,
+                   size_t argN) {
+  const Function *F = cast<Function>(Callee);
+  if (argN >= F->arg_size())
+    return true;
+
+  auto I = AAA.find(F->getGUID());
+  if (I == AAA.end()) {
+    logLookupMiss(F);
+    return true;
+  }
+
+  if (argN >= I->second.size())
+    return true;
+
+  return I->second[argN].Leak;
+}
+
+void analyzeAlloca(Value *A,
+                   const std::function<bool(Value *V)> &IsExpectedAlloca,
+                   SmallPtrSetImpl<Instruction *> &Leaks,
+                   SmallPtrSetImpl<Instruction *> &Instructions,
+                   const TargetLibraryInfo &TLI, ScalarEvolution &SE,
+                   const ArgumentMemAccess &AAA) {
+  SmallPtrSet<Value *, 16> Visited;
+  SmallVector<Value *, 8> WorkList;
+  Visited.insert(A);
+  WorkList.push_back(A);
+
+  while (!WorkList.empty()) {
+    Value *V = WorkList.pop_back_val();
+    for (const Use &UI : V->uses()) {
+      Instruction *U = dyn_cast<Instruction>(UI.getUser());
+      assert(V == UI.get());
+
+      if (CmpInst *CI = dyn_cast<CmpInst>(U))
+        continue; // Ignore
+
+      if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
+        if (IsExpectedAlloca(SI->getValueOperand())) {
+          Leaks.insert(SI);
+          continue;
+        }
+
+        if (IsExpectedAlloca(SI->getPointerOperand()))
+          Instructions.insert(SI);
+
+        continue;
+      }
+
+      if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
+        if (IsExpectedAlloca(LI->getPointerOperand()))
+          Instructions.insert(LI);
+        continue;
+      }
+
+      if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
+        if (IsExpectedAlloca(MTI->getRawSource()) ||
+            IsExpectedAlloca(MTI->getRawDest()))
+          Instructions.insert(MTI);
+        continue;
+      }
+
+      if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
+        if (IsExpectedAlloca(MSI->getRawDest()))
+          Instructions.insert(MSI);
+        continue;
+      }
+
+      if (CallInst *CI = dyn_cast<CallInst>(U)) {
+        if (CI->isLifetimeStartOrEnd())
+          continue; // Ignore
+        if (isa<DbgInfoIntrinsic>(CI))
+          continue; // Ignore
+        if (isFreeCall(CI, &TLI))
+          continue; // Ignore
+
+        ImmutableCallSite CS(CI);
+
+        const GlobalValue *Callee = dyn_cast<GlobalValue>(
+            CS.getCalledValue()->stripPointerCastsNoFollowAliases());
+        if (!Callee) {
+          Leaks.insert(CI);
+          continue;
+        }
+
+        int argN = 0;
+        for (auto &A : make_range(CS.arg_begin(), CS.arg_end())) {
+          if (IsExpectedAlloca(A.get())) {
+            if (IsLeakingCall(AAA, Callee, argN)) {
+              Leaks.insert(CI);
+              break;
+            }
+            Instructions.insert(CI);
+          }
+          ++argN;
+        }
+
+        continue;
+      }
+
+      if (InvokeInst *II = dyn_cast<InvokeInst>(U)) {
+        Leaks.insert(II);
+        continue;
+      }
+
+      if (Visited.insert(U).second) {
+        if (IsExpectedAlloca(U)) {
+          WorkList.push_back(U);
+          continue;
+        }
+        Instruction *I = dyn_cast<Instruction>(U);
+        assert(I);
+        Leaks.insert(I);
+      }
+    }
+  }
+}
+
+DenseMap<Value *, Value *>
+findUndelyingUniqueObjects(Function &F,
+                           const SmallVectorImpl<Value *> &Values) {
+  DenseMap<Value *, Value *> Visited;
+  SmallVector<Value *, 8> WorkList;
+  SmallPtrSet<Value *, 4> NonAllocas;
+
+  for (Value *V : Values) {
+    WorkList.push_back(V);
+    Visited[V] = V;
+  }
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  auto AddWork = [&Visited, &WorkList](Value *U, Value *AI) {
+    auto Ins = Visited.insert({U, AI});
+    if (Ins.second) {
+      WorkList.push_back(U);
+    } else if (Ins.first->second && Ins.first->second != AI) {
+      Ins.first->second = nullptr;
+      WorkList.push_back(U);
+    }
+  };
+
+  auto CheckUndelyingObject = [&DL, &Visited, &AddWork](Value *U, Value *AI) {
+    Value *UV = GetUnderlyingObject(U, DL, 1);
+    if (UV == U)
+      return false;
+
+    auto I = Visited.find(UV);
+    // if (I == Visited.end()) {
+    //   // Store for later processing.
+    //   NonAllocas.insert(UV);
+    //   //return false;
+    // }
+
+    if (I != Visited.end() && I->second == AI)
+      AddWork(U, AI);
+
+    return true;
+  };
+
+  auto HasWork = [&] {
+    if (WorkList.empty()) {
+      for (Value *V : NonAllocas) {
+        // errs() << *V << " U\n" ;
+        if (Visited.find(V) == Visited.end())
+          AddWork(V, nullptr);
+      }
+      NonAllocas.clear();
+    }
+    return !WorkList.empty();
+  };
+
+  while (HasWork()) {
+    Value *V = WorkList.pop_back_val();
+    Value *AI = Visited[V];
+
+    for (const Use &UI : V->uses()) {
+      Value *U = UI.getUser();
+      assert(V == UI.get());
+      // auto& UAI = Visited.try_emplace(UV, AI);
+      // if ()
+
+      if (CheckUndelyingObject(U, AI)) {
+      } else if (SelectInst *SI = dyn_cast<SelectInst>(U)) {
+        NonAllocas.insert(SI->getTrueValue());
+        NonAllocas.insert(SI->getFalseValue());
+        if (V == SI->getTrueValue() || V == SI->getFalseValue())
+          AddWork(U, AI);
+      } else if (PHINode *PN = dyn_cast<PHINode>(U)) {
+        for (Value *IncValue : PN->incoming_values()) {
+          NonAllocas.insert(IncValue);
+          if (V == IncValue) {
+            AddWork(U, AI);
+          }
+        }
+      } else if (CastInst *CI = dyn_cast<CastInst>(U)) {
+        AddWork(U, AI);
+      }
+    }
+  }
+
+  auto VerifyResults = [&](const DenseMap<Value *, AllocaInst *> &Visited) {
+    for (BasicBlock &BB : F) {
+      for (Instruction &I : BB) {
+        if (Value *V = dyn_cast<Value>(&I)) {
+          SmallVector<Value *, 4> Objects;
+          findAllocasForValue(V, Objects, DL);
+          assert(!Objects.empty());
+
+          auto It = Visited.find(V);
+          const Value *Vis = ((It == Visited.end()) ? nullptr : It->second);
+          if (Objects.size() == 1 && isa<AllocaInst>(Objects[0])) {
+            if (Objects[0] != Vis) {
+              errs() << "UNEXPECTED UND: " << *V << "\n" << F << "\n";
+              for (auto &P : Visited) {
+                if (P.second)
+                  errs() << *P.first << " -> " << *P.second << "\n";
+                else
+                  errs() << *P.first << " -> "
+                         << "\n";
+              }
+            }
+            assert(Objects[0] == Vis);
+          } else {
+            if (Vis) {
+              errs() << "UNEXPECTED UND: " << *V << "\n" << *Vis << F << "\n";
+              for (auto &P : Visited) {
+                if (P.second)
+                  errs() << *P.first << " -> " << *P.second << "\n";
+                else
+                  errs() << *P.first << " -> "
+                         << "\n";
+              }
+            }
+            assert(Vis == nullptr);
+          }
+        }
+      }
+    }
+  };
+  (void)VerifyResults;
+
+  // LLVM_DEBUG(VerifyResults(Visited));
+
+  return Visited;
+};
+
+void findMemoryAccessesAfterEscape(
+    const SmallPtrSetImpl<MemoryAccess *> &Leaks,
+    SmallPtrSetImpl<MemoryAccess *> &AfterLeaks) {
+  SmallVector<MemoryAccess *, 8> WorkList(Leaks.begin(), Leaks.end());
+
+  while (!WorkList.empty()) {
+    MemoryAccess *MA = WorkList.pop_back_val();
+
+    for (const Use &UI : MA->uses()) {
+      MemoryAccess *U = dyn_cast<MemoryAccess>(UI.getUser());
+      if (AfterLeaks.insert(U).second) {
+        WorkList.push_back(U);
+      }
+    }
+  }
+}
+
+bool tryToShorten(StoreInst *SI, const SparseSet &Before,
+                  const SparseSet &After, SmallVectorImpl<Value *> &MaybeDead) {
+  ++NumStoreInstrToShrink;
+  // Not implemented number of these are low.
+  return false;
+}
+
+bool tryToShortenImpl(MemIntrinsic *I, const SparseSet &Before,
+                      const SparseSet &After,
+                      SmallVectorImpl<Value *> &MaybeDead) {
+  LLVM_DEBUG(dbgs() << "  tryToShortenImpl: " << Before << " -> " << After
+                    << "\n");
+  ++NumMemIntrinsicToShrink;
+
+  assert(After.IsSingleRange());
+  assert(Before.IsSingleRange());
+
+  auto PtrAdd = After.getLower() - Before.getLower();
+  assert(PtrAdd >= 0);
+  
+  auto LenSub = PtrAdd + Before.getUpper() - After.getUpper();
+  if (!LenSub)
+    return false;
+  assert(LenSub > 0);
+
+  auto NewLength = Before.getUpper() - Before.getLower() - LenSub;
+  MaybeDead.push_back(I->getLength());
+  Value *ILength = I->getLength();
+  Value *TrimmedLength = ConstantInt::get(ILength->getType(), NewLength);
+  I->setLength(TrimmedLength);
+
+  Value *Indices[1] = {ConstantInt::get(ILength->getType(), PtrAdd)};
+  GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
+      I->getRawDest()->getType()->getPointerElementType(), I->getRawDest(),
+      Indices, "", I);
+  I->setDest(NewDestGEP);
+  I->setDestAlignment(GreatestCommonDivisor64(I->getDestAlignment(), PtrAdd));
+
+  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
+    GetElementPtrInst *NewSrcGEP = GetElementPtrInst::CreateInBounds(
+        MTI->getRawSource()->getType()->getPointerElementType(),
+        MTI->getRawSource(), Indices, "", MTI);
+    MTI->setSource(NewSrcGEP);
+    MTI->setSourceAlignment(
+        GreatestCommonDivisor64(MTI->getSourceAlignment(), PtrAdd));
+  }
+
+  ++NumMemIntrinsicShrinked;
+  return true;
+}
+
+bool tryToShorten(MemIntrinsic *I, const SparseSet &Before,
+                  const SparseSet &After, SmallVectorImpl<Value *> &MaybeDead) {
+  LLVM_DEBUG(dbgs() << "tryToShorten: " << Before << " -> " << After << "\n");
+
+  if (After.IsSingleRange()) {
+    return tryToShortenImpl(I, Before, After, MaybeDead);
+  }
+
+  for (SparseSet T = After; !T.isEmptySet();
+       T = T.difference(T.getFirstRange())) {
+    MemIntrinsic *C = cast<MemIntrinsic>(I->clone());
+    C->insertBefore(I);
+    auto R = T.getFirstRange();
+    bool Changed = tryToShortenImpl(C, Before, R, MaybeDead);
+    assert(Changed);
+  }
+  MaybeDead.push_back(I->getLength());
+  I->eraseFromParent();
+  return true;
+}
+
+static bool
+deleteDeadInstruction(const TargetLibraryInfo &TLI,
+                      SmallPtrSetImpl<Instruction *> &NowDeadInsts,
+                      DenseMap<Instruction *, MemAccessInfo> &ShrinkStores) {
+  SmallVector<Instruction *, 32> WorkList(NowDeadInsts.begin(),
+                                          NowDeadInsts.end());
+  bool Changed = !NowDeadInsts.empty();
+
+  for (auto &It : ShrinkStores) {
+    SmallVector<Value *, 32> MaybeDead;
+
+    if (StoreInst *SI = dyn_cast<StoreInst>(It.first)) {
+      if (tryToShorten(SI, It.second.GetStore(), It.second.GetGood(),
+                       MaybeDead))
+        Changed = true;
+    } else {
+      if (tryToShorten(cast<MemIntrinsic>(It.first), It.second.GetStore(),
+                       It.second.GetGood(), MaybeDead))
+        Changed = true;
+    }
+
+    for (Value *Op : MaybeDead) {
+      // If this operand just became dead, add it to the WorkList list.
+      if (!Op->use_empty())
+        continue;
+
+      if (Instruction *OpI = dyn_cast<Instruction>(Op)) {
+        if (isInstructionTriviallyDead(OpI, &TLI)) {
+          NowDeadInsts.insert(OpI);
+          WorkList.push_back(OpI);
+        }
+      }
+    }
+  }
+
+  while (!WorkList.empty()) {
+    Instruction *I = WorkList.pop_back_val();
+
+    // Try to preserve debug information attached to the dead instruction.
+    salvageDebugInfo(*I);
+
+    for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
+      Value *Op = I->getOperand(op);
+      I->setOperand(op, nullptr);
+
+      // If this operand just became dead, add it to the WorkList list.
+      if (!Op->use_empty())
+        continue;
+
+      if (Instruction *OpI = dyn_cast<Instruction>(Op)) {
+        if (isInstructionTriviallyDead(OpI, &TLI)) {
+          NowDeadInsts.insert(OpI);
+          WorkList.push_back(OpI);
+        }
+      }
+    }
+  }
+  return Changed;
+}
+
+void findDeadStores(Function &F, SmallVectorImpl<Value *> &Values,
+                    const TargetLibraryInfo &TLI, MemorySSA &MSSA,
+                    ScalarEvolution &SE,
+                    SmallPtrSet<Instruction *, 32> &NowDeadInsts,
+                    DenseMap<Instruction *, MemAccessInfo> &ShrinkStores,
+                    std::vector<ArgumentAccessInfo> &ArgInfo,
+                    const ArgumentMemAccess &AAA) {
+  auto UndelyingAllocas = findUndelyingUniqueObjects(F, Values);
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  unsigned PointerSizeInBits = DL.getPointerSizeInBits();
+
+  for (Value *AI : Values) {
+    assert(AI);
+    LLVM_DEBUG(dbgs() << "findDeadStores into " << *AI << " in " << F.getName()
+                      << "\n");
+    ArgInfo.emplace_back(PointerSizeInBits);
+
+    if (!DebugCounter::shouldExecute(DeadStoreEliminationExp))
+      continue;
+
+    SmallPtrSet<Instruction *, 4> Leaks;
+    SmallPtrSet<Instruction *, 4> Instructions;
+
+    auto IsExpectedAlloca = [&](Value *V) {
+      auto It = UndelyingAllocas.find(V);
+      return It != UndelyingAllocas.end() && It->second == AI;
+    };
+
+    analyzeAlloca(AI, IsExpectedAlloca, Leaks, Instructions, TLI, SE, AAA);
+    bool Skip = false;
+
+    SmallPtrSet<MemoryAccess *, 4> LeakedAccesses;
+    for (Instruction *L : Leaks) {
+      LLVM_DEBUG(dbgs() << "Escape here: " << *L << "\n");
+      MemoryAccess *M = MSSA.getMemoryAccess(L);
+      if (!M) {
+        M = MSSA.getMemoryAccess(L->getParent());
+        if (!M) {
+          LLVM_DEBUG(dbgs() << "Skip value: escape has no MemoryAccess\n");
+          Skip = true;
+          break;
+        }
+      }
+      if (MemoryDef *MA = dyn_cast<MemoryDef>(M)) {
+        LeakedAccesses.insert(MA);
+        continue;
+      }
+
+      bool HasDef = false;
+      for (MemoryAccess *Def : make_range(M->defs_begin(), M->defs_end())) {
+        assert(isa<MemoryDef>(Def) || isa<MemoryPhi>(Def));
+        LeakedAccesses.insert(Def);
+        HasDef = true;
+      }
+
+      if (!HasDef) {
+        LLVM_DEBUG(dbgs() << "Skip value: can't find MemoryDef\n");
+        Skip = true;
+      }
+    }
+
+    for (Instruction *I : Instructions) {
+      MemoryAccess *MA = MSSA.getMemoryAccess(I);
+      if (!MA) {
+        LLVM_DEBUG(dbgs() << "Skip value: can't find MemoryDef\n");
+        Skip = true;
+      }
+    }
+
+    SmallPtrSet<MemoryAccess *, 4> AccessesAfterLeak;
+    if (!Skip)
+      findMemoryAccessesAfterEscape(LeakedAccesses, AccessesAfterLeak);
+
+    for (Instruction *I : Instructions) {
+      assert(I);
+      if (!isa<StoreInst>(I) && !isa<MemIntrinsic>(I))
+        continue;
+      ++NumMemWrites;
+
+      if (Skip) {
+        ++NumMemWritesSkipWithAlloca;
+        continue;
+      }
+
+      MemoryAccess *MA = MSSA.getMemoryAccess(I);
+      if (LeakedAccesses.find(MA) != LeakedAccesses.end() ||
+          AccessesAfterLeak.find(MA) != AccessesAfterLeak.end()) {
+        LLVM_DEBUG(errs() << "NumMemWritesSkip: " << *I << "\n");
+        ++NumMemWritesSkip;
+        continue;
+      }
+
+      ++NumMemWritesToAnalize;
+    }
+
+    if (!Skip) {
+      bool dbg = 0;
+      MemAccessInfo MAI = processAlloca(
+          dbg, F, *AI, IsExpectedAlloca, Instructions, LeakedAccesses,
+          AccessesAfterLeak, DL, MSSA, SE, AAA, NowDeadInsts, ShrinkStores);
+      ArgInfo.back().Leak = !LeakedAccesses.empty();
+      ArgInfo.back().CanRead = MAI.GetUsed();
+      ArgInfo.back().MustWrite = MAI.GetStoreLater();
+    }
+    // ArgInfo.back().Leak = false;
+  }
+}
+
+bool eliminateDeadStores(Function &F, MemorySSA &MSSA, ScalarEvolution &SE,
+                         const TargetLibraryInfo &TLI,
+                         const ArgumentMemAccess &AAA) {
+  SmallPtrSet<Instruction *, 32> NowDeadInsts;
+  DenseMap<Instruction *, MemAccessInfo> ShrinkStores;
+
+  SmallVector<Value *, 4> Values;
+  for (BasicBlock &BB : F) {
+    for (Instruction &I : BB) {
+      if (isa<AnyMemIntrinsic>(&I) || isa<StoreInst>(&I)) {
+        ++NumMemWritesAny;
+        continue;
+      }
+      if (isa<AllocaInst>(&I)) {
+        // continue;
+        ++NumAlloca;
+      } else if (isa<CallInst>(&I) && isAllocationFn(&I, &TLI)) {
+        continue;
+        ++NumAllocation;
+      } else {
+        continue;
+      }
+      Values.push_back(&I);
+    }
+  }
+
+  std::vector<ArgumentAccessInfo> MemInfo;
+  findDeadStores(F, Values, TLI, MSSA, SE, NowDeadInsts, ShrinkStores, MemInfo,
+                 AAA);
+
+  NumMemWritesDeleted += NowDeadInsts.size();
+  NumOtherDeleted -= NowDeadInsts.size();
+  bool Changed = deleteDeadInstruction(TLI, NowDeadInsts, ShrinkStores);
+  NumOtherDeleted += NowDeadInsts.size();
+  for (Instruction *I : NowDeadInsts) {
+    LLVM_DEBUG(dbgs() << "Erase: " << *I << "\n");
+    if (!I->use_empty()) {
+      dbgs() << "Erase: " << *I << "\n";
+    }
+    I->eraseFromParent();
+  }
+
+  return Changed;
+}
+
+class ArgumentAccessInfoLegacyPass : public ModulePass {
+public:
+  static char ID;
+  ArgumentMemAccess AAMI;
+
+  ArgumentAccessInfoLegacyPass() : ModulePass(ID) {
+    initializeArgumentAccessInfoLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  const ArgumentMemAccess &getResult() const { return AAMI; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<CallGraphWrapperPass>();
+    AU.addRequired<MemorySSAWrapperPass>();
+    AU.addRequired<ScalarEvolutionWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.setPreservesAll();
+  }
+
+  template <typename AnalysisType>
+  AnalysisType *getAnalysisIfAvalible(Function &F) {
+    Pass *P = getResolver()->findImplPass(this, &AnalysisType::ID, F);
+    if (!P)
+      return 0;
+
+    return static_cast<AnalysisType *>(P);
+  }
+
+  bool runOnModule(Module &M) override {
+    uncompressAAMI(AAMI);
+
+    std::set<GlobalValue::GUID> GUIDS;
+    auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+    for (const std::vector<CallGraphNode *> &NV :
+         make_range(scc_begin(&CG), scc_end(&CG))) {
+      for (const CallGraphNode *CGN : NV) {
+        if (Function *F = CGN->getFunction()) {
+          static std::set<Function *> b;
+          assert(b.insert(F).second);
+
+          auto *TLI = getAnalysisIfAvalible<TargetLibraryInfoWrapperPass>(*F);
+          if (!TLI)
+            continue;
+          auto *MSSA = getAnalysisIfAvalible<MemorySSAWrapperPass>(*F);
+          if (!MSSA)
+            continue;
+          auto *SE = getAnalysisIfAvalible<ScalarEvolutionWrapperPass>(*F);
+          if (!SE)
+            continue;
+
+          SmallPtrSet<Instruction *, 32> NowDeadInsts;
+          DenseMap<Instruction *, MemAccessInfo> ShrinkStores;
+
+          SmallVector<Value *, 4> Values;
+          for (Argument &A : F->args())
+            Values.push_back(&A);
+
+          std::vector<ArgumentAccessInfo> ArgInfo;
+
+          findDeadStores(*F, Values, TLI->getTLI(), MSSA->getMSSA(),
+                         SE->getSE(), NowDeadInsts, ShrinkStores, ArgInfo,
+                         AAMI);
+          if (ArgInfo.empty())
+            continue;
+
+          AAMI[F->getGUID()] = ArgInfo;
+
+          GUIDS.insert(F->getGUID());
+        }
+      }
+    }
+
+    compressAAMI(AAMI, GUIDS);
+    return false;
+  }
+};
+
+/// A legacy pass for the legacy pass manager that wraps \c DSEEPass.
+class DSEELegacyPass : public FunctionPass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  DSEELegacyPass() : FunctionPass(ID) {
+    initializeDSEELegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+
+    return eliminateDeadStores(
+        F, getAnalysis<MemorySSAWrapperPass>().getMSSA(),
+        getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
+        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
+        getAnalysis<ArgumentAccessInfoLegacyPass>().getResult());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<ArgumentAccessInfoLegacyPass>();
+    AU.addRequired<MemorySSAWrapperPass>();
+    AU.addRequired<ScalarEvolutionWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.setPreservesCFG();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+  }
+};
+
+char DSEELegacyPass::ID = 0;
+char ArgumentAccessInfoLegacyPass::ID = 0;
+
+} // end anonymous namespace
+
+SparseSet SparseSet::difference(const SparseSet &Other) const {
+  SparseSet Res(PointerSize, false);
+  Res.Intervals = ApplySetFn(Intervals, Other.Intervals,
+                             [](bool A, bool B) { return A && !B; });
+  return Res;
+}
+
+SparseSet SparseSet::unionWith(const SparseSet &Other) const {
+  SparseSet Res(PointerSize, false);
+  Res.Intervals = ApplySetFn(Intervals, Other.Intervals,
+                             [](bool A, bool B) { return A || B; });
+  return Res;
+}
+
+SparseSet SparseSet::intersectWith(const SparseSet &Other) const {
+  SparseSet Res(PointerSize, false);
+  Res.Intervals = ApplySetFn(Intervals, Other.Intervals,
+                             [](bool A, bool B) { return A && B; });
+  return Res;
+}
+
+SparseSet SparseSet::getFirstRange() const {
+  SparseSet Res(PointerSize, false);
+  if (!Intervals.empty()) {
+    Res.Intervals.push_back(Intervals[0]);
+    if (Intervals.size() > 1)
+      Res.Intervals.push_back(Intervals[1]);
+  }
+  return Res;
+}
+
+bool SparseSet::addCanOverflow(APInt A) const {
+  if (Intervals.empty())
+    return false;
+  if (Intervals.size() % 2 != 0)
+    return true;
+  if (Intervals.front() == Min)
+    return true;
+  if (Intervals.back() == Max)
+    return true;
+
+  uint64_t V = A.getLimitedValue();
+  if (V >= uint64_t(Max) - Intervals.back())
+    return true;
+
+  return false;
+}
+
+constexpr SparseSet::T SparseSet::Min;
+constexpr SparseSet::T SparseSet::Max;
+
+SparseSet SparseSet::add(APInt A) const {
+  assert(!addCanOverflow(A));
+  SparseSet Res(PointerSize, false);
+  Res.Intervals = Intervals;
+  uint64_t V = A.getLimitedValue();
+  for (auto &P : Res.Intervals)
+    P += V;
+  assert(std::is_sorted(Res.Intervals.begin(), Res.Intervals.end()));
+  return Res;
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &os, const SparseSet &SS) {
+  return ::operator<<(os, SS.Intervals);
+}
+
+DSEEPass::DSEEPass() { uncompressAAMI(AAI); }
+
+DSEEPass::~DSEEPass() { compressAAMI(AAI, GUIDS); }
+
+PreservedAnalyses DSEEPass::run(Function &F, FunctionAnalysisManager &AM) {
+  GUIDS.insert(F.getGUID());
+
+  SmallVector<Value *, 4> Values;
+  for (Argument &A : F.args())
+    Values.push_back(&A);
+
+  SmallPtrSet<Instruction *, 32> NowDeadInsts;
+  DenseMap<Instruction *, MemAccessInfo> ShrinkStores;
+
+  std::vector<ArgumentAccessInfo> ArgInfo;
+
+  findDeadStores(F, Values, AM.getResult<TargetLibraryAnalysis>(F),
+                 AM.getResult<MemorySSAAnalysis>(F).getMSSA(),
+                 AM.getResult<ScalarEvolutionAnalysis>(F), NowDeadInsts,
+                 ShrinkStores, ArgInfo, AAI);
+
+  // assert(0);
+  // errs() << F << "\n";
+  assert(F.arg_size() == ArgInfo.size());
+  AAI[F.getGUID()] = ArgInfo;
+
+  // AAMA = AAMA ? AAMA : &Empty;
+  if (!eliminateDeadStores(F, AM.getResult<MemorySSAAnalysis>(F).getMSSA(),
+                           AM.getResult<ScalarEvolutionAnalysis>(F),
+                           AM.getResult<TargetLibraryAnalysis>(F), AAI)) {
+    return PreservedAnalyses::all();
+  }
+  // return PreservedAnalyses();
+
+  // return PreservedAnalyses::all();
+  PreservedAnalyses PA;
+  PA.preserve<MemorySSAAnalysis>();
+  PA.preserveSet<CFGAnalyses>();
+  PA.preserve<GlobalsAA>();
+  PA.preserve<MemoryDependenceAnalysis>();
+  return PA;
+}
+
+INITIALIZE_PASS_BEGIN(ArgumentAccessInfoLegacyPass, "argument-access",
+                      "Argument Access Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_END(ArgumentAccessInfoLegacyPass, "argument-access",
+                    "Argument Access Analysis", false, true)
+
+INITIALIZE_PASS_BEGIN(DSEELegacyPass, "dsee",
+                      "Experimental Dead Store Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(ArgumentAccessInfoLegacyPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_END(DSEELegacyPass, "dsee",
+                    "Experimental Dead Store Elimination", false, false)
+
+FunctionPass *llvm::createDeadStoreEliminationExpPass() {
+  return new DSEELegacyPass();
+}

llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.h

+// FIXME: Remove or implement with ThinLTO. There is no evidence yet that it
+// has significant effect.
+
+#ifndef LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATIONEXPGLOBAL_H
+#define LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATIONEXPGLOBAL_H
+
+#include "llvm/Transforms/Scalar/DeadStoreEliminationExp.h"
+
+namespace llvm {
+
+void logLookupMiss(const Function *F);
+void uncompressAAMI(ArgumentMemAccess &AAMI);
+void compressAAMI(const ArgumentMemAccess &AAMI,
+                  std::set<GlobalValue::GUID> &GUIDS);
+
+} // namespace llvm
+
+#endif

llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGlobal.cpp

+// FIXME: Remove or implement with ThinLTO. There is no evidence yet that it
+// has significant effect.
+
+#include "DeadStoreEliminationExpGlobal.h"
+#include "llvm/Support/Compression.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+
+static cl::opt<bool>
+EnabledGlobalAnalysis("enable-dse-global-analysis",
+  cl::init(false), cl::Hidden,
+  cl::desc("Enable global analysis in DSE"));
+
+static cl::opt<bool>
+UseGlobalAnalysis("use-dse-global-analysis",
+  cl::init(false), cl::Hidden,
+  cl::desc("Use global analysis in DSE"));
+
+static const GlobalValue::GUID GUIDS_LOOKUP[] = {
+// grep  -P -o "(?<=LOOKUP_FN: ).*" <logfile> | sort -u >
+// ../llvm-project/llvm/lib/Transforms/Scalar/DeadStoreEliminationExpGUIDs.h
+#include "DeadStoreEliminationExpGlobalGUIDListGen.h"
+};
+
+static const char GlobalArgumentMemAccess[] = {
+// grep  -P -o "(?<=FUNCTION_INFO: ).*" <logfile> | sort -u >
+// ../llvm-project/llvm/lib/Transforms/Scalar/DeadStoreEliminationExpData.h
+#include "DeadStoreEliminationExpGlobalArgInfoGen.h"
+};
+
+void logLookupMiss(const Function *F) {
+  if (!EnabledGlobalAnalysis)
+    return;
+
+  static std::set<GlobalValue::GUID> Done;
+  if (Done.insert(F->getGUID()).second)
+    errs() << "LOOKUP_FN: " << F->getGUID() << "ULL,\n";
+}
+
+SparseSet fromStringSparseSet(const char *&P) {
+  SparseSet SS(12, false);
+  SS.PointerSize = *(unsigned *)P;
+  P += sizeof(SS.PointerSize);
+  size_t N = *(size_t *)P;
+  P += sizeof(N);
+  auto &II = SS.Intervals;
+  II.assign((int64_t *)P, (int64_t *)(P + sizeof(int64_t) * N));
+  P += sizeof(int64_t) * N;
+  return SS;
+}
+
+ArgumentAccessInfo fromStringArgumentAccessInfo(const char *&P) {
+  ArgumentAccessInfo AAI(0);
+  AAI.Leak = (*P == 'L');
+  ++P;
+  AAI.CanRead = fromStringSparseSet(P);
+  AAI.MustWrite = fromStringSparseSet(P);
+  return AAI;
+}
+
+void uncompressAAMI(ArgumentMemAccess &AAMI) {
+  if (!EnabledGlobalAnalysis && !UseGlobalAnalysis)
+    return;
+  SmallVector<char, 10000> UncompressedBuffer(10000);
+  for (const char *CUR = GlobalArgumentMemAccess;
+       CUR < GlobalArgumentMemAccess + sizeof(GlobalArgumentMemAccess);) {
+    auto SZ = *(const uint32_t *)(CUR);
+    CUR += sizeof(SZ);
+
+    UncompressedBuffer.resize(UncompressedBuffer.capacity());
+    for (;;) {
+      Error E = zlib::uncompress(std::string(CUR, SZ), UncompressedBuffer,
+                                 UncompressedBuffer.size());
+      if (!E)
+        break;
+      consumeError(std::move(E));
+      assert(UncompressedBuffer.size() * 2 > UncompressedBuffer.capacity());
+      UncompressedBuffer.resize(2 * UncompressedBuffer.capacity());
+    }
+    CUR += SZ;
+
+    const char *P = UncompressedBuffer.data();
+    while (P < UncompressedBuffer.data() + UncompressedBuffer.size()) {
+      assert(UncompressedBuffer.size() >= sizeof(GlobalValue::GUID));
+
+      auto GUID = *(GlobalValue::GUID *)P;
+      P += sizeof(GUID);
+      size_t N = *(size_t *)P;
+      P += sizeof(N);
+      AAMI[GUID].resize(N, 0);
+      for (auto &AAI : AAMI[GUID])
+        AAI = fromStringArgumentAccessInfo(P);
+    }
+  }
+}
+
+std::string toString(const SparseSet &SS) {
+  std::string R;
+  R += std::string((const char *)(&SS.PointerSize), sizeof(SS.PointerSize));
+  size_t N = SS.Intervals.size();
+  R += std::string((const char *)(&N), sizeof(N));
+  R += std::string((const char *)(SS.Intervals.data()),
+                   N * sizeof(*SS.Intervals.data()));
+  return R;
+}
+
+std::string toString(const ArgumentAccessInfo &AAI) {
+  std::string R;
+  R += AAI.Leak ? "L" : " ";
+  R += toString(AAI.CanRead);
+  R += toString(AAI.MustWrite);
+  return R;
+}
+
+void compressAAMI(const ArgumentMemAccess &AAMI,
+                  std::set<GlobalValue::GUID> &GUIDS) {
+  if (!EnabledGlobalAnalysis)
+    return;
+
+  std::string I;
+
+  std::set<GlobalValue::GUID> Need(GUIDS_LOOKUP,
+                                   GUIDS_LOOKUP + sizeof(GUIDS_LOOKUP) /
+                                                      sizeof(GUIDS_LOOKUP[0]));
+  for (GlobalValue::GUID GUID2 : GUIDS) {
+    if (!Need.count(GUID2))
+      continue;
+    size_t GUID = GUID2;
+    auto FN = AAMI.find(GUID);
+    if (FN != AAMI.end()) {
+      I += std::string((const char *)(&GUID), sizeof(GUID));
+      size_t N = FN->second.size();
+      I += std::string((const char *)(&N), sizeof(N));
+      for (const auto &AAI : FN->second) {
+        I += toString(AAI);
+      }
+    }
+  }
+
+  if (I.empty())
+    return;
+
+  SmallVector<char, 100> comp;
+  auto E = zlib::compress(I, comp);
+  if (E || comp.empty())
+    return;
+
+  errs() << "FUNCTION_INFO: ";
+  union {
+    uint32_t S;
+    char c[4];
+  } S;
+  S.S = comp.size();
+
+  for (int c : S.c) {
+    errs() << c << ",";
+  }
+
+  for (int c : comp) {
+    errs() << c << ",";
+  }
+  errs() << "\n";
+}
+
+} // namespace llvm

llvm/lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeConstantHoistingLegacyPassPass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCELegacyPassPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeDivRemPairsLegacyPassPass(Registry);
   initializeScalarizerLegacyPassPass(Registry);
   initializeDSELegacyPassPass(Registry);
+  initializeDSEELegacyPassPass(Registry);
   initializeGuardWideningLegacyPassPass(Registry);
   initializeLoopGuardWideningLegacyPassPass(Registry);
   initializeGVNLegacyPassPass(Registry);
   initializeNewGVNLegacyPassPass(Registry);
   initializeEarlyCSELegacyPassPass(Registry);
   initializeEarlyCSEMemSSALegacyPassPass(Registry);
   initializeMakeGuardsExplicitLegacyPassPass(Registry);
   initializeGVNHoistLegacyPassPass(Registry);
void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeTailCallElimPass(Registry);
   initializeSeparateConstOffsetFromGEPPass(Registry);
   initializeSpeculativeExecutionLegacyPassPass(Registry);
   initializeStraightLineStrengthReducePass(Registry);
   initializePlaceBackedgeSafepointsImplPass(Registry);
   initializePlaceSafepointsPass(Registry);
   initializeFloat2IntLegacyPassPass(Registry);
   initializeLoopDistributeLegacyPass(Registry);
+  initializeArgumentAccessInfoLegacyPassPass(Registry);
   initializeLoopLoadEliminationPass(Registry);
   initializeLoopSimplifyCFGLegacyPassPass(Registry);
   initializeLoopVersioningPassPass(Registry);
   initializeEntryExitInstrumenterPass(Registry);
   initializePostInlineEntryExitInstrumenterPass(Registry);
 }
 
 void LLVMAddLoopSimplifyCFGPass(LLVMPassManagerRef PM) {

 void LLVMAddCFGSimplificationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createCFGSimplificationPass(1, false, false, true));
 }
 
 void LLVMAddDeadStoreEliminationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createDeadStoreEliminationPass());
 }
 
+void LLVMAddDeadStoreEliminationExpPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createDeadStoreEliminationExpPass());
+}
+
 void LLVMAddScalarizerPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createScalarizerPass());
 }
 
 void LLVMAddGVNPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createGVNPass());
 }
 

llvm/test/ObjectYAML/MachO/DWARF-debug_line.yaml

-# RUN: yaml2obj %s | obj2yaml | FileCheck %s
+# RUN: yaml2obj %s | obj2yaml 
+#| FileCheck %s
 
 --- !mach-o
 FileHeader:      
   magic:           0xFEEDFACF
   cputype:         0x01000007
   cpusubtype:      0x00000003
   filetype:        0x0000000A
   ncmds:           7

llvm/test/Other/dsae.ll

+; RUN: opt -debug-only=dsae --stats -dsae -S -o - %s
+;;| FileCheck %s
+; RU1N: not opt -debug-only=dsae --stats -dsae -S -o - %s && false
+
+; ModuleID = '/tmp/compiler-explorer-compiler119313-53-jv8jef.mjvq/example.c'
+source_filename = "/tmp/compiler-explorer-compiler119313-53-jv8jef.mjvq/example.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.M = type { i32, [111 x i32] }
+
+@t = common dso_local local_unnamed_addr global i32 0, align 4
+@n = common dso_local local_unnamed_addr global %struct.M zeroinitializer, align 4
+
+; Function Attrs: nounwind uwtable
+define dso_local void @F1() local_unnamed_addr #0 {
+  %1 = alloca %struct.M, align 4
+  %2 = bitcast %struct.M* %1 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 448, i8* nonnull %2) #4
+  call void @llvm.memset.p0i8.i64(i8* nonnull align 4 %2, i8 -86, i64 448, i1 false)
+  call fastcc void @WRITE(%struct.M* nonnull sret %1)
+  call void @X(%struct.M* nonnull %1) #4
+  call void @llvm.lifetime.end.p0i8(i64 448, i8* nonnull %2) #4
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg) #1
+
+; Function Attrs: noinline nounwind uwtable
+define internal fastcc void @WRITE(%struct.M* noalias nocapture sret) unnamed_addr #2 {
+  %2 = getelementptr inbounds %struct.M, %struct.M* %0, i64 0, i32 1
+  %3 = bitcast [111 x i32]* %2 to i8*
+  tail call void @llvm.memset.p0i8.i64(i8* nonnull align 4 %3, i8 0, i64 444, i1 false)
+  %4 = getelementptr inbounds %struct.M, %struct.M* %0, i64 0, i32 0
+  store i32 5, i32* %4, align 4, !tbaa !2
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1 immarg) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+declare dso_local void @X(%struct.M*) local_unnamed_addr #3
+
+; Function Attrs: nounwind uwtable
+define dso_local void @F2() local_unnamed_addr #0 {
+  %1 = alloca %struct.M, align 4
+  %2 = bitcast %struct.M* %1 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 448, i8* nonnull %2) #4
+  call void @llvm.memset.p0i8.i64(i8* nonnull align 4 %2, i8 -86, i64 448, i1 false)
+  call fastcc void @NOREAD(%struct.M* nonnull %1)
+  call void @X(%struct.M* nonnull %1) #4
+  call void @llvm.lifetime.end.p0i8(i64 448, i8* nonnull %2) #4
+  ret void
+}
+
+; Function Attrs: noinline nounwind uwtable
+define internal fastcc void @NOREAD(%struct.M* nocapture) unnamed_addr #2 {
+  %2 = bitcast %struct.M* %0 to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %2, i8* align 4 bitcast (%struct.M* @n to i8*), i64 448, i1 false), !tbaa.struct !7
+  ret void
+}
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 9.0.0 (trunk 358316)"}
+!2 = !{!3, !4, i64 0}
+!3 = !{!"M", !4, i64 0, !5, i64 4}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C/C++ TBAA"}
+!7 = !{i64 0, i64 4, !8, i64 4, i64 444, !9}
+!8 = !{!4, !4, i64 0}
+!9 = !{!5, !5, i64 0}

llvm/test/Other/dse-exp-struct.ll

+; RU1N: opt -debug-only=dsee --stats -dsee -S -o - %s
+;;| FileCheck %s
+; RUN: not opt --stats -dsee -S -o - %s | opt -O2 -S -o - && false
+
+; ModuleID = './example.cpp'
+source_filename = "./example.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Struct2 = type { i8 }
+%struct.Struct = type { %struct.Struct2, i32, i32, i32, float, double }
+
+$_ZN6StructC2Ev = comdat any
+
+$_ZN7Struct2C2Ev = comdat any
+
+@__const.main.s = private unnamed_addr constant { %struct.Struct2, [3 x i8], i32, i32, i32, float, [4 x i8], double } { %struct.Struct2 { i8 -86 }, [3 x i8] c"\AA\AA\AA", i32 -1431655766, i32 -1431655766, i32 -1431655766, float 0xFFFFFFFFE0000000, [4 x i8] c"\AA\AA\AA\AA", double 0xFFFFFFFFFFFFFFFF }, align 8
+
+; Function Attrs: norecurse uwtable
+define dso_local i32 @main() local_unnamed_addr #0 {
+  %1 = alloca %struct.Struct, align 8
+  %2 = getelementptr inbounds %struct.Struct, %struct.Struct* %1, i64 0, i32 0, i32 0
+  call void @llvm.lifetime.start.p0i8(i64 32, i8* nonnull %2) #4
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %2, i8* align 8 getelementptr inbounds ({ %struct.Struct2, [3 x i8], i32, i32, i32, float, [4 x i8], double }, { %struct.Struct2, [3 x i8], i32, i32, i32, float, [4 x i8], double }* @__const.main.s, i64 0, i32 0, i32 0), i64 32, i1 false)
+  call void @_ZN6StructC2Ev(%struct.Struct* nonnull %1)
+  %3 = getelementptr inbounds %struct.Struct, %struct.Struct* %1, i64 0, i32 1
+  %4 = load i32, i32* %3, align 4, !tbaa !2
+  %5 = getelementptr inbounds %struct.Struct, %struct.Struct* %1, i64 0, i32 2
+  %6 = load i32, i32* %5, align 8, !tbaa !9
+  %7 = add nsw i32 %6, %4
+  call void @llvm.lifetime.end.p0i8(i64 32, i8* nonnull %2) #4
+  ret i32 %7
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1 immarg) #1
+
+; Function Attrs: noinline uwtable
+define linkonce_odr dso_local void @_ZN6StructC2Ev(%struct.Struct*) unnamed_addr #2 comdat align 2 {
+  %2 = getelementptr inbounds %struct.Struct, %struct.Struct* %0, i64 0, i32 0
+  tail call void @_ZN7Struct2C2Ev(%struct.Struct2* %2)
+  %3 = getelementptr inbounds %struct.Struct, %struct.Struct* %0, i64 0, i32 2
+  store i32 4, i32* %3, align 8, !tbaa !9
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: noinline nounwind uwtable
+define linkonce_odr dso_local void @_ZN7Struct2C2Ev(%struct.Struct2*) unnamed_addr #3 comdat align 2 {
+  %2 = getelementptr inbounds %struct.Struct2, %struct.Struct2* %0, i64 0, i32 0
+  store i8 4, i8* %2, align 1, !tbaa !10
+  ret void
+}
+
+attributes #0 = { norecurse uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { noinline uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 9.0.0 (trunk 364263)"}
+!2 = !{!3, !4, i64 4}
+!3 = !{!"_ZTS6Struct", !4, i64 4, !4, i64 8, !4, i64 12, !7, i64 16, !8, i64 24}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C++ TBAA"}
+!7 = !{!"float", !5, i64 0}
+!8 = !{!"double", !5, i64 0}
+!9 = !{!3, !4, i64 8}
+!10 = !{!11, !5, i64 0}
+!11 = !{!"_ZTS7Struct2", !5, i64 0}

llvm/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: SCCPPass
 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-EP-PEEPHOLE-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O-NEXT: Running pass: DSEPass
+; CHECK-O2-NEXT: Running pass: DSEEPass
+; CHECK-O3-NEXT: Running pass: DSEEPass
+; CHECK-Os-NEXT: Running pass: DSEEPass
+; CHECK-Oz-NEXT: Running pass: DSEEPass
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LICMPass{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-EP-SCALAR-LATE-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O-NEXT: Running pass: ADCEPass
 ; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O1-NEXT: Running analysis: PhiValuesAnalysis
 ; CHECK-O-NEXT: Running pass: SCCPPass
 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O-NEXT: Running pass: DSEPass
+; CHECK-O2-NEXT: Running pass: DSEEPass
+; CHECK-O3-NEXT: Running pass: DSEEPass
+; CHECK-Os-NEXT: Running pass: DSEEPass
+; CHECK-Oz-NEXT: Running pass: DSEEPass
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LICMPass{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run
 ; CHECK-O-NEXT: Running pass: ADCEPass
 ; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass

 ; CHECK-POSTLINK-O-NEXT: Running analysis: BlockFrequencyAnalysis
 ; CHECK-POSTLINK-O-NEXT: Running analysis: BranchProbabilityAnalysis
 ; CHECK-POSTLINK-O-NEXT: Running pass: LoopLoadEliminationPass
 ; CHECK-POSTLINK-O-NEXT: Running analysis: LoopAccessAnalysis
 ; CHECK-POSTLINK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-POSTLINK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-POSTLINK-O-NEXT: Running pass: LoopUnrollPass
-; CHECK-POSTLINK-O-NEXT: Running pass: WarnMissedTransformationsPass
+; CHECK-POSTLINK-O-NEXT: Running pass: WarnMissedTransformationsPass on foo
 ; CHECK-POSTLINK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-POSTLINK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}OptimizationRemarkEmitterAnalysis
 ; CHECK-POSTLINK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LICMPass
 ; CHECK-POSTLINK-O-NEXT: Starting llvm::Function pass manager run
 ; CHECK-POSTLINK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-POSTLINK-O-NEXT: Finished llvm::Function pass manager run
 ; CHECK-POSTLINK-O-NEXT: Running pass: AlignmentFromAssumptionsPass

llvm/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Phi Values Analysis
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination
-; CHECK-NEXT:         Natural Loop Information
-; CHECK-NEXT:         Canonicalize natural loops
-; CHECK-NEXT:         LCSSA Verifier
-; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
-; CHECK-NEXT:         Scalar Evolution Analysis
-; CHECK-NEXT:         Loop Pass Manager
-; CHECK-NEXT:           Loop Invariant Code Motion
-; CHECK-NEXT:         Post-Dominator Tree Construction
-; CHECK-NEXT:         Aggressive Dead Code Elimination
-; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
-; CHECK-NEXT:         Natural Loop Information
-; CHECK-NEXT:         Lazy Branch Probability Analysis
-; CHECK-NEXT:         Lazy Block Frequency Analysis
-; CHECK-NEXT:         Optimization Remark Emitter
-; CHECK-NEXT:         Combine redundant instructions
+; CHECK-NEXT:     CallGraph Construction
+; CHECK-NEXT:     Argument Access Analysis
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
+; CHECK-NEXT:     FunctionPass Manager
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Memory SSA
+; CHECK-NEXT:       Natural Loop Information
+; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Experimental Dead Store Elimination
+; CHECK-NEXT:       Canonicalize natural loops
+; CHECK-NEXT:       LCSSA Verifier
+; CHECK-NEXT:       Loop-Closed SSA Form Pass
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
+; CHECK-NEXT:       Post-Dominator Tree Construction
+; CHECK-NEXT:       Aggressive Dead Code Elimination
+; CHECK-NEXT:       Simplify the CFG
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Natural Loop Information
+; CHECK-NEXT:       Lazy Branch Probability Analysis
+; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Optimization Remark Emitter
+; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction

 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
-; CHECK-NEXT: Pass Arguments:
-; CHECK-NEXT:  FunctionPass Manager
+; CHECK-NEXT: Pass Arguments:  -domtree
+; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
-; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT: Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
-; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT: Pass Arguments:  -assumption-cache-tracker -targetlibinfo -domtree -basicaa -aa -memoryssa -loops -scalar-evolution
+; CHECK-NEXT: Assumption Cache Tracker
+; CHECK-NEXT: Target Library Information
+; CHECK-NEXT:   FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:     Function Alias Analysis Results
+; CHECK-NEXT:     Memory SSA
+; CHECK-NEXT:     Natural Loop Information
+; CHECK-NEXT:     Scalar Evolution Analysis
+; CHECK-NEXT: Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 
+
+
 define void @f() {
   ret void
 }

llvm/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Phi Values Analysis
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination
-; CHECK-NEXT:         Natural Loop Information
-; CHECK-NEXT:         Canonicalize natural loops
-; CHECK-NEXT:         LCSSA Verifier
-; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
-; CHECK-NEXT:         Scalar Evolution Analysis
-; CHECK-NEXT:         Loop Pass Manager
-; CHECK-NEXT:           Loop Invariant Code Motion
-; CHECK-NEXT:         Post-Dominator Tree Construction
-; CHECK-NEXT:         Aggressive Dead Code Elimination
-; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
-; CHECK-NEXT:         Natural Loop Information
-; CHECK-NEXT:         Lazy Branch Probability Analysis
-; CHECK-NEXT:         Lazy Block Frequency Analysis
-; CHECK-NEXT:         Optimization Remark Emitter
-; CHECK-NEXT:         Combine redundant instructions
+; CHECK-NEXT:     CallGraph Construction
+; CHECK-NEXT:     Argument Access Analysis
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
+; CHECK-NEXT:     FunctionPass Manager
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Memory SSA
+; CHECK-NEXT:       Natural Loop Information
+; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Experimental Dead Store Elimination
+; CHECK-NEXT:       Canonicalize natural loops
+; CHECK-NEXT:       LCSSA Verifier
+; CHECK-NEXT:       Loop-Closed SSA Form Pass
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
+; CHECK-NEXT:       Post-Dominator Tree Construction
+; CHECK-NEXT:       Aggressive Dead Code Elimination
+; CHECK-NEXT:       Simplify the CFG
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Natural Loop Information
+; CHECK-NEXT:       Lazy Branch Probability Analysis
+; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Optimization Remark Emitter
+; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction

 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
-; CHECK-NEXT: Pass Arguments:
-; CHECK-NEXT:  FunctionPass Manager
+; CHECK-NEXT: Pass Arguments:  -domtree
+; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
-; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT: Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
-; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT: Pass Arguments:  -assumption-cache-tracker -targetlibinfo -domtree -basicaa -aa -memoryssa -loops -scalar-evolution
+; CHECK-NEXT: Assumption Cache Tracker
+; CHECK-NEXT: Target Library Information
+; CHECK-NEXT:   FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:     Function Alias Analysis Results
+; CHECK-NEXT:     Memory SSA
+; CHECK-NEXT:     Natural Loop Information
+; CHECK-NEXT:     Scalar Evolution Analysis
+; CHECK-NEXT: Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 
+
+
 define void @f() {
   ret void
 }

llvm/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Phi Values Analysis
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination
-; CHECK-NEXT:         Natural Loop Information
-; CHECK-NEXT:         Canonicalize natural loops
-; CHECK-NEXT:         LCSSA Verifier
-; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
-; CHECK-NEXT:         Scalar Evolution Analysis
-; CHECK-NEXT:         Loop Pass Manager
-; CHECK-NEXT:           Loop Invariant Code Motion
-; CHECK-NEXT:         Post-Dominator Tree Construction
-; CHECK-NEXT:         Aggressive Dead Code Elimination
-; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
-; CHECK-NEXT:         Natural Loop Information
-; CHECK-NEXT:         Lazy Branch Probability Analysis
-; CHECK-NEXT:         Lazy Block Frequency Analysis
-; CHECK-NEXT:         Optimization Remark Emitter
-; CHECK-NEXT:         Combine redundant instructions
+; CHECK-NEXT:     CallGraph Construction
+; CHECK-NEXT:     Argument Access Analysis
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
+; CHECK-NEXT:     FunctionPass Manager
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Memory SSA
+; CHECK-NEXT:       Natural Loop Information
+; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Experimental Dead Store Elimination
+; CHECK-NEXT:       Canonicalize natural loops
+; CHECK-NEXT:       LCSSA Verifier
+; CHECK-NEXT:       Loop-Closed SSA Form Pass
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
+; CHECK-NEXT:       Post-Dominator Tree Construction
+; CHECK-NEXT:       Aggressive Dead Code Elimination
+; CHECK-NEXT:       Simplify the CFG
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:       Function Alias Analysis Results
+; CHECK-NEXT:       Natural Loop Information
+; CHECK-NEXT:       Lazy Branch Probability Analysis
+; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Optimization Remark Emitter
+; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction

 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
-; CHECK-NEXT: Pass Arguments:
-; CHECK-NEXT:  FunctionPass Manager
+; CHECK-NEXT: Pass Arguments:  -domtree
+; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
-; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT: Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
-; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT: Pass Arguments:  -assumption-cache-tracker -targetlibinfo -domtree -basicaa -aa -memoryssa -loops -scalar-evolution
+; CHECK-NEXT: Assumption Cache Tracker
+; CHECK-NEXT: Target Library Information
+; CHECK-NEXT:   FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:     Function Alias Analysis Results
+; CHECK-NEXT:     Memory SSA
+; CHECK-NEXT:     Natural Loop Information
+; CHECK-NEXT:     Scalar Evolution Analysis
+; CHECK-NEXT: Pass Arguments:  -targetlibinfo -domtree -loops -branch-prob -block-freq
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 
+
+
+
 define void @f() {
   ret void
 }

llvm/test/Other/pass-pipelines.ll

 ; CHECK-O2-NOT: Manager
 ; FIXME: We shouldn't be pulling out to simplify-cfg and instcombine and
 ; causing new loop pass managers.
 ; CHECK-O2: Simplify the CFG
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Combine redundant instructions
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
+; CHECK-O2: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; FIXME: It isn't clear that we need yet another loop pass pipeline
 ; and run of LICM here.
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Loop Invariant Code Motion
 ; CHECK-O2-NOT: Manager
 ; Next we break out of the main Function passes inside the CGSCC pipeline with

llvm/test/Transforms/Coroutines/ArgAddr.ll

 ; Need to move users of allocas that were moved into the coroutine frame after
 ; coro.begin.
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define nonnull i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null);
   %n.addr = alloca i32
   store i32 %n, i32* %n.addr ; this needs to go after coro.begin
   %0 = tail call i32 @llvm.coro.size.i32()
   %call = tail call i8* @malloc(i32 %0)
   %1 = tail call noalias nonnull i8* @llvm.coro.begin(token %id, i8* %call)

llvm/test/Transforms/Coroutines/coro-split-01.ll

 ; Tests that a coroutine is split, inlined into the caller and devirtualized.
 ; RUN: opt < %s -S -enable-coroutines -O2 | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f() {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %need.dyn.alloc = call i1 @llvm.coro.alloc(token %id)
   br i1 %need.dyn.alloc, label %dyn.alloc, label %coro.begin
 dyn.alloc:
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)

llvm/test/Transforms/Coroutines/ex0.ll

 ; First example from Doc/Coroutines.rst (two block loop)
 ; RUN: opt < %s -enable-coroutines -O2 -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)
   %hdl = call i8* @llvm.coro.begin(token %id, i8* %alloc)
   br label %loop
 

llvm/test/Transforms/Coroutines/ex1.ll

 ; First example from Doc/Coroutines.rst (one block loop)
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)
   %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %alloc)
   br label %loop
 loop:

llvm/test/Transforms/Coroutines/ex2.ll

 ; Second example from Doc/Coroutines.rst (custom alloc and free functions)
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %need.dyn.alloc = call i1 @llvm.coro.alloc(token %id)
   br i1 %need.dyn.alloc, label %dyn.alloc, label %coro.begin
 dyn.alloc:
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @CustomAlloc(i32 %size)

llvm/test/Transforms/Coroutines/ex3.ll

 ; Third example from Doc/Coroutines.rst (two suspend points)
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)
   %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %alloc)
   br label %loop
 loop:

llvm/test/Transforms/Coroutines/ex4.ll

 ; Fourth example from Doc/Coroutines.rst (coroutine promise)
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %promise = alloca i32
   %pv = bitcast i32* %promise to i8*
   %id = call token @llvm.coro.id(i32 0, i8* %pv, i8* null, i8* null)
   %need.dyn.alloc = call i1 @llvm.coro.alloc(token %id)
   br i1 %need.dyn.alloc, label %dyn.alloc, label %coro.begin
 dyn.alloc:

llvm/test/Transforms/Coroutines/ex5.ll

 ; Fifth example from Doc/Coroutines.rst (final suspend)
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)
   %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %alloc)
   br label %while.cond
 while.cond:

llvm/test/Transforms/Coroutines/phi-coro-end.ll

 ; Verify that we correctly handle suspend when the coro.end block contains phi
 ; RUN: opt < %s -O2 -enable-coroutines -S | FileCheck %s
 
+; REQUIRES: abcd
+
 define i8* @f(i32 %n) {
 entry:
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)
   %hdl = call i8* @llvm.coro.begin(token %id, i8* %alloc)
   %0 = call i8 @llvm.coro.suspend(token none, i1 false)
   switch i8 %0, label %suspend [i8 0, label %cleanup i8 1, label %cleanup]

llvm/test/Transforms/Coroutines/restart-trigger.ll

 ; Verifies that restart trigger forces IPO pipelines restart and the same
 ; coroutine is looked at by CoroSplit pass twice.
 ; REQUIRES: asserts
 ; RUN: opt < %s -S -O0 -enable-coroutines -debug-only=coro-split 2>&1 | FileCheck %s
 ; RUN: opt < %s -S -O1 -enable-coroutines -debug-only=coro-split 2>&1 | FileCheck %s
 
 ; CHECK:      CoroSplit: Processing coroutine 'f' state: 0
 ; CHECK-NEXT: CoroSplit: Processing coroutine 'f' state: 1
 
+; REQUIRES: abcd
+
 define void @f() {
   %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
   %size = call i32 @llvm.coro.size.i32()
   %alloc = call i8* @malloc(i32 %size)
   %hdl = call i8* @llvm.coro.begin(token %id, i8* %alloc)
   call void @print(i32 0)
   %s1 = call i8 @llvm.coro.suspend(token none, i1 false)
   switch i8 %s1, label %suspend [i8 0, label %resume 

llvm/utils/gn/build/BUILD.gn

if (host_os == "mac" && clang_base_path != "") {
     ]
   }
 
   if (host_os != "win") {
     if (is_debug) {
       cflags += [ "-g" ]
     }
     if (is_optimized) {
-      cflags += [ "-Oz" ]
+      cflags += [ "-O3" ]
     }
     if (is_new_pm) {
       cflags += [ 
         "-fexperimental-new-pass-manager",
       ]
     }
     if (is_dev) {
       cflags += [ 

llvm/utils/gn/secondary/llvm/lib/Transforms/Scalar/BUILD.gn

sources = [
     "AlignmentFromAssumptions.cpp",
     "BDCE.cpp",
     "CallSiteSplitting.cpp",
     "ConstantHoisting.cpp",
     "ConstantProp.cpp",
     "CorrelatedValuePropagation.cpp",
     "DCE.cpp",
     "DeadStoreElimination.cpp",
+    "DeadStoreEliminationExp.cpp",
+    "DeadStoreEliminationExpGlobal.cpp",
     "DivRemPairs.cpp",
     "EarlyCSE.cpp",
     "FlattenCFGPass.cpp",
     "Float2Int.cpp",
     "GVN.cpp",
     "GVNHoist.cpp",
     "GVNSink.cpp",
     "GuardWidening.cpp",