Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -37,6 +37,7 @@ class Loop; class LoopInfo; class MDNode; +class MemorySSA; class OptimizationRemarkEmitter; class StringRef; class TargetLibraryInfo; @@ -304,10 +305,12 @@ /// 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(V), DL, MaxLookup); + unsigned MaxLookup = 6, + const MemorySSA *MSSA = nullptr) { + return GetUnderlyingObject(const_cast(V), DL, MaxLookup, MSSA); } /// This method is similar to GetUnderlyingObject except that it can @@ -340,7 +343,8 @@ /// it shouldn't look through the phi above. void GetUnderlyingObjects(Value *V, SmallVectorImpl &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. Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #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" @@ -3445,7 +3446,8 @@ } 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) { @@ -3478,13 +3480,43 @@ } } - // See if InstructionSimplify knows any relevant tricks. - if (Instruction *I = dyn_cast(V)) + if (Instruction *I = dyn_cast(V)) { + // See if InstructionSimplify knows any relevant tricks. // 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(I); + if (MSSA && LI) { + // Make sure that the load is MemoryUse. + MemoryUse *MLoad = dyn_cast(MSSA->getMemoryAccess(LI)); + if (MLoad) { + // Check whether MemorySSA has any idea about this instruction. + Optional AR = MLoad->getOptimizedAccessType(); + MemoryAccess *MA = MLoad->getDefiningAccess(); + + // If def has 'MustAlias' relation with this use.. + if (AR && *AR == MustAlias && isa(MA)) { + // Check whether the def is store. + MemoryDef *MDef = dyn_cast(MA); + if (MDef != MSSA->getLiveOnEntryDef()) { + StoreInst *DefI = dyn_cast(MDef->getMemoryInst()); + if (DefI && DefI->getValueOperand()->getType()->isPointerTy()) { + V = DefI->getValueOperand(); + continue; + } + } + } + } + } + } return V; } @@ -3495,13 +3527,14 @@ void llvm::GetUnderlyingObjects(Value *V, SmallVectorImpl &Objects, const DataLayout &DL, LoopInfo *LI, - unsigned MaxLookup) { + unsigned MaxLookup, + const MemorySSA *MSSA) { SmallPtrSet Visited; SmallVector 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; Index: unittests/Analysis/ValueTrackingTest.cpp =================================================================== --- unittests/Analysis/ValueTrackingTest.cpp +++ unittests/Analysis/ValueTrackingTest.cpp @@ -7,8 +7,13 @@ // //===----------------------------------------------------------------------===// +#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" @@ -313,3 +318,71 @@ 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 MSSA = make_unique(*F, &AA, &DT); + + auto *PtrVal = + cast(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 MSSA = make_unique(*F, &AA, &DT); + + auto *PtrVal = + cast(F->getEntryBlock().getTerminator())->getOperand(0); + auto *UO = GetUnderlyingObject(PtrVal, DL, 6, &*MSSA); + Value *Ptr0Val = &*(++F->getEntryBlock().begin()); + EXPECT_EQ(UO, Ptr0Val); +}