1//===- MemorySSA.cpp - Unit tests for MemorySSA ---------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9#include "llvm/Transforms/Utils/MemorySSA.h"
10#include "llvm/Analysis/AliasAnalysis.h"
11#include "llvm/Analysis/BasicAliasAnalysis.h"
12#include "llvm/IR/BasicBlock.h"
13#include "llvm/IR/DataLayout.h"
14#include "llvm/IR/Dominators.h"
15#include "llvm/IR/IRBuilder.h"
16#include "llvm/IR/Instructions.h"
17#include "llvm/IR/LLVMContext.h"
18#include "gtest/gtest.h"
19
20using namespace llvm;
21
22const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128";
23
24/// There's a lot of common setup between these tests. This fixture helps reduce
25/// that. Tests should mock up a function, store it in F, and then call
26/// setupAnalyses().
27class MemorySSATest : public testing::Test {
28protected:
29  // N.B. Many of these members depend on each other (e.g. the Module depends on
30  // the Context, etc.). So, order matters here (and in TestAnalyses).
31  LLVMContext C;
32  Module M;
33  IRBuilder<> B;
34  DataLayout DL;
35  TargetLibraryInfoImpl TLII;
36  TargetLibraryInfo TLI;
37  Function *F;
38
39  // Things that we need to build after the function is created.
40  struct TestAnalyses {
41    DominatorTree DT;
42    AssumptionCache AC;
43    AAResults AA;
44    BasicAAResult BAA;
45    MemorySSA MSSA;
46    MemorySSAWalker *Walker;
47
48    TestAnalyses(MemorySSATest &Test)
49        : DT(*Test.F), AC(*Test.F), AA(Test.TLI),
50          BAA(Test.DL, Test.TLI, AC, &DT), MSSA(*Test.F, &AA, &DT) {
51      AA.addAAResult(BAA);
52      Walker = MSSA.getWalker();
53    }
54  };
55
56  std::unique_ptr<TestAnalyses> Analyses;
57
58  void setupAnalyses() {
59    assert(F);
60    Analyses.reset(new TestAnalyses(*this));
61  }
62
63public:
64  MemorySSATest()
65      : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
66};
67
68TEST_F(MemorySSATest, CreateALoadAndPhi) {
69  // We create a diamond where there is a store on one side, and then after
70  // running memory ssa, create a load after the merge point, and use it to test
71  // updating by creating an access for the load and a memoryphi.
72  F = Function::Create(
73      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
74      GlobalValue::ExternalLinkage, "F", &M);
75  BasicBlock *Entry(BasicBlock::Create(C, "", F));
76  BasicBlock *Left(BasicBlock::Create(C, "", F));
77  BasicBlock *Right(BasicBlock::Create(C, "", F));
78  BasicBlock *Merge(BasicBlock::Create(C, "", F));
79  B.SetInsertPoint(Entry);
80  B.CreateCondBr(B.getTrue(), Left, Right);
81  B.SetInsertPoint(Left);
82  Argument *PointerArg = &*F->arg_begin();
83  StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
84  BranchInst::Create(Merge, Left);
85  BranchInst::Create(Merge, Right);
86
87  setupAnalyses();
88  MemorySSA &MSSA = Analyses->MSSA;
89  // Add the load
90  B.SetInsertPoint(Merge);
91  LoadInst *LoadInst = B.CreateLoad(PointerArg);
92  // Should be no phi to start
93  EXPECT_EQ(MSSA.getMemoryAccess(Merge), nullptr);
94
95  // Create the phi
96  MemoryPhi *MP = MSSA.createMemoryPhi(Merge);
97  MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
98  MP->addIncoming(StoreAccess, Left);
99  MP->addIncoming(MSSA.getLiveOnEntryDef(), Right);
100
101  // Create the load memory acccess
102  MemoryUse *LoadAccess = cast<MemoryUse>(
103      MSSA.createMemoryAccessInBB(LoadInst, MP, Merge, MemorySSA::Beginning));
104  MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
105  EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
106  MSSA.verifyMemorySSA();
107}
108
109TEST_F(MemorySSATest, RemoveAPhi) {
110  // We create a diamond where there is a store on one side, and then a load
111  // after the merge point.  This enables us to test a bunch of different
112  // removal cases.
113  F = Function::Create(
114      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
115      GlobalValue::ExternalLinkage, "F", &M);
116  BasicBlock *Entry(BasicBlock::Create(C, "", F));
117  BasicBlock *Left(BasicBlock::Create(C, "", F));
118  BasicBlock *Right(BasicBlock::Create(C, "", F));
119  BasicBlock *Merge(BasicBlock::Create(C, "", F));
120  B.SetInsertPoint(Entry);
121  B.CreateCondBr(B.getTrue(), Left, Right);
122  B.SetInsertPoint(Left);
123  Argument *PointerArg = &*F->arg_begin();
124  StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
125  BranchInst::Create(Merge, Left);
126  BranchInst::Create(Merge, Right);
127  B.SetInsertPoint(Merge);
128  LoadInst *LoadInst = B.CreateLoad(PointerArg);
129
130  setupAnalyses();
131  MemorySSA &MSSA = Analyses->MSSA;
132  // Before, the load will be a use of a phi<store, liveonentry>.
133  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
134  MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
135  MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
136  EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
137  // Kill the store
138  MSSA.removeMemoryAccess(StoreAccess);
139  MemoryPhi *MP = cast<MemoryPhi>(DefiningAccess);
140  // Verify the phi ended up as liveonentry, liveonentry
141  for (auto &Op : MP->incoming_values())
142    EXPECT_TRUE(MSSA.isLiveOnEntryDef(cast<MemoryAccess>(Op.get())));
143  // Replace the phi uses with the live on entry def
144  MP->replaceAllUsesWith(MSSA.getLiveOnEntryDef());
145  // Verify the load is now defined by liveOnEntryDef
146  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
147  // Remove the PHI
148  MSSA.removeMemoryAccess(MP);
149  MSSA.verifyMemorySSA();
150}
151
152TEST_F(MemorySSATest, RemoveMemoryAccess) {
153  // We create a diamond where there is a store on one side, and then a load
154  // after the merge point.  This enables us to test a bunch of different
155  // removal cases.
156  F = Function::Create(
157      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
158      GlobalValue::ExternalLinkage, "F", &M);
159  BasicBlock *Entry(BasicBlock::Create(C, "", F));
160  BasicBlock *Left(BasicBlock::Create(C, "", F));
161  BasicBlock *Right(BasicBlock::Create(C, "", F));
162  BasicBlock *Merge(BasicBlock::Create(C, "", F));
163  B.SetInsertPoint(Entry);
164  B.CreateCondBr(B.getTrue(), Left, Right);
165  B.SetInsertPoint(Left);
166  Argument *PointerArg = &*F->arg_begin();
167  StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
168  BranchInst::Create(Merge, Left);
169  BranchInst::Create(Merge, Right);
170  B.SetInsertPoint(Merge);
171  LoadInst *LoadInst = B.CreateLoad(PointerArg);
172
173  setupAnalyses();
174  MemorySSA &MSSA = Analyses->MSSA;
175  MemorySSAWalker *Walker = Analyses->Walker;
176
177  // Before, the load will be a use of a phi<store, liveonentry>. It should be
178  // the same after.
179  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
180  MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
181  MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
182  EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
183  // The load is currently clobbered by one of the phi arguments, so the walker
184  // should determine the clobbering access as the phi.
185  EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst));
186  MSSA.removeMemoryAccess(StoreAccess);
187  MSSA.verifyMemorySSA();
188  // After the removeaccess, let's see if we got the right accesses
189  // The load should still point to the phi ...
190  EXPECT_EQ(DefiningAccess, LoadAccess->getDefiningAccess());
191  // but we should now get live on entry for the clobbering definition of the
192  // load, since it will walk past the phi node since every argument is the
193  // same.
194  EXPECT_TRUE(
195      MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
196
197  // The phi should now be a two entry phi with two live on entry defs.
198  for (const auto &Op : DefiningAccess->operands()) {
199    MemoryAccess *Operand = cast<MemoryAccess>(&*Op);
200    EXPECT_TRUE(MSSA.isLiveOnEntryDef(Operand));
201  }
202
203  // Now we try to remove the single valued phi
204  MSSA.removeMemoryAccess(DefiningAccess);
205  MSSA.verifyMemorySSA();
206  // Now the load should be a load of live on entry.
207  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
208}
209
210// We had a bug with caching where the walker would report MemoryDef#3's clobber
211// (below) was MemoryDef#1.
212//
213// define void @F(i8*) {
214//   %A = alloca i8, i8 1
215// ; 1 = MemoryDef(liveOnEntry)
216//   store i8 0, i8* %A
217// ; 2 = MemoryDef(1)
218//   store i8 1, i8* %A
219// ; 3 = MemoryDef(2)
220//   store i8 2, i8* %A
221// }
222TEST_F(MemorySSATest, TestTripleStore) {
223  F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
224                       GlobalValue::ExternalLinkage, "F", &M);
225  B.SetInsertPoint(BasicBlock::Create(C, "", F));
226  Type *Int8 = Type::getInt8Ty(C);
227  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
228  StoreInst *S1 = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
229  StoreInst *S2 = B.CreateStore(ConstantInt::get(Int8, 1), Alloca);
230  StoreInst *S3 = B.CreateStore(ConstantInt::get(Int8, 2), Alloca);
231
232  setupAnalyses();
233  MemorySSA &MSSA = Analyses->MSSA;
234  MemorySSAWalker *Walker = Analyses->Walker;
235
236  unsigned I = 0;
237  for (StoreInst *V : {S1, S2, S3}) {
238    // Everything should be clobbered by its defining access
239    MemoryAccess *DefiningAccess =
240        cast<MemoryUseOrDef>(MSSA.getMemoryAccess(V))->getDefiningAccess();
241    MemoryAccess *WalkerClobber = Walker->getClobberingMemoryAccess(V);
242    EXPECT_EQ(DefiningAccess, WalkerClobber)
243        << "Store " << I << " doesn't have the correct clobbering access";
244    // EXPECT_EQ expands such that if we increment I above, it won't get
245    // incremented except when we try to print the error message.
246    ++I;
247  }
248}
249
250// ...And fixing the above bug made it obvious that, when walking, MemorySSA's
251// walker was caching the initial node it walked. This was fine (albeit
252// mostly redundant) unless the initial node being walked is a clobber for the
253// query. In that case, we'd cache that the node clobbered itself.
254TEST_F(MemorySSATest, TestStoreAndLoad) {
255  F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
256                       GlobalValue::ExternalLinkage, "F", &M);
257  B.SetInsertPoint(BasicBlock::Create(C, "", F));
258  Type *Int8 = Type::getInt8Ty(C);
259  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
260  Instruction *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
261  Instruction *LI = B.CreateLoad(Alloca);
262
263  setupAnalyses();
264  MemorySSA &MSSA = Analyses->MSSA;
265  MemorySSAWalker *Walker = Analyses->Walker;
266
267  MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LI);
268  EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SI));
269  EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SI)));
270}
271
272// Another bug (related to the above two fixes): It was noted that, given the
273// following code:
274// ; 1 = MemoryDef(liveOnEntry)
275// store i8 0, i8* %1
276//
277// ...A query to getClobberingMemoryAccess(MemoryAccess*, MemoryLocation) would
278// hand back the store (correctly). A later call to
279// getClobberingMemoryAccess(const Instruction*) would also hand back the store
280// (incorrectly; it should return liveOnEntry).
281//
282// This test checks that repeated calls to either function returns what they're
283// meant to.
284TEST_F(MemorySSATest, TestStoreDoubleQuery) {
285  F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
286                       GlobalValue::ExternalLinkage, "F", &M);
287  B.SetInsertPoint(BasicBlock::Create(C, "", F));
288  Type *Int8 = Type::getInt8Ty(C);
289  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
290  StoreInst *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
291
292  setupAnalyses();
293  MemorySSA &MSSA = Analyses->MSSA;
294  MemorySSAWalker *Walker = Analyses->Walker;
295
296  MemoryAccess *StoreAccess = MSSA.getMemoryAccess(SI);
297  MemoryLocation StoreLoc = MemoryLocation::get(SI);
298  MemoryAccess *Clobber =
299      Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
300  MemoryAccess *LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
301
302  EXPECT_EQ(Clobber, StoreAccess);
303  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
304
305  // Try again (with entries in the cache already) for good measure...
306  Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
307  LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
308  EXPECT_EQ(Clobber, StoreAccess);
309  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
310}
311