Let GetUnderlyingObject/Objects use MemorySSA

[aqjune]

Summary

This patch makes GetUnderlyingObject/Objects use MemorySSA if it is given.

Any comment is welcome. :)

[hfinkel]

Seems like an interesting idea. What's the motivation for doing this?

I'm uneasy with making GetUnderlyingObject fundamentally more powerful than GetUnderlyingObjects - the latter should always provide a superset of the functionality of the former.

lib/Analysis/ValueTracking.cpp

3512

You can use dyn_cast_or_null here:

if (StoreInst *DefI = dyn_cast_or_null<StoreInst>(MDef->getMemoryInst())) {

[george.burgess.iv]

Thanks for this! In addition to Hal's comments...

lib/Analysis/ValueTracking.cpp

3500

This isn't always true: MSSA models volatile/atomic (>= monotonic) loads as MemoryDefs. Do we check for this elsewhere in this function?

If so, all of this can be collapsed into auto *MLoad = cast<MemoryUse>(MSSA->getMemoryAccess(LI));. If not, please make it a dyn_cast<MemoryUse>(MSSA->getMemoryAccess(LI)) + null check.

3511

Nit: I think it's way more common/somewhat more readable to say MDef != MSSA->getLiveOnEntry().

If any other Def/Use has a null MemoryInst, MSSA is probably broken. :)

[aqjune]

• Address comments
• Update the title
• Add a new test that deals with load volatile

[aqjune]

Thanks for the comments!

@hfinkel The motivation is that GetUnderlyingObject stucks at cases like this:

store i8* %p, i8** %q
%p2 = load i8*, i8** %q ; p2 is p

If we have MemorySSA, this can be resolved in constant time. I believe BasicAliasAnalysis can get benefit this, hence supporting partially flow sensitive analysis.

Regarding GetUnderlyingObjects - this patch contains update to help GetUnderlyingObjects use MemorySSA as well, by passing the argument into GetUnderlyingObject. I found that description/title of this patch wasn't containing the info. so I updated it.

[hfinkel]

In D50295#1188623, @aqjune wrote:

Thanks for the comments!

@hfinkel The motivation is that GetUnderlyingObject stucks at cases like this:

store i8* %p, i8** %q
%p2 = load i8*, i8** %q ; p2 is p

If we have MemorySSA, this can be resolved in constant time. I believe BasicAliasAnalysis can get benefit this, hence supporting partially flow sensitive analysis.

I read that in the comment ;) -- but why? Shouldn't all such cases be simplified by GVN (etc.) into a form where GetUnderlyingObjects, as is, can reason about them?

Regarding GetUnderlyingObjects - this patch contains update to help GetUnderlyingObjects use MemorySSA as well, by passing the argument into GetUnderlyingObject. I found that description/title of this patch wasn't containing the info. so I updated it.

[aqjune]

In D50295#1188969, @hfinkel wrote:

In D50295#1188623, @aqjune wrote:

store i8* %p, i8** %q
%p2 = load i8*, i8** %q ; p2 is p

If we have MemorySSA, this can be resolved in constant time. I believe BasicAliasAnalysis can get benefit this, hence supporting partially flow sensitive analysis.

I read that in the comment ;) -- but why? Shouldn't all such cases be simplified by GVN (etc.) into a form where GetUnderlyingObjects, as is, can reason about them?

Ideally, yes - but wouldn't eagerly removing such store-load pairs be costly?
A pair of store-load still remains in this example as well - https://godbolt.org/g/zutKyi (load i8*, i8** still remains)
Or I can search for a way to remove such pairs in more eager way, by adopting MemorySSA into InstSimplify or making GVN remove the pair in the example above.

[jdoerfert]

lib/Analysis/ValueTracking.cpp

3512

Couldn't the store write to more than just the values read by the load?
If so, do we need to take that into account?

include/llvm/Analysis/ValueTracking.h

 class DataLayout;
 class DominatorTree;
 class GEPOperator;
 class IntrinsicInst;
 struct KnownBits;
 class Loop;
 class LoopInfo;
 class MDNode;
+class MemorySSA;
 class OptimizationRemarkEmitter;
 class StringRef;
 class TargetLibraryInfo;
 class Value;
 
   /// Determine which bits of V are known to be either zero or one and return
   /// them in the KnownZero/KnownOne bit sets.
   ///
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
       ImmutableCallSite CS);
 
   /// This method strips off any GEP address adjustments and pointer casts from
   /// the specified value, returning the original object being addressed. Note
   /// that the returned value has pointer type if the specified value does. If
   /// the MaxLookup value is non-zero, it limits the number of instructions to
   /// be stripped off.
   Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
-                             unsigned MaxLookup = 6);
+                             unsigned MaxLookup = 6,
+                             const MemorySSA *MSSA = nullptr);
   inline const Value *GetUnderlyingObject(const Value *V, const DataLayout &DL,
-                                          unsigned MaxLookup = 6) {
-    return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup);
+                                          unsigned MaxLookup = 6,
+                                          const MemorySSA *MSSA = nullptr) {
+    return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup, MSSA);
   }
 
   /// This method is similar to GetUnderlyingObject except that it can
   /// look through phi and select instructions and return multiple objects.
   ///
   /// If LoopInfo is passed, loop phis are further analyzed.  If a pointer
   /// accesses different objects in each iteration, we don't look through the
   /// phi node. E.g. consider this loop nest:
class Value;
   ///     }
   ///   }
   ///
   /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
   /// should not assume that Curr and Prev share the same underlying object thus
   /// it shouldn't look through the phi above.
   void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                             const DataLayout &DL, LoopInfo *LI = nullptr,
-                            unsigned MaxLookup = 6);
+                            unsigned MaxLookup = 6,
+                            const MemorySSA *MSSA = nullptr);
 
   /// This is a wrapper around GetUnderlyingObjects and adds support for basic
   /// ptrtoint+arithmetic+inttoptr sequences.
   bool getUnderlyingObjectsForCodeGen(const Value *V,
                             SmallVectorImpl<Value *> &Objects,
                             const DataLayout &DL);
 
   /// Return true if the only users of this pointer are lifetime markers.

lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains routines that help analyze properties that chains of
 // computations have.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
 Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
-                                 unsigned MaxLookup) {
+                                 unsigned MaxLookup,
+                                 const MemorySSA *MSSA) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
         // cause weird miscompilations where 2 aliasing pointers are assumed to
         // noalias.
         if (auto *RP = getArgumentAliasingToReturnedPointer(CS)) {
           V = RP;
           continue;
         }
       }
 
+      if (Instruction *I = dyn_cast<Instruction>(V)) {
         // See if InstructionSimplify knows any relevant tricks.
-      if (Instruction *I = dyn_cast<Instruction>(V))
         // TODO: Acquire a DominatorTree and AssumptionCache and use them.
         if (Value *Simplified = SimplifyInstruction(I, {DL, I})) {
           V = Simplified;
           continue;
         }
+        // See whether the pointer is from load, and MemorySSA has
+        // information about the load.
+        // This can be helpful in cases like this:
+        //
+        // store i8* %p, i8** %q
+        // %p2 = load i8*, i8** %q ; p2 is p
+        LoadInst *LI = dyn_cast<LoadInst>(I);
+        if (MSSA && LI) {
+          // Make sure that the load is MemoryUse.
+          MemoryUse *MLoad = dyn_cast<MemoryUse>(MSSA->getMemoryAccess(LI));
+          if (MLoad) {
+            // Check whether MemorySSA has any idea about this instruction.
+            Optional<AliasResult> AR = MLoad->getOptimizedAccessType();
+            MemoryAccess *MA = MLoad->getDefiningAccess();
+
+             // If def has 'MustAlias' relation with this use..
+            if (AR && *AR == MustAlias && isa<MemoryDef>(MA)) {
+              // Check whether the def is store.
+              MemoryDef *MDef = dyn_cast<MemoryDef>(MA);
+              if (MDef != MSSA->getLiveOnEntryDef()) {
+                StoreInst *DefI = dyn_cast<StoreInst>(MDef->getMemoryInst());
+                if (DefI && DefI->getValueOperand()->getType()->isPointerTy()) {
+                  V = DefI->getValueOperand();
+                  continue;
+                }
+              }
+            }
+          }
+        }
+      }
 
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
 void llvm::GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                                 const DataLayout &DL, LoopInfo *LI,
-                                unsigned MaxLookup) {
+                                unsigned MaxLookup,
+                                const MemorySSA *MSSA) {
   SmallPtrSet<Value *, 4> Visited;
   SmallVector<Value *, 4> Worklist;
   Worklist.push_back(V);
   do {
     Value *P = Worklist.pop_back_val();
-    P = GetUnderlyingObject(P, DL, MaxLookup);
+    P = GetUnderlyingObject(P, DL, MaxLookup, MSSA);
 
     if (!Visited.insert(P).second)
       continue;
 
     if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
       Worklist.push_back(SI->getTrueValue());
       Worklist.push_back(SI->getFalseValue());
       continue;

unittests/Analysis/ValueTrackingTest.cpp

 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/KnownBits.h"
 #include "gtest/gtest.h"
TEST(ValueTracking, ComputeKnownMulBits) {
 
   auto *RVal =
       cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0);
   auto Known = computeKnownBits(RVal, M->getDataLayout());
   ASSERT_FALSE(Known.hasConflict());
   EXPECT_EQ(Known.One.getZExtValue(), 32u);
   EXPECT_EQ(Known.Zero.getZExtValue(), 95u);
 }
+
+TEST(ValueTracking, GetUnderlyingObject_MemSSA) {
+  StringRef Assembly = "define i32* @f(i32* %a, i32** %b) { "
+                       "  store i32 *%a, i32** %b "
+                       "  %a2 = load i32*, i32** %b "
+                       "  %a3 = getelementptr i32, i32* %a2 "
+                       "  ret i32* %a3"
+                       "} ";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  const DataLayout &DL = M->getDataLayout();
+
+  auto *F = M->getFunction("f");
+  assert(F && "Bad assembly?");
+
+  DominatorTree DT(*F);
+  AssumptionCache AC(*F);
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+  AAResults AA(TLI);
+  BasicAAResult BAA(DL, *F, TLI, AC, &DT);
+  AA.addAAResult(BAA);
+  std::unique_ptr<MemorySSA> MSSA = make_unique<MemorySSA>(*F, &AA, &DT);
+
+  auto *PtrVal =
+      cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0);
+  auto *UO = GetUnderlyingObject(PtrVal, DL, 6, &*MSSA);
+  Value *Ptr0Val = &*F->arg_begin();
+  EXPECT_EQ(UO, Ptr0Val);
+}
+
+TEST(ValueTracking, GetUnderlyingObject_MemSSA2) {
+  StringRef Assembly = "define i32* @f(i32* %a, i32** %b) { "
+                       "  store i32 *%a, i32** %b "
+                       "  %a2 = load volatile i32*, i32** %b "
+                       "  %a3 = getelementptr i32, i32* %a2 "
+                       "  ret i32* %a3"
+                       "} ";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  const DataLayout &DL = M->getDataLayout();
+
+  auto *F = M->getFunction("f");
+  assert(F && "Bad assembly?");
+
+  DominatorTree DT(*F);
+  AssumptionCache AC(*F);
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+  AAResults AA(TLI);
+  BasicAAResult BAA(DL, *F, TLI, AC, &DT);
+  AA.addAAResult(BAA);
+  std::unique_ptr<MemorySSA> MSSA = make_unique<MemorySSA>(*F, &AA, &DT);
+
+  auto *PtrVal =
+      cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0);
+  auto *UO = GetUnderlyingObject(PtrVal, DL, 6, &*MSSA);
+  Value *Ptr0Val = &*(++F->getEntryBlock().begin());
+  EXPECT_EQ(UO, Ptr0Val);
+}