[AA][Intrinsics] Add separate_storage assumptions.

[davidtgoldblatt]

Summary

This operand bundle on an assume informs alias analysis that the
arguments point to regions of memory that were allocated separately
(i.e. different heap allocations, different allocas, or different
globals).

As a safety measure, we leave the analysis flag-disabled by default.

[davidtgoldblatt]

Updating per review comments.

[lebedev.ri]

Missing langref changes.

[davidtgoldblatt]

Add langref change for separate_storage attribute.

[nikic]

llvm/include/llvm/IR/Attributes.td

183 ↗

(On Diff #478393)

It doesn't make sense to add an actual attribute for this. This would allow you to write something like define foo(ptr separate_storage %arg), and what is that supposed to mean?

We should allow separate_storage as an assume operand bundled only -- there's not fundamental reason why these bundled have to map onto attributes. That's just all we needed historically.

[nikic]

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

99

I don't think Loc without pointer is legal in this context. Should be fine to drop this check.

104

Hm, I wonder if we can use assumptionsFor() here?

[davidtgoldblatt]

Per review comments.

[davidtgoldblatt]

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

104

I think eventually we should be able to, but there's two things that make this tricky:

• I think the AssumptionCache assumes that the only value that matters for assumptionsFor is the first one (because of the param attribute background?), which would introduce a weird asymmetry in how we can use it.
• We care about the comparison after a getUnderlyingObject call, but the AssumptionCache doesn't trace through GEPs in findAffectedValues.

(plausibly other issues; I checked that naive attempts at assumptionsFor didn't work, but didn't dig as much into the why).

I think the right thing to do eventually is to rewrite the hints during InstCombine (which should fix issue 2 as well as just speeding things up), but figured it didn't make sense to add extra complication to the AssumptionCache to fix 1 until that was done.

[davidtgoldblatt]

Fix the LangRef changes -- left some junk lying around.

[nikic]

This looks basically fine to me. My one remaining concern here is compile-time impact. Adding a new SeparateStorageAliasAnalysis pass does add some overhead even if these assumptions are not used (the last two patches add about 0.2% overhead). I think we might be better off just folding this code into BasicAA at an appropriate place, which also saves a good bit of boilerplate.

llvm/docs/LangRef.rst

2514 ↗

(On Diff #481492)

Spurious newline.

2534 ↗

(On Diff #481492)

Spurious indent.

2602 ↗

(On Diff #481492)

Spurious newline

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

104

My thinking was that we add the underlying object as the affected value in the assumption cache, but your suggestion to strip that away in InstCombine does sound better.

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

2

I don't think you need to specify aa-pipeline here, it's in the default pipeline.

4

Data layout not necessary.

8

It would be preferable to make this an aa-eval test, to test AA directly, rather than a pass using it.

[davidtgoldblatt]

Movie logic into BasicAA.

[davidtgoldblatt]

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

8

This is a little hard in the aa-eval of today because of the flow-sensitivity; it can't just print out yes/no/maybe results for all pairs of pointers; it would have to do so out all program locations too. TBAA has a similar sort of issue, uses the same "use gvn to check effects rather than results" trick to get around it too.

The only aa-eval improvements I could think of were:

• Do the cubic-size "print AA result for every pair of pointers at every program location" output under a flag
• Have some sort of magic "print aa-eval results at this location" function

Both of which seemed like overkill, although I suppose the first is manageable so long as we make sure to keep any test cases sufficiently compact. WDYT?

[nikic]

LGTM

llvm/docs/LangRef.rst

2582 ↗

(On Diff #481769)

nit: double space

llvm/test/Analysis/BasicAA/separate_storage.ll

1 ↗

(On Diff #481769)

Please use update_test_checks.py to generate CHECK lines.

[nikic]

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

8

We could add a mode to print ModRef results rather than AliasResults (like we do for calls). But I think your current test is fine.

[davidtgoldblatt]

Fix langref nit, use update_test_checks.py.

[davidtgoldblatt]

Rebase, futz with parent diffs in arc for wenlei@.

[fhahn]

What's the plan for flipping the default for EnableSeparateStorageAnalysis?

llvm/include/llvm/Analysis/SeparateStorageAliasAnalysis.h

 // Interface to the separate storage alias analysis pass.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_SEPARATESTORAGEALIASANALYSIS
 #define LLVM_ANALYSIS_SEPARATESTORAGEALIASANALYSIS
 
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 /// A simple AA result that uses calls to the separate storage intrinsics.
 class SeparateStorageAAResult : public AAResultBase {
 public:
+  SeparateStorageAAResult(Function &F);
+
+  AliasResult aliasAt(const MemoryLocation &LocA, const MemoryLocation &LocB,
+                      const Instruction *I, AAQueryInfo &AAQI);
+
   bool invalidate(Function &, const PreservedAnalyses &,
                   FunctionAnalysisManager::Invalidator &) {
+    // The AA framework is otherwise stateless, and AA-dependent passes have
+    // gotten a little bit sloppy in their consideration of whether or not
+    // they're effective without alias analysis (and so rely on getCachedResult
+    // instead of getResult sort of haphazardly). This is extra bad in our case,
+    // since if we get invalidate it also invalidates the AAResults we're
+    // associated with, so we drop the stateless analyses too.
+    //
+    // For now, we just recompute on demand. We do this lazily, in the hope
+    // that maybe we can avoid it entirely.
+    //
+    // There's some ways we can make this less wasteful:
+    // - Generalize the AssumptionCache machinery work for separate-storage
+    //   assumptions too.
+    // - Make the PassManager know about "partially invalidated" results, which
+    //   then get recomputed the next time an analysis is requested via
+    //   getResult rather than getCachedResult.
+    // - Do a (one-time) module scan for separate-storage assumptions. If none
+    //   are present, we can skip any function-level scanning.
+    CachedState.reset();
     return false;
   }
+
+private:
+  struct State {
+    DominatorTree DT;
+    SmallVector<WeakVH, 4> Hints;
+  };
+
+  Function &F;
+  Optional<State> CachedState;
+
+  State &getState();
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class SeparateStorageAA : public AnalysisInfoMixin<SeparateStorageAA> {
   friend AnalysisInfoMixin<SeparateStorageAA>;
 
   static AnalysisKey Key;
 

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
                                         TTI::TargetCostKind CostKind) const {
     switch (ICA.getID()) {
     default:
       break;
     case Intrinsic::annotation:
     case Intrinsic::assume:
+    case Intrinsic::experimental_separate_storage: // facebook T130678741
     case Intrinsic::sideeffect:
     case Intrinsic::pseudoprobe:
     case Intrinsic::arithmetic_fence:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
     case Intrinsic::dbg_label:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
case Instruction::Load: {
       // If there is a non-register sized type, the cost estimation may expand
       // it to be several instructions to load into multiple registers on the
       // target.  But, if the only use of the load is a trunc instruction to a
       // register sized type, the instruction selector can combine these
       // instructions to be a single load.  So, in this case, we use the
       // destination type of the trunc instruction rather than the load to
       // accurately estimate the cost of this load instruction.
       if (CostKind == TTI::TCK_CodeSize && LI->hasOneUse() &&
-          !LoadType->isVectorTy()) {    
+          !LoadType->isVectorTy()) {
         if (const TruncInst *TI = dyn_cast<TruncInst>(*LI->user_begin()))
           LoadType = TI->getDestTy();
       }
       return TargetTTI->getMemoryOpCost(Opcode, LoadType, LI->getAlign(),
                                         LI->getPointerAddressSpace(), CostKind,
                                         {TTI::OK_AnyValue, TTI::OP_None}, I);
     }
     case Instruction::Select: {

llvm/include/llvm/IR/IntrinsicInst.h

bool isCommutative() const {
     case Intrinsic::smul_with_overflow:
     case Intrinsic::umul_with_overflow:
     case Intrinsic::smul_fix:
     case Intrinsic::umul_fix:
     case Intrinsic::smul_fix_sat:
     case Intrinsic::umul_fix_sat:
     case Intrinsic::fma:
     case Intrinsic::fmuladd:
+    case Intrinsic::experimental_separate_storage: // facebook T130678741
       return true;
     default:
       return false;
     }
   }
 
   /// Checks if the intrinsic is an annotation.
   bool isAssumeLikeIntrinsic() const {
     switch (getIntrinsicID()) {
     default: break;
     case Intrinsic::assume:
+    case Intrinsic::experimental_separate_storage: // facebook T130678741
     case Intrinsic::sideeffect:
     case Intrinsic::pseudoprobe:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
     case Intrinsic::dbg_label:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::lifetime_start:
public:
   static bool classof(const IntrinsicInst *I) {
     return I->getIntrinsicID() == Intrinsic::assume;
   }
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 };
 
+// facebook begin T130678741
+/// This represents the llvm.experimental.separate.storage intrinsic.
+class SeparateStorageInst : public IntrinsicInst {
+public:
+  static bool classof(const IntrinsicInst *I) {
+    return I->getIntrinsicID() == Intrinsic::experimental_separate_storage;
+  }
+  static bool classof(const Value *V) {
+    return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
+  }
+};
+// facebook end T130678741
+
 } // end namespace llvm
 
 #endif // LLVM_IR_INTRINSICINST_H

llvm/include/llvm/IR/Intrinsics.td

 
 def int_readcyclecounter : DefaultAttrsIntrinsic<[llvm_i64_ty]>;
 
 // The assume intrinsic is marked InaccessibleMemOnly so that proper control
 // dependencies will be maintained.
 def int_assume : DefaultAttrsIntrinsic<
     [], [llvm_i1_ty], [IntrInaccessibleMemOnly, NoUndef<ArgIndex<0>>]>;
 
+// facebook begin T130678741
+// No pointer derived from the first argument will alias any pointer derived
+// from the second.
+def int_experimental_separate_storage : DefaultAttrsIntrinsic<
+    [], [llvm_ptr_ty, llvm_ptr_ty], [IntrInaccessibleMemOnly]>;
+// facebook end T130678741
+
 // 'llvm.experimental.noalias.scope.decl' intrinsic: Inserted at the location of
 // noalias scope declaration. Makes it possible to identify that a noalias scope
 // is only valid inside the body of a loop.
 //
 // Purpose of the different arguments:
 // - arg0: id.scope: metadata representing the scope declaration.
 def int_experimental_noalias_scope_decl
     : DefaultAttrsIntrinsic<[], [llvm_metadata_ty],

llvm/lib/Analysis/MemorySSA.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // FIXME: We probably don't actually want MemorySSA to model these at all
     // (including creating MemoryAccesses for them): we just end up inventing
     // clobbers where they don't really exist at all. Please see D43269 for
     // context.
     switch (II->getIntrinsicID()) {
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::assume:
+    case Intrinsic::experimental_separate_storage: // facebook T130678741
     case Intrinsic::experimental_noalias_scope_decl:
     case Intrinsic::pseudoprobe:
       return false;
     case Intrinsic::dbg_addr:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_label:
     case Intrinsic::dbg_value:
       llvm_unreachable("debuginfo shouldn't have associated defs!");
MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
   // dependencies here.
   // FIXME: Replace this special casing with a more accurate modelling of
   // assume's control dependency.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default:
       break;
     case Intrinsic::assume:
+    case Intrinsic::experimental_separate_storage: // facebook T130678741
     case Intrinsic::experimental_noalias_scope_decl:
     case Intrinsic::pseudoprobe:
       return nullptr;
     }
   }
 
   // Using a nonstandard AA pipelines might leave us with unexpected modref
   // results for I, so add a check to not model instructions that may not read

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

 // facebook begin T130678741
 //===- SeparateStorageAliasAnalysis.cpp -----------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Implements the separate storage alias analysis pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/SeparateStorageAliasAnalysis.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/InitializePasses.h"
 
 using namespace llvm;
 
+static cl::opt<bool> EnableSeparateStorageAA("enable-separate-storage-aa",
+                                             cl::Hidden, cl::init(false));
+
+SeparateStorageAAResult::SeparateStorageAAResult(Function &F) : F(F) {}
+
+SeparateStorageAAResult::State &SeparateStorageAAResult::getState() {
+  if (!CachedState) {
+    CachedState.emplace();
+    CachedState.value().DT.recalculate(F);
+    for (BasicBlock &B : F)
+      for (Instruction &I : B)
+        if (SeparateStorageInst *SSI = dyn_cast<SeparateStorageInst>(&I))
+          CachedState.value().Hints.push_back(SSI);
+  }
+  return *CachedState;
+}
+
+AliasResult SeparateStorageAAResult::aliasAt(const MemoryLocation &LocA,
+                                             const MemoryLocation &LocB,
+                                             const Instruction *I,
+                                             AAQueryInfo &AAQI) {
+  if (!EnableSeparateStorageAA) {
+    return AAResultBase::aliasAt(LocA, LocB, I, AAQI);
+  }
+
+  const Value *PtrA = LocA.Ptr;
+  const Value *PtrB = LocB.Ptr;
+  if (!PtrA || !PtrB)
+    return AAResultBase::aliasAt(LocA, LocB, I, AAQI);
+
+  auto &State = getState();
+  const Value *UnderlyingA = getUnderlyingObject(PtrA);
+  const Value *UnderlyingB = getUnderlyingObject(PtrB);
+
+  for (WeakVH &VH : State.Hints) {
+    if (!VH)
+      continue;
+    auto *SSI = cast<SeparateStorageInst>(VH);
+    const Value *Hint0 = SSI->getOperand(0);
+    const Value *Hint1 = SSI->getOperand(1);
+    const Value *UnderlyingHint0 = getUnderlyingObject(Hint0);
+    const Value *UnderlyingHint1 = getUnderlyingObject(Hint1);
+
+    if (((UnderlyingA == UnderlyingHint0 && UnderlyingB == UnderlyingHint1) ||
+         (UnderlyingA == UnderlyingHint1 && UnderlyingB == UnderlyingHint0)) &&
+        isValidAssumeForContext(SSI, I, &State.DT))
+      return AliasResult::NoAlias;
+  }
+  return AAResultBase::aliasAt(LocA, LocB, I, AAQI);
+}
+
 AnalysisKey SeparateStorageAA::Key;
 
 SeparateStorageAAResult SeparateStorageAA::run(Function &F,
                                                FunctionAnalysisManager &AM) {
-  return SeparateStorageAAResult();
+  return SeparateStorageAAResult(F);
 }
-
 char SeparateStorageAAWrapperPass::ID = 0;
 INITIALIZE_PASS(SeparateStorageAAWrapperPass, "separatestorage-aa",
                 "Separate Storage Alias Analysis", false, true)
 
 FunctionPass *llvm::createSeparateStorageAAWrapperPass() {
   return new SeparateStorageAAWrapperPass();
 }
 
 SeparateStorageAAWrapperPass::SeparateStorageAAWrapperPass()
     : FunctionPass(ID) {
   initializeSeparateStorageAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 bool SeparateStorageAAWrapperPass::runOnFunction(Function &F) {
-  Result.reset(new SeparateStorageAAResult());
+  Result.reset(new SeparateStorageAAResult(F));
   return false;
 }
 
 void SeparateStorageAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
 }
 // facebook end T130678741

llvm/lib/CodeGen/Analysis.cpp

for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
     // Pseudo probe intrinsics do not block tail call optimization either.
     if (BBI->isDebugOrPseudoInst())
       continue;
     // A lifetime end, assume or noalias.decl intrinsic should not stop tail
     // call optimization.
     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
       if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
           II->getIntrinsicID() == Intrinsic::assume ||
+          // facebook begin T130678741
+          II->getIntrinsicID() == Intrinsic::experimental_separate_storage ||
+          // facebook end T130678741
           II->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl)
         continue;
     if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
         !isSafeToSpeculativelyExecute(&*BBI))
       return false;
   }
 
   const Function *F = ExitBB->getParent();

llvm/lib/CodeGen/CodeGenPrepare.cpp

while (CurInstIterator != BB.end()) {
       if (auto *Assume = dyn_cast<AssumeInst>(I)) {
         MadeChange = true;
         Value *Operand = Assume->getOperand(0);
         Assume->eraseFromParent();
 
         resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
           RecursivelyDeleteTriviallyDeadInstructions(Operand, TLInfo, nullptr);
         });
+      // facebook begin T130678741
+      } else if (auto *SSI = dyn_cast<SeparateStorageInst>(I)) {
+        MadeChange = true;
+        Value *Operand1 = SSI->getOperand(0);
+        Value *Operand2 = SSI->getOperand(1);
+        SSI->eraseFromParent();
+
+        resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
+          RecursivelyDeleteTriviallyDeadInstructions(Operand1, TLInfo, nullptr);
+          RecursivelyDeleteTriviallyDeadInstructions(Operand2, TLInfo, nullptr);
+        });
       }
+      // facebook end T130678741
     }
   }
   return MadeChange;
 }
 
 /// An instruction is about to be deleted, so remove all references to it in our
 /// GEP-tracking data strcutures.
 void CodeGenPrepare::removeAllAssertingVHReferences(Value *V) {
bool CodeGenPrepare::optimizeCallInst(CallInst *CI, ModifyDT &ModifiedDT) {
 
   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
   if (II) {
     switch (II->getIntrinsicID()) {
     default:
       break;
     case Intrinsic::assume:
       llvm_unreachable("llvm.assume should have been removed already");
+    // facebook begin T130678741
+    case Intrinsic::experimental_separate_storage:
+      llvm_unreachable("llvm.experimental.separate.storage should have been "
+                       "removed already");
+    // facebook end T130678741
     case Intrinsic::experimental_widenable_condition: {
       // Give up on future widening oppurtunties so that we can fold away dead
       // paths and merge blocks before going into block-local instruction
       // selection.
       if (II->use_empty()) {
         II->eraseFromParent();
         return true;
       }

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

bool IRTranslator::translateKnownIntrinsic(const CallInst &CI, Intrinsic::ID ID,
   case Intrinsic::launder_invariant_group:
   case Intrinsic::strip_invariant_group: {
     // Drop the intrinsic, but forward the value.
     MIRBuilder.buildCopy(getOrCreateVReg(CI),
                          getOrCreateVReg(*CI.getArgOperand(0)));
     return true;
   }
   case Intrinsic::assume:
+  case Intrinsic::experimental_separate_storage: // facebook T130678741
   case Intrinsic::experimental_noalias_scope_decl:
   case Intrinsic::var_annotation:
   case Intrinsic::sideeffect:
     // Discard annotate attributes, assumptions, and artificial side-effects.
     return true;
   case Intrinsic::read_volatile_register:
   case Intrinsic::read_register: {
     Value *Arg = CI.getArgOperand(0);

llvm/lib/CodeGen/IntrinsicLowering.cpp

void IntrinsicLowering::LowerIntrinsicCall(CallInst *CI) {
 
   case Intrinsic::annotation:
   case Intrinsic::ptr_annotation:
     // Just drop the annotation, but forward the value
     CI->replaceAllUsesWith(CI->getOperand(0));
     break;
 
   case Intrinsic::assume:
+  case Intrinsic::experimental_separate_storage: // facebook T130678741
   case Intrinsic::experimental_noalias_scope_decl:
   case Intrinsic::var_annotation:
     break;   // Strip out these intrinsics
 
   case Intrinsic::memcpy: {
     Type *IntPtr = DL.getIntPtrType(Context);
     Value *Size = Builder.CreateIntCast(CI->getArgOperand(2), IntPtr,
                                         /* isSigned */ false);

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) {
   case Intrinsic::lifetime_start:
   case Intrinsic::lifetime_end:
   // The donothing intrinsic does, well, nothing.
   case Intrinsic::donothing:
   // Neither does the sideeffect intrinsic.
   case Intrinsic::sideeffect:
   // Neither does the assume intrinsic; it's also OK not to codegen its operand.
   case Intrinsic::assume:
+  // facebook begin T130678741
+  // Ditto
+  case Intrinsic::experimental_separate_storage:
+  // facebook end T130678741
   // Neither does the llvm.experimental.noalias.scope.decl intrinsic
   case Intrinsic::experimental_noalias_scope_decl:
     return true;
   case Intrinsic::dbg_declare: {
     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
     assert(DI->getVariable() && "Missing variable");
     if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

#include "llvm/IR/VPIntrinsics.def"
   case Intrinsic::ptr_annotation:
   case Intrinsic::launder_invariant_group:
   case Intrinsic::strip_invariant_group:
     // Drop the intrinsic, but forward the value
     setValue(&I, getValue(I.getOperand(0)));
     return;
 
   case Intrinsic::assume:
+  case Intrinsic::experimental_separate_storage: // facebook T130678741
   case Intrinsic::experimental_noalias_scope_decl:
   case Intrinsic::var_annotation:
   case Intrinsic::sideeffect:
     // Discard annotate attributes, noalias scope declarations, assumptions, and
     // artificial side-effects.
     return;
 
   case Intrinsic::codeview_annotation: {

llvm/lib/IR/User.cpp

MutableArrayRef<uint8_t> User::getDescriptor() {
   auto *DI = reinterpret_cast<DescriptorInfo *>(getIntrusiveOperands()) - 1;
   assert(DI->SizeInBytes != 0 && "Should not have had a descriptor otherwise!");
 
   return MutableArrayRef<uint8_t>(
       reinterpret_cast<uint8_t *>(DI) - DI->SizeInBytes, DI->SizeInBytes);
 }
 
 bool User::isDroppable() const {
-  return isa<AssumeInst>(this) || isa<PseudoProbeInst>(this);
+  // facebook begin T130678741
+  return isa<AssumeInst>(this) || isa<SeparateStorageInst>(this) ||
+         isa<PseudoProbeInst>(this);
+  // facebook end T130678741
 }
 
 //===----------------------------------------------------------------------===//
 //                         User operator new Implementations
 //===----------------------------------------------------------------------===//
 
 void *User::allocateFixedOperandUser(size_t Size, unsigned Us,
                                      unsigned DescBytes) {

llvm/lib/IR/Value.cpp

if (auto *Assume = dyn_cast<AssumeInst>(U.getUser())) {
     unsigned OpNo = U.getOperandNo();
     if (OpNo == 0)
       U.set(ConstantInt::getTrue(Assume->getContext()));
     else {
       U.set(UndefValue::get(U.get()->getType()));
       CallInst::BundleOpInfo &BOI = Assume->getBundleOpInfoForOperand(OpNo);
       BOI.Tag = Assume->getContext().pImpl->getOrInsertBundleTag("ignore");
     }
-    return;
-  }
-
+    // facebook begin T130678741
+  } else if (auto *SSI = dyn_cast<SeparateStorageInst>(U.getUser())) {
+    U.set(Constant::getNullValue(U->getType()));
+  } else {
     llvm_unreachable("unkown droppable use");
   }
+  // facebook end T130678741
+}
 
 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
   // This can be computed either by scanning the instructions in BB, or by
   // scanning the use list of this Value. Both lists can be very long, but
   // usually one is quite short.
   //
   // Scan both lists simultaneously until one is exhausted. This limits the
   // search to the shorter list.
bool Value::canBeFreed() const {
   // With garbage collection, deallocation typically occurs solely at or after
   // safepoints.  If we're compiling for a collector which uses the
   // gc.statepoint infrastructure, safepoints aren't explicitly present
   // in the IR until after lowering from abstract to physical machine model.
   // The collector could chose to mix explicit deallocation and gc'd objects
   // which is why we need the explicit opt in on a per collector basis.
   if (!F->hasGC())
     return true;
-  
   const auto &GCName = F->getGC();
   if (GCName == "statepoint-example") {
     auto *PT = cast<PointerType>(this->getType());
     if (PT->getAddressSpace() != 1)
       // For the sake of this example GC, we arbitrarily pick addrspace(1) as
       // our GC managed heap.  This must match the same check in
       // RewriteStatepointsForGC (and probably needs better factored.)
       return true;

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (User *U : PI->users()) {
           case Intrinsic::memcpy:
           case Intrinsic::memset: {
             MemIntrinsic *MI = cast<MemIntrinsic>(II);
             if (MI->isVolatile() || MI->getRawDest() != PI)
               return false;
             [[fallthrough]];
           }
           case Intrinsic::assume:
+          case Intrinsic::experimental_separate_storage: // facebook T130678741
           case Intrinsic::invariant_start:
           case Intrinsic::invariant_end:
           case Intrinsic::lifetime_start:
           case Intrinsic::lifetime_end:
           case Intrinsic::objectsize:
             Users.emplace_back(I);
             continue;
           case Intrinsic::launder_invariant_group:

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 bool isNoopIntrinsic(Instruction *I) {
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::invariant_end:
     case Intrinsic::launder_invariant_group:
     case Intrinsic::assume:
+    case Intrinsic::experimental_separate_storage: // facebook T130678741
       return true;
     case Intrinsic::dbg_addr:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_label:
     case Intrinsic::dbg_value:
       llvm_unreachable("Intrinsic should not be modeled in MemorySSA");
     default:
       return false;

llvm/lib/Transforms/Scalar/GVNHoist.cpp

for (Instruction &I1 : *BB) {
       if (auto *Load = dyn_cast<LoadInst>(&I1))
         LI.insert(Load, VN);
       else if (auto *Store = dyn_cast<StoreInst>(&I1))
         SI.insert(Store, VN);
       else if (auto *Call = dyn_cast<CallInst>(&I1)) {
         if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
           if (isa<DbgInfoIntrinsic>(Intr) ||
               Intr->getIntrinsicID() == Intrinsic::assume ||
+              // facebook begin T130678741
+              Intr->getIntrinsicID() ==
+                  Intrinsic::experimental_separate_storage ||
+              // facebook end T130678741
               Intr->getIntrinsicID() == Intrinsic::sideeffect)
             continue;
         }
         if (Call->mayHaveSideEffects())
           break;
 
         if (Call->isConvergent())
           break;

llvm/lib/Transforms/Scalar/SROA.cpp

bool visitIntrinsicInst(IntrinsicInst &II) {
     assert((II.isLifetimeStartOrEnd() || II.isDroppable()) &&
            "Unexpected intrinsic!");
     LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
 
     // Record this instruction for deletion.
     Pass.DeadInsts.push_back(&II);
 
     if (II.isDroppable()) {
-      assert(II.getIntrinsicID() == Intrinsic::assume && "Expected assume");
+      // facebook begin T130678741
+      assert((II.getIntrinsicID() == Intrinsic::experimental_separate_storage ||
+              II.getIntrinsicID() == Intrinsic::assume) &&
+             "Expected assume");
+      // facebook end T130678741
+
       // TODO For now we forget assumed information, this can be improved.
       OldPtr->dropDroppableUsesIn(II);
       return true;
     }
 
     assert(II.getArgOperand(1) == OldPtr);
     // Lifetime intrinsics are only promotable if they cover the whole alloca.
     // Therefore, we drop lifetime intrinsics which don't cover the whole

 ///
 /// We also record the alloca instructions deleted here so that they aren't
 /// subsequently handed to mem2reg to promote.
 bool SROAPass::deleteDeadInstructions(
     SmallPtrSetImpl<AllocaInst *> &DeletedAllocas) {
   bool Changed = false;
   while (!DeadInsts.empty()) {
     Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
-    if (!I) continue; 
+    if (!I) continue;
     LLVM_DEBUG(dbgs() << "Deleting dead instruction: " << *I << "\n");
 
     // If the instruction is an alloca, find the possible dbg.declare connected
     // to it, and remove it too. We must do this before calling RAUW or we will
     // not be able to find it.
     if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) {
       DeletedAllocas.insert(AI);
       for (DbgVariableIntrinsic *OldDII : FindDbgAddrUses(AI))

llvm/lib/Transforms/Utils/Evaluator.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
           }
           // Continue even if we do nothing.
           ++CurInst;
           continue;
         } else if (II->getIntrinsicID() == Intrinsic::assume) {
           LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
           ++CurInst;
           continue;
+          // facebook begin T130678741
+        } else if (II->getIntrinsicID() ==
+                   Intrinsic::experimental_separate_storage) {
+          LLVM_DEBUG(dbgs() << "Skipping separate storage intrinsic.\n");
+          ++CurInst;
+          continue;
+          // facebook end T130678741
         } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
           LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
           ++CurInst;
           continue;
         } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
           LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
           ++CurInst;
           continue;

llvm/test/Analysis/CostModel/X86/free-intrinsics.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -mtriple=x86_64-- -passes="print<cost-model>" 2>&1 -disable-output -cost-kind=code-size %s -S -o - | FileCheck %s --check-prefix=CHECK-SIZE
 ; RUN: opt -mtriple=x86_64-- -passes="print<cost-model>" 2>&1 -disable-output -cost-kind=throughput %s -S -o - | FileCheck %s --check-prefix=CHECK-THROUGHPUT
 
 define i32 @trivially_free() {
 ; CHECK-SIZE-LABEL: 'trivially_free'
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a0 = call i32 @llvm.annotation.i32(i32 undef, i8* undef, i8* undef, i32 undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.assume(i1 undef)
+; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.experimental.separate.storage(i8* undef, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.experimental.noalias.scope.decl(metadata !0)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.sideeffect()
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a1 = call {}* @llvm.invariant.start.p0i8(i64 1, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.invariant.end.p0i8({}* undef, i64 1, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a2 = call i8* @llvm.launder.invariant.group.p0i8(i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a3 = call i8* @llvm.strip.invariant.group.p0i8(i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a4 = call i1 @llvm.is.constant.i32(i32 undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.lifetime.start.p0i8(i64 1, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.lifetime.end.p0i8(i64 1, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a5 = call i64 @llvm.objectsize.i64.p0i8(i8* undef, i1 true, i1 true, i1 true)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a6 = call i8* @llvm.ptr.annotation.p0i8(i8* undef, i8* undef, i8* undef, i32 undef, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.var.annotation(i8* undef, i8* undef, i8* undef, i32 undef, i8* undef)
 ; CHECK-SIZE-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret i32 undef
 ;
 ; CHECK-THROUGHPUT-LABEL: 'trivially_free'
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a0 = call i32 @llvm.annotation.i32(i32 undef, i8* undef, i8* undef, i32 undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.assume(i1 undef)
+; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.experimental.separate.storage(i8* undef, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.experimental.noalias.scope.decl(metadata !0)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.sideeffect()
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a1 = call {}* @llvm.invariant.start.p0i8(i64 1, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.invariant.end.p0i8({}* undef, i64 1, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a2 = call i8* @llvm.launder.invariant.group.p0i8(i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a3 = call i8* @llvm.strip.invariant.group.p0i8(i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a4 = call i1 @llvm.is.constant.i32(i32 undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.lifetime.start.p0i8(i64 1, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.lifetime.end.p0i8(i64 1, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a5 = call i64 @llvm.objectsize.i64.p0i8(i8* undef, i1 true, i1 true, i1 true)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %a6 = call i8* @llvm.ptr.annotation.p0i8(i8* undef, i8* undef, i8* undef, i32 undef, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: call void @llvm.var.annotation(i8* undef, i8* undef, i8* undef, i32 undef, i8* undef)
 ; CHECK-THROUGHPUT-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i32 undef
 ;
   %a0 = call i32 @llvm.annotation.i32(i32 undef, i8* undef, i8* undef, i32 undef)
   call void @llvm.assume(i1 undef)
+  ; facebook begin T130678741
+  call void @llvm.experimental.separate.storage(i8* undef, i8* undef)
+  ; facebook end T130678741
   call void @llvm.experimental.noalias.scope.decl(metadata !4)
   call void @llvm.sideeffect()
   call void @llvm.dbg.declare(metadata i8** undef, metadata !0, metadata !DIExpression())
   call void @llvm.dbg.value(metadata i64 undef, i64 undef, metadata !DIExpression(), metadata !DIExpression())
   call void @llvm.dbg.label(metadata !2)
   %a1 = call {}* @llvm.invariant.start.p0i8(i64 1, i8* undef)
   call void @llvm.invariant.end.p0i8({}* undef, i64 1, i8* undef)
   %a2 = call i8* @llvm.launder.invariant.group.p0i8(i8* undef)
   %a3 = call i8* @llvm.strip.invariant.group.p0i8(i8* undef)
   %a4 = call i1 @llvm.is.constant.i32(i32 undef)
   call void @llvm.lifetime.start.p0i8(i64 1, i8* undef)
   call void @llvm.lifetime.end.p0i8(i64 1, i8* undef)
   %a5 = call i64 @llvm.objectsize.i64.p0i8(i8* undef, i1 1, i1 1, i1 1)
   %a6 = call i8* @llvm.ptr.annotation.p0i8(i8* undef, i8* undef, i8* undef, i32 undef, i8* undef)
   call void @llvm.var.annotation(i8* undef, i8* undef, i8* undef, i32 undef, i8* undef)
   ret i32 undef
 }
 
 declare i32 @llvm.annotation.i32(i32, i8*, i8*, i32)
 declare void @llvm.assume(i1)
+; facebook begin T130678741
+declare void @llvm.experimental.separate.storage(i8*, i8*)
+; facebook end T130678741
 declare void @llvm.experimental.noalias.scope.decl(metadata)
 declare void @llvm.sideeffect()
 declare void @llvm.dbg.declare(metadata, metadata, metadata)
 declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
 declare void @llvm.dbg.label(metadata)
 declare {}* @llvm.invariant.start.p0i8(i64, i8*)
 declare void @llvm.invariant.end.p0i8({}*, i64, i8*)
 declare i8* @llvm.launder.invariant.group.p0i8(i8*)

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

+; facebook begin T130678741
+; RUN: opt < %s -aa-pipeline=separatestorage-aa,basic-aa -gvn -enable-separate-storage-aa -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+declare void @llvm.experimental.separate.storage(ptr, ptr)
+
+; Test basic queries.
+
+; CHECK-LAEBL: @simple_no
+; CHECK: ret i8 %loadofstore
+define i8 @simple_no(ptr %p1, ptr %p2) {
+entry:
+  store i8 0, ptr %p1
+  store i8 1, ptr %p2
+  %loadofstore = load i8, ptr %p1
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @simple_yes
+; CHECK: ret i8 0
+define i8 @simple_yes(ptr %p1, ptr %p2) {
+entry:
+  call void @llvm.experimental.separate.storage(ptr %p1, ptr %p2)
+  store i8 0, ptr %p1
+  store i8 1, ptr %p2
+  %loadofstore = load i8, ptr %p1
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @ptr_to_ptr_no
+; CHECK: ret i8 %loadofstore
+define i8 @ptr_to_ptr_no(ptr %pp) {
+entry:
+  %p_base = load ptr, ptr %pp
+  store i8 0, ptr %p_base
+  %p_base2 = load ptr, ptr %pp
+  %loadofstore = load i8, ptr %p_base2
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @ptr_to_ptr_yes
+; CHECK: ret i8 0
+define i8 @ptr_to_ptr_yes(ptr %pp) {
+entry:
+  %p_base = load ptr, ptr %pp
+  call void @llvm.experimental.separate.storage(ptr %p_base, ptr %pp)
+  store i8 0, ptr %p_base
+  %p_base2 = load ptr, ptr %pp
+  %loadofstore = load i8, ptr %p_base2
+  ret i8 %loadofstore
+}
+
+; The analysis should only kick in if executed (or will be executed) at the
+; given program point.
+
+; CHECK-LABEL: @flow_sensitive
+; CHECK: %loadofstore = phi i8 [ %loadofstore_true, %true_branch ], [ 33, %false_branch ]
+define i8 @flow_sensitive(ptr %p1, ptr %p2, i1 %cond) {
+entry:
+  br i1 %cond, label %true_branch, label %false_branch
+
+true_branch:
+  store i8 11, ptr %p1
+  store i8 22, ptr %p2
+  %loadofstore_true = load i8, ptr %p1
+  br label %endif
+
+false_branch:
+  call void @llvm.experimental.separate.storage(ptr %p1, ptr %p2)
+  store i8 33, ptr %p1
+  store i8 44, ptr %p2
+  %loadofstore_false = load i8, ptr %p1
+  br label %endif
+
+endif:
+  %loadofstore = phi i8 [ %loadofstore_true, %true_branch ], [ %loadofstore_false, %false_branch ]
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @flow_sensitive_with_dominator
+; CHECK: %loadofstore = phi i8 [ 11, %true_branch ], [ 33, %false_branch ]
+define i8 @flow_sensitive_with_dominator(ptr %p1, ptr %p2, i1 %cond) {
+entry:
+  call void @llvm.experimental.separate.storage(ptr %p1, ptr %p2)
+  br i1 %cond, label %true_branch, label %false_branch
+
+true_branch:
+  store i8 11, ptr %p1
+  store i8 22, ptr %p2
+  %loadofstore_true = load i8, ptr %p1
+  br label %endif
+
+false_branch:
+  store i8 33, ptr %p1
+  store i8 44, ptr %p2
+  %loadofstore_false = load i8, ptr %p1
+  br label %endif
+
+endif:
+  %loadofstore = phi i8 [ %loadofstore_true, %true_branch ], [ %loadofstore_false, %false_branch ]
+  ret i8 %loadofstore
+}
+
+; Hints are relative to entire regions of storage, not particular pointers
+; inside them. We should know that the whole ranges are disjoint given hints at
+; offsets.
+
+; CHECK-LABEL: @offset_agnostic
+; CHECK: ret i8 0
+define i8 @offset_agnostic(ptr %p1, ptr %p2) {
+  %access1 = getelementptr inbounds i8, ptr %p1, i64 12
+  %access2 = getelementptr inbounds i8, ptr %p2, i64 34
+
+  %hint1 = getelementptr inbounds i8, ptr %p1, i64 56
+  %hint2 = getelementptr inbounds i8, ptr %p2, i64 78
+  call void @llvm.experimental.separate.storage(ptr %hint1, ptr %hint2)
+
+  store i8 0, ptr %access1
+  store i8 1, ptr %access2
+  %loadofstore = load i8, ptr %access1
+  ret i8 %loadofstore
+}
+; facebook end T130678741

llvm/test/CodeGen/Generic/experimental-separate-storage.ll

+; facebook begin T130678741
+; RUN: llc < %s
+
+declare void @llvm.experimental.separate.storage(ptr, ptr)
+
+define void @f() {
+  call void @llvm.experimental.separate.storage(i8* undef, i8* undef)
+  ret void
+}
+; facebook end T130678741