1 //===- MemorySSA.cpp - Unit tests for MemorySSA ---------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 #include "llvm/Analysis/MemorySSA.h"
9 #include "llvm/Analysis/AliasAnalysis.h"
10 #include "llvm/Analysis/AssumptionCache.h"
11 #include "llvm/Analysis/BasicAliasAnalysis.h"
12 #include "llvm/Analysis/MemorySSAUpdater.h"
13 #include "llvm/Analysis/TargetLibraryInfo.h"
14 #include "llvm/AsmParser/Parser.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/DataLayout.h"
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/IR/IRBuilder.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/Support/SourceMgr.h"
22 #include "gtest/gtest.h"
23
24 using namespace llvm;
25
26 const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128";
27
28 /// There's a lot of common setup between these tests. This fixture helps reduce
29 /// that. Tests should mock up a function, store it in F, and then call
30 /// setupAnalyses().
31 class MemorySSATest : public testing::Test {
32 protected:
33 // N.B. Many of these members depend on each other (e.g. the Module depends on
34 // the Context, etc.). So, order matters here (and in TestAnalyses).
35 LLVMContext C;
36 Module M;
37 IRBuilder<> B;
38 DataLayout DL;
39 TargetLibraryInfoImpl TLII;
40 TargetLibraryInfo TLI;
41 Function *F;
42
43 // Things that we need to build after the function is created.
44 struct TestAnalyses {
45 DominatorTree DT;
46 AssumptionCache AC;
47 AAResults AA;
48 BasicAAResult BAA;
49 // We need to defer MSSA construction until AA is *entirely* set up, which
50 // requires calling addAAResult. Hence, we just use a pointer here.
51 std::unique_ptr<MemorySSA> MSSA;
52 MemorySSAWalker *Walker;
53
TestAnalysesMemorySSATest::TestAnalyses54 TestAnalyses(MemorySSATest &Test)
55 : DT(*Test.F), AC(*Test.F), AA(Test.TLI),
56 BAA(Test.DL, *Test.F, Test.TLI, AC, &DT) {
57 AA.addAAResult(BAA);
58 MSSA = std::make_unique<MemorySSA>(*Test.F, &AA, &DT);
59 Walker = MSSA->getWalker();
60 }
61 };
62
63 std::unique_ptr<TestAnalyses> Analyses;
64
setupAnalyses()65 void setupAnalyses() {
66 assert(F);
67 Analyses.reset(new TestAnalyses(*this));
68 }
69
70 public:
MemorySSATest()71 MemorySSATest()
72 : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
73 };
74
TEST_F(MemorySSATest,CreateALoad)75 TEST_F(MemorySSATest, CreateALoad) {
76 // We create a diamond where there is a store on one side, and then after
77 // building MemorySSA, create a load after the merge point, and use it to test
78 // updating by creating an access for the load.
79 F = Function::Create(
80 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
81 GlobalValue::ExternalLinkage, "F", &M);
82 BasicBlock *Entry(BasicBlock::Create(C, "", F));
83 BasicBlock *Left(BasicBlock::Create(C, "", F));
84 BasicBlock *Right(BasicBlock::Create(C, "", F));
85 BasicBlock *Merge(BasicBlock::Create(C, "", F));
86 B.SetInsertPoint(Entry);
87 B.CreateCondBr(B.getTrue(), Left, Right);
88 B.SetInsertPoint(Left);
89 Argument *PointerArg = &*F->arg_begin();
90 B.CreateStore(B.getInt8(16), PointerArg);
91 BranchInst::Create(Merge, Left);
92 BranchInst::Create(Merge, Right);
93
94 setupAnalyses();
95 MemorySSA &MSSA = *Analyses->MSSA;
96 MemorySSAUpdater Updater(&MSSA);
97 // Add the load
98 B.SetInsertPoint(Merge);
99 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);
100
101 // MemoryPHI should already exist.
102 MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
103 EXPECT_NE(MP, nullptr);
104
105 // Create the load memory acccess
106 MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
107 LoadInst, MP, Merge, MemorySSA::Beginning));
108 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
109 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
110 MSSA.verifyMemorySSA();
111 }
TEST_F(MemorySSATest,CreateLoadsAndStoreUpdater)112 TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
113 // We create a diamond, then build memoryssa with no memory accesses, and
114 // incrementally update it by inserting a store in the, entry, a load in the
115 // merge point, then a store in the branch, another load in the merge point,
116 // and then a store in the entry.
117 F = Function::Create(
118 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
119 GlobalValue::ExternalLinkage, "F", &M);
120 BasicBlock *Entry(BasicBlock::Create(C, "", F));
121 BasicBlock *Left(BasicBlock::Create(C, "", F));
122 BasicBlock *Right(BasicBlock::Create(C, "", F));
123 BasicBlock *Merge(BasicBlock::Create(C, "", F));
124 B.SetInsertPoint(Entry);
125 B.CreateCondBr(B.getTrue(), Left, Right);
126 B.SetInsertPoint(Left, Left->begin());
127 Argument *PointerArg = &*F->arg_begin();
128 B.SetInsertPoint(Left);
129 B.CreateBr(Merge);
130 B.SetInsertPoint(Right);
131 B.CreateBr(Merge);
132
133 setupAnalyses();
134 MemorySSA &MSSA = *Analyses->MSSA;
135 MemorySSAUpdater Updater(&MSSA);
136 // Add the store
137 B.SetInsertPoint(Entry, Entry->begin());
138 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
139 MemoryAccess *EntryStoreAccess = Updater.createMemoryAccessInBB(
140 EntryStore, nullptr, Entry, MemorySSA::Beginning);
141 Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));
142
143 // Add the load
144 B.SetInsertPoint(Merge, Merge->begin());
145 LoadInst *FirstLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);
146
147 // MemoryPHI should not already exist.
148 MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
149 EXPECT_EQ(MP, nullptr);
150
151 // Create the load memory access
152 MemoryUse *FirstLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
153 FirstLoad, nullptr, Merge, MemorySSA::Beginning));
154 Updater.insertUse(FirstLoadAccess);
155 // Should just have a load using the entry access, because it should discover
156 // the phi is trivial
157 EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess);
158
159 // Create a store on the left
160 // Add the store
161 B.SetInsertPoint(Left, Left->begin());
162 StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
163 MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB(
164 LeftStore, nullptr, Left, MemorySSA::Beginning);
165 Updater.insertDef(cast<MemoryDef>(LeftStoreAccess), false);
166
167 // MemoryPHI should exist after adding LeftStore.
168 MP = MSSA.getMemoryAccess(Merge);
169 EXPECT_NE(MP, nullptr);
170
171 // Add the second load
172 B.SetInsertPoint(Merge, Merge->begin());
173 LoadInst *SecondLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);
174
175 // Create the load memory access
176 MemoryUse *SecondLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
177 SecondLoad, nullptr, Merge, MemorySSA::Beginning));
178 Updater.insertUse(SecondLoadAccess);
179 // Now the load should be a phi of the entry store and the left store
180 MemoryPhi *MergePhi =
181 dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
182 EXPECT_NE(MergePhi, nullptr);
183 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
184 EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
185 // Now create a store below the existing one in the entry
186 B.SetInsertPoint(Entry, --Entry->end());
187 StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg);
188 MemoryAccess *SecondEntryStoreAccess = Updater.createMemoryAccessInBB(
189 SecondEntryStore, nullptr, Entry, MemorySSA::End);
190 // Insert it twice just to test renaming
191 Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), false);
192 EXPECT_NE(FirstLoadAccess->getDefiningAccess(), MergePhi);
193 Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), true);
194 EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), MergePhi);
195 // and make sure the phi below it got updated, despite being blocks away
196 MergePhi = dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
197 EXPECT_NE(MergePhi, nullptr);
198 EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess);
199 EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
200 MSSA.verifyMemorySSA();
201 }
202
TEST_F(MemorySSATest,CreateALoadUpdater)203 TEST_F(MemorySSATest, CreateALoadUpdater) {
204 // We create a diamond, then build memoryssa with no memory accesses, and
205 // incrementally update it by inserting a store in one of the branches, and a
206 // load in the merge point
207 F = Function::Create(
208 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
209 GlobalValue::ExternalLinkage, "F", &M);
210 BasicBlock *Entry(BasicBlock::Create(C, "", F));
211 BasicBlock *Left(BasicBlock::Create(C, "", F));
212 BasicBlock *Right(BasicBlock::Create(C, "", F));
213 BasicBlock *Merge(BasicBlock::Create(C, "", F));
214 B.SetInsertPoint(Entry);
215 B.CreateCondBr(B.getTrue(), Left, Right);
216 B.SetInsertPoint(Left, Left->begin());
217 Argument *PointerArg = &*F->arg_begin();
218 B.SetInsertPoint(Left);
219 B.CreateBr(Merge);
220 B.SetInsertPoint(Right);
221 B.CreateBr(Merge);
222
223 setupAnalyses();
224 MemorySSA &MSSA = *Analyses->MSSA;
225 MemorySSAUpdater Updater(&MSSA);
226 B.SetInsertPoint(Left, Left->begin());
227 // Add the store
228 StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
229 MemoryAccess *StoreAccess =
230 Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
231 Updater.insertDef(cast<MemoryDef>(StoreAccess));
232
233 // MemoryPHI should be created when inserting the def
234 MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
235 EXPECT_NE(MP, nullptr);
236
237 // Add the load
238 B.SetInsertPoint(Merge, Merge->begin());
239 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);
240
241 // Create the load memory acccess
242 MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
243 LoadInst, nullptr, Merge, MemorySSA::Beginning));
244 Updater.insertUse(LoadAccess);
245 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
246 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
247 MSSA.verifyMemorySSA();
248 }
249
TEST_F(MemorySSATest,SinkLoad)250 TEST_F(MemorySSATest, SinkLoad) {
251 F = Function::Create(
252 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
253 GlobalValue::ExternalLinkage, "F", &M);
254 BasicBlock *Entry(BasicBlock::Create(C, "", F));
255 BasicBlock *Left(BasicBlock::Create(C, "", F));
256 BasicBlock *Right(BasicBlock::Create(C, "", F));
257 BasicBlock *Merge(BasicBlock::Create(C, "", F));
258 B.SetInsertPoint(Entry);
259 B.CreateCondBr(B.getTrue(), Left, Right);
260 B.SetInsertPoint(Left, Left->begin());
261 Argument *PointerArg = &*F->arg_begin();
262 B.SetInsertPoint(Left);
263 B.CreateBr(Merge);
264 B.SetInsertPoint(Right);
265 B.CreateBr(Merge);
266
267 // Load in left block
268 B.SetInsertPoint(Left, Left->begin());
269 LoadInst *LoadInst1 = B.CreateLoad(B.getInt8Ty(), PointerArg);
270 // Store in merge block
271 B.SetInsertPoint(Merge, Merge->begin());
272 B.CreateStore(B.getInt8(16), PointerArg);
273
274 setupAnalyses();
275 MemorySSA &MSSA = *Analyses->MSSA;
276 MemorySSAUpdater Updater(&MSSA);
277
278 // Mimic sinking of a load:
279 // - clone load
280 // - insert in "exit" block
281 // - insert in mssa
282 // - remove from original block
283
284 LoadInst *LoadInstClone = cast<LoadInst>(LoadInst1->clone());
285 Merge->getInstList().insert(Merge->begin(), LoadInstClone);
286 MemoryAccess * NewLoadAccess =
287 Updater.createMemoryAccessInBB(LoadInstClone, nullptr,
288 LoadInstClone->getParent(),
289 MemorySSA::Beginning);
290 Updater.insertUse(cast<MemoryUse>(NewLoadAccess));
291 MSSA.verifyMemorySSA();
292 Updater.removeMemoryAccess(MSSA.getMemoryAccess(LoadInst1));
293 MSSA.verifyMemorySSA();
294 }
295
TEST_F(MemorySSATest,MoveAStore)296 TEST_F(MemorySSATest, MoveAStore) {
297 // We create a diamond where there is a in the entry, a store on one side, and
298 // a load at the end. After building MemorySSA, we test updating by moving
299 // the store from the side block to the entry block. This destroys the old
300 // access.
301 F = Function::Create(
302 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
303 GlobalValue::ExternalLinkage, "F", &M);
304 BasicBlock *Entry(BasicBlock::Create(C, "", F));
305 BasicBlock *Left(BasicBlock::Create(C, "", F));
306 BasicBlock *Right(BasicBlock::Create(C, "", F));
307 BasicBlock *Merge(BasicBlock::Create(C, "", F));
308 B.SetInsertPoint(Entry);
309 Argument *PointerArg = &*F->arg_begin();
310 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
311 B.CreateCondBr(B.getTrue(), Left, Right);
312 B.SetInsertPoint(Left);
313 StoreInst *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
314 BranchInst::Create(Merge, Left);
315 BranchInst::Create(Merge, Right);
316 B.SetInsertPoint(Merge);
317 B.CreateLoad(B.getInt8Ty(), PointerArg);
318 setupAnalyses();
319 MemorySSA &MSSA = *Analyses->MSSA;
320 MemorySSAUpdater Updater(&MSSA);
321 // Move the store
322 SideStore->moveBefore(Entry->getTerminator());
323 MemoryAccess *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
324 MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
325 MemoryAccess *NewStoreAccess = Updater.createMemoryAccessAfter(
326 SideStore, EntryStoreAccess, EntryStoreAccess);
327 EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
328 Updater.removeMemoryAccess(SideStoreAccess);
329 MSSA.verifyMemorySSA();
330 }
331
TEST_F(MemorySSATest,MoveAStoreUpdater)332 TEST_F(MemorySSATest, MoveAStoreUpdater) {
333 // We create a diamond where there is a in the entry, a store on one side, and
334 // a load at the end. After building MemorySSA, we test updating by moving
335 // the store from the side block to the entry block. This destroys the old
336 // access.
337 F = Function::Create(
338 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
339 GlobalValue::ExternalLinkage, "F", &M);
340 BasicBlock *Entry(BasicBlock::Create(C, "", F));
341 BasicBlock *Left(BasicBlock::Create(C, "", F));
342 BasicBlock *Right(BasicBlock::Create(C, "", F));
343 BasicBlock *Merge(BasicBlock::Create(C, "", F));
344 B.SetInsertPoint(Entry);
345 Argument *PointerArg = &*F->arg_begin();
346 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
347 B.CreateCondBr(B.getTrue(), Left, Right);
348 B.SetInsertPoint(Left);
349 auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
350 BranchInst::Create(Merge, Left);
351 BranchInst::Create(Merge, Right);
352 B.SetInsertPoint(Merge);
353 auto *MergeLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);
354 setupAnalyses();
355 MemorySSA &MSSA = *Analyses->MSSA;
356 MemorySSAUpdater Updater(&MSSA);
357
358 // Move the store
359 SideStore->moveBefore(Entry->getTerminator());
360 auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
361 auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
362 auto *NewStoreAccess = Updater.createMemoryAccessAfter(
363 SideStore, EntryStoreAccess, EntryStoreAccess);
364 // Before, the load will point to a phi of the EntryStore and SideStore.
365 auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
366 EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
367 MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
368 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
369 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
370 Updater.removeMemoryAccess(SideStoreAccess);
371 Updater.insertDef(cast<MemoryDef>(NewStoreAccess));
372 // After it's a phi of the new side store access.
373 EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);
374 EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess);
375 MSSA.verifyMemorySSA();
376 }
377
TEST_F(MemorySSATest,MoveAStoreUpdaterMove)378 TEST_F(MemorySSATest, MoveAStoreUpdaterMove) {
379 // We create a diamond where there is a in the entry, a store on one side, and
380 // a load at the end. After building MemorySSA, we test updating by moving
381 // the store from the side block to the entry block. This does not destroy
382 // the old access.
383 F = Function::Create(
384 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
385 GlobalValue::ExternalLinkage, "F", &M);
386 BasicBlock *Entry(BasicBlock::Create(C, "", F));
387 BasicBlock *Left(BasicBlock::Create(C, "", F));
388 BasicBlock *Right(BasicBlock::Create(C, "", F));
389 BasicBlock *Merge(BasicBlock::Create(C, "", F));
390 B.SetInsertPoint(Entry);
391 Argument *PointerArg = &*F->arg_begin();
392 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
393 B.CreateCondBr(B.getTrue(), Left, Right);
394 B.SetInsertPoint(Left);
395 auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
396 BranchInst::Create(Merge, Left);
397 BranchInst::Create(Merge, Right);
398 B.SetInsertPoint(Merge);
399 auto *MergeLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);
400 setupAnalyses();
401 MemorySSA &MSSA = *Analyses->MSSA;
402 MemorySSAUpdater Updater(&MSSA);
403
404 // Move the store
405 auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
406 auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
407 // Before, the load will point to a phi of the EntryStore and SideStore.
408 auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
409 EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
410 MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
411 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
412 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
413 SideStore->moveBefore(*EntryStore->getParent(), ++EntryStore->getIterator());
414 Updater.moveAfter(SideStoreAccess, EntryStoreAccess);
415 // After, it's a phi of the side store.
416 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
417 EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);
418
419 MSSA.verifyMemorySSA();
420 }
421
TEST_F(MemorySSATest,MoveAStoreAllAround)422 TEST_F(MemorySSATest, MoveAStoreAllAround) {
423 // We create a diamond where there is a in the entry, a store on one side, and
424 // a load at the end. After building MemorySSA, we test updating by moving
425 // the store from the side block to the entry block, then to the other side
426 // block, then to before the load. This does not destroy the old access.
427 F = Function::Create(
428 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
429 GlobalValue::ExternalLinkage, "F", &M);
430 BasicBlock *Entry(BasicBlock::Create(C, "", F));
431 BasicBlock *Left(BasicBlock::Create(C, "", F));
432 BasicBlock *Right(BasicBlock::Create(C, "", F));
433 BasicBlock *Merge(BasicBlock::Create(C, "", F));
434 B.SetInsertPoint(Entry);
435 Argument *PointerArg = &*F->arg_begin();
436 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
437 B.CreateCondBr(B.getTrue(), Left, Right);
438 B.SetInsertPoint(Left);
439 auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
440 BranchInst::Create(Merge, Left);
441 BranchInst::Create(Merge, Right);
442 B.SetInsertPoint(Merge);
443 auto *MergeLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);
444 setupAnalyses();
445 MemorySSA &MSSA = *Analyses->MSSA;
446 MemorySSAUpdater Updater(&MSSA);
447
448 // Move the store
449 auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
450 auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
451 // Before, the load will point to a phi of the EntryStore and SideStore.
452 auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
453 EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
454 MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
455 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
456 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
457 // Move the store before the entry store
458 SideStore->moveBefore(*EntryStore->getParent(), EntryStore->getIterator());
459 Updater.moveBefore(SideStoreAccess, EntryStoreAccess);
460 // After, it's a phi of the entry store.
461 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
462 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
463 MSSA.verifyMemorySSA();
464 // Now move the store to the right branch
465 SideStore->moveBefore(*Right, Right->begin());
466 Updater.moveToPlace(SideStoreAccess, Right, MemorySSA::Beginning);
467 MSSA.verifyMemorySSA();
468 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
469 EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);
470 // Now move it before the load
471 SideStore->moveBefore(MergeLoad);
472 Updater.moveBefore(SideStoreAccess, LoadAccess);
473 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
474 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
475 MSSA.verifyMemorySSA();
476 }
477
TEST_F(MemorySSATest,RemoveAPhi)478 TEST_F(MemorySSATest, RemoveAPhi) {
479 // We create a diamond where there is a store on one side, and then a load
480 // after the merge point. This enables us to test a bunch of different
481 // removal cases.
482 F = Function::Create(
483 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
484 GlobalValue::ExternalLinkage, "F", &M);
485 BasicBlock *Entry(BasicBlock::Create(C, "", F));
486 BasicBlock *Left(BasicBlock::Create(C, "", F));
487 BasicBlock *Right(BasicBlock::Create(C, "", F));
488 BasicBlock *Merge(BasicBlock::Create(C, "", F));
489 B.SetInsertPoint(Entry);
490 B.CreateCondBr(B.getTrue(), Left, Right);
491 B.SetInsertPoint(Left);
492 Argument *PointerArg = &*F->arg_begin();
493 StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
494 BranchInst::Create(Merge, Left);
495 BranchInst::Create(Merge, Right);
496 B.SetInsertPoint(Merge);
497 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);
498
499 setupAnalyses();
500 MemorySSA &MSSA = *Analyses->MSSA;
501 MemorySSAUpdater Updater(&MSSA);
502
503 // Before, the load will be a use of a phi<store, liveonentry>.
504 MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
505 MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
506 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
507 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
508 // Kill the store
509 Updater.removeMemoryAccess(StoreAccess);
510 MemoryPhi *MP = cast<MemoryPhi>(DefiningAccess);
511 // Verify the phi ended up as liveonentry, liveonentry
512 for (auto &Op : MP->incoming_values())
513 EXPECT_TRUE(MSSA.isLiveOnEntryDef(cast<MemoryAccess>(Op.get())));
514 // Replace the phi uses with the live on entry def
515 MP->replaceAllUsesWith(MSSA.getLiveOnEntryDef());
516 // Verify the load is now defined by liveOnEntryDef
517 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
518 // Remove the PHI
519 Updater.removeMemoryAccess(MP);
520 MSSA.verifyMemorySSA();
521 }
522
TEST_F(MemorySSATest,RemoveMemoryAccess)523 TEST_F(MemorySSATest, RemoveMemoryAccess) {
524 // We create a diamond where there is a store on one side, and then a load
525 // after the merge point. This enables us to test a bunch of different
526 // removal cases.
527 F = Function::Create(
528 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
529 GlobalValue::ExternalLinkage, "F", &M);
530 BasicBlock *Entry(BasicBlock::Create(C, "", F));
531 BasicBlock *Left(BasicBlock::Create(C, "", F));
532 BasicBlock *Right(BasicBlock::Create(C, "", F));
533 BasicBlock *Merge(BasicBlock::Create(C, "", F));
534 B.SetInsertPoint(Entry);
535 B.CreateCondBr(B.getTrue(), Left, Right);
536 B.SetInsertPoint(Left);
537 Argument *PointerArg = &*F->arg_begin();
538 StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
539 BranchInst::Create(Merge, Left);
540 BranchInst::Create(Merge, Right);
541 B.SetInsertPoint(Merge);
542 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);
543
544 setupAnalyses();
545 MemorySSA &MSSA = *Analyses->MSSA;
546 MemorySSAWalker *Walker = Analyses->Walker;
547 MemorySSAUpdater Updater(&MSSA);
548
549 // Before, the load will be a use of a phi<store, liveonentry>. It should be
550 // the same after.
551 MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
552 MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
553 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
554 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
555 // The load is currently clobbered by one of the phi arguments, so the walker
556 // should determine the clobbering access as the phi.
557 EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst));
558 Updater.removeMemoryAccess(StoreAccess);
559 MSSA.verifyMemorySSA();
560 // After the removeaccess, let's see if we got the right accesses
561 // The load should still point to the phi ...
562 EXPECT_EQ(DefiningAccess, LoadAccess->getDefiningAccess());
563 // but we should now get live on entry for the clobbering definition of the
564 // load, since it will walk past the phi node since every argument is the
565 // same.
566 // XXX: This currently requires either removing the phi or resetting optimized
567 // on the load
568
569 EXPECT_FALSE(
570 MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
571 // If we reset optimized, we get live on entry.
572 LoadAccess->resetOptimized();
573 EXPECT_TRUE(
574 MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
575 // The phi should now be a two entry phi with two live on entry defs.
576 for (const auto &Op : DefiningAccess->operands()) {
577 MemoryAccess *Operand = cast<MemoryAccess>(&*Op);
578 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Operand));
579 }
580
581 // Now we try to remove the single valued phi
582 Updater.removeMemoryAccess(DefiningAccess);
583 MSSA.verifyMemorySSA();
584 // Now the load should be a load of live on entry.
585 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
586 }
587
588 // We had a bug with caching where the walker would report MemoryDef#3's clobber
589 // (below) was MemoryDef#1.
590 //
591 // define void @F(i8*) {
592 // %A = alloca i8, i8 1
593 // ; 1 = MemoryDef(liveOnEntry)
594 // store i8 0, i8* %A
595 // ; 2 = MemoryDef(1)
596 // store i8 1, i8* %A
597 // ; 3 = MemoryDef(2)
598 // store i8 2, i8* %A
599 // }
TEST_F(MemorySSATest,TestTripleStore)600 TEST_F(MemorySSATest, TestTripleStore) {
601 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
602 GlobalValue::ExternalLinkage, "F", &M);
603 B.SetInsertPoint(BasicBlock::Create(C, "", F));
604 Type *Int8 = Type::getInt8Ty(C);
605 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
606 StoreInst *S1 = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
607 StoreInst *S2 = B.CreateStore(ConstantInt::get(Int8, 1), Alloca);
608 StoreInst *S3 = B.CreateStore(ConstantInt::get(Int8, 2), Alloca);
609
610 setupAnalyses();
611 MemorySSA &MSSA = *Analyses->MSSA;
612 MemorySSAWalker *Walker = Analyses->Walker;
613
614 unsigned I = 0;
615 for (StoreInst *V : {S1, S2, S3}) {
616 // Everything should be clobbered by its defining access
617 MemoryAccess *DefiningAccess = MSSA.getMemoryAccess(V)->getDefiningAccess();
618 MemoryAccess *WalkerClobber = Walker->getClobberingMemoryAccess(V);
619 EXPECT_EQ(DefiningAccess, WalkerClobber)
620 << "Store " << I << " doesn't have the correct clobbering access";
621 // EXPECT_EQ expands such that if we increment I above, it won't get
622 // incremented except when we try to print the error message.
623 ++I;
624 }
625 }
626
627 // ...And fixing the above bug made it obvious that, when walking, MemorySSA's
628 // walker was caching the initial node it walked. This was fine (albeit
629 // mostly redundant) unless the initial node being walked is a clobber for the
630 // query. In that case, we'd cache that the node clobbered itself.
TEST_F(MemorySSATest,TestStoreAndLoad)631 TEST_F(MemorySSATest, TestStoreAndLoad) {
632 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
633 GlobalValue::ExternalLinkage, "F", &M);
634 B.SetInsertPoint(BasicBlock::Create(C, "", F));
635 Type *Int8 = Type::getInt8Ty(C);
636 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
637 Instruction *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
638 Instruction *LI = B.CreateLoad(Int8, Alloca);
639
640 setupAnalyses();
641 MemorySSA &MSSA = *Analyses->MSSA;
642 MemorySSAWalker *Walker = Analyses->Walker;
643
644 MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LI);
645 EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SI));
646 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SI)));
647 }
648
649 // Another bug (related to the above two fixes): It was noted that, given the
650 // following code:
651 // ; 1 = MemoryDef(liveOnEntry)
652 // store i8 0, i8* %1
653 //
654 // ...A query to getClobberingMemoryAccess(MemoryAccess*, MemoryLocation) would
655 // hand back the store (correctly). A later call to
656 // getClobberingMemoryAccess(const Instruction*) would also hand back the store
657 // (incorrectly; it should return liveOnEntry).
658 //
659 // This test checks that repeated calls to either function returns what they're
660 // meant to.
TEST_F(MemorySSATest,TestStoreDoubleQuery)661 TEST_F(MemorySSATest, TestStoreDoubleQuery) {
662 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
663 GlobalValue::ExternalLinkage, "F", &M);
664 B.SetInsertPoint(BasicBlock::Create(C, "", F));
665 Type *Int8 = Type::getInt8Ty(C);
666 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
667 StoreInst *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
668
669 setupAnalyses();
670 MemorySSA &MSSA = *Analyses->MSSA;
671 MemorySSAWalker *Walker = Analyses->Walker;
672
673 MemoryAccess *StoreAccess = MSSA.getMemoryAccess(SI);
674 MemoryLocation StoreLoc = MemoryLocation::get(SI);
675 MemoryAccess *Clobber =
676 Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
677 MemoryAccess *LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
678
679 EXPECT_EQ(Clobber, StoreAccess);
680 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
681
682 // Try again (with entries in the cache already) for good measure...
683 Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
684 LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
685 EXPECT_EQ(Clobber, StoreAccess);
686 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
687 }
688
689 // Bug: During phi optimization, the walker wouldn't cache to the proper result
690 // in the farthest-walked BB.
691 //
692 // Specifically, it would assume that whatever we walked to was a clobber.
693 // "Whatever we walked to" isn't a clobber if we hit a cache entry.
694 //
695 // ...So, we need a test case that looks like:
696 // A
697 // / \
698 // B |
699 // \ /
700 // C
701 //
702 // Where, when we try to optimize a thing in 'C', a blocker is found in 'B'.
703 // The walk must determine that the blocker exists by using cache entries *while
704 // walking* 'B'.
TEST_F(MemorySSATest,PartialWalkerCacheWithPhis)705 TEST_F(MemorySSATest, PartialWalkerCacheWithPhis) {
706 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
707 GlobalValue::ExternalLinkage, "F", &M);
708 B.SetInsertPoint(BasicBlock::Create(C, "A", F));
709 Type *Int8 = Type::getInt8Ty(C);
710 Constant *One = ConstantInt::get(Int8, 1);
711 Constant *Zero = ConstantInt::get(Int8, 0);
712 Value *AllocA = B.CreateAlloca(Int8, One, "a");
713 Value *AllocB = B.CreateAlloca(Int8, One, "b");
714 BasicBlock *IfThen = BasicBlock::Create(C, "B", F);
715 BasicBlock *IfEnd = BasicBlock::Create(C, "C", F);
716
717 B.CreateCondBr(UndefValue::get(Type::getInt1Ty(C)), IfThen, IfEnd);
718
719 B.SetInsertPoint(IfThen);
720 Instruction *FirstStore = B.CreateStore(Zero, AllocA);
721 B.CreateStore(Zero, AllocB);
722 Instruction *ALoad0 = B.CreateLoad(Int8, AllocA, "");
723 Instruction *BStore = B.CreateStore(Zero, AllocB);
724 // Due to use optimization/etc. we make a store to A, which is removed after
725 // we build MSSA. This helps keep the test case simple-ish.
726 Instruction *KillStore = B.CreateStore(Zero, AllocA);
727 Instruction *ALoad = B.CreateLoad(Int8, AllocA, "");
728 B.CreateBr(IfEnd);
729
730 B.SetInsertPoint(IfEnd);
731 Instruction *BelowPhi = B.CreateStore(Zero, AllocA);
732
733 setupAnalyses();
734 MemorySSA &MSSA = *Analyses->MSSA;
735 MemorySSAWalker *Walker = Analyses->Walker;
736 MemorySSAUpdater Updater(&MSSA);
737
738 // Kill `KillStore`; it exists solely so that the load after it won't be
739 // optimized to FirstStore.
740 Updater.removeMemoryAccess(MSSA.getMemoryAccess(KillStore));
741 KillStore->eraseFromParent();
742 auto *ALoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(ALoad));
743 EXPECT_EQ(ALoadMA->getDefiningAccess(), MSSA.getMemoryAccess(BStore));
744
745 // Populate the cache for the store to AllocB directly after FirstStore. It
746 // should point to something in block B (so something in D can't be optimized
747 // to it).
748 MemoryAccess *Load0Clobber = Walker->getClobberingMemoryAccess(ALoad0);
749 EXPECT_EQ(MSSA.getMemoryAccess(FirstStore), Load0Clobber);
750
751 // If the bug exists, this will introduce a bad cache entry for %a on BStore.
752 // It will point to the store to %b after FirstStore. This only happens during
753 // phi optimization.
754 MemoryAccess *BottomClobber = Walker->getClobberingMemoryAccess(BelowPhi);
755 MemoryAccess *Phi = MSSA.getMemoryAccess(IfEnd);
756 EXPECT_EQ(BottomClobber, Phi);
757
758 // This query will first check the cache for {%a, BStore}. It should point to
759 // FirstStore, not to the store after FirstStore.
760 MemoryAccess *UseClobber = Walker->getClobberingMemoryAccess(ALoad);
761 EXPECT_EQ(UseClobber, MSSA.getMemoryAccess(FirstStore));
762 }
763
764 // Test that our walker properly handles loads with the invariant group
765 // attribute. It's a bit hacky, since we add the invariant attribute *after*
766 // building MSSA. Otherwise, the use optimizer will optimize it for us, which
767 // isn't what we want.
768 // FIXME: It may be easier/cleaner to just add an 'optimize uses?' flag to MSSA.
TEST_F(MemorySSATest,WalkerInvariantLoadOpt)769 TEST_F(MemorySSATest, WalkerInvariantLoadOpt) {
770 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
771 GlobalValue::ExternalLinkage, "F", &M);
772 B.SetInsertPoint(BasicBlock::Create(C, "", F));
773 Type *Int8 = Type::getInt8Ty(C);
774 Constant *One = ConstantInt::get(Int8, 1);
775 Value *AllocA = B.CreateAlloca(Int8, One, "");
776
777 Instruction *Store = B.CreateStore(One, AllocA);
778 Instruction *Load = B.CreateLoad(Int8, AllocA);
779
780 setupAnalyses();
781 MemorySSA &MSSA = *Analyses->MSSA;
782 MemorySSAWalker *Walker = Analyses->Walker;
783
784 auto *LoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(Load));
785 auto *StoreMA = cast<MemoryDef>(MSSA.getMemoryAccess(Store));
786 EXPECT_EQ(LoadMA->getDefiningAccess(), StoreMA);
787
788 // ...At the time of writing, no cache should exist for LoadMA. Be a bit
789 // flexible to future changes.
790 Walker->invalidateInfo(LoadMA);
791 Load->setMetadata(LLVMContext::MD_invariant_load, MDNode::get(C, {}));
792
793 MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LoadMA);
794 EXPECT_EQ(LoadClobber, MSSA.getLiveOnEntryDef());
795 }
796
797 // Test loads get reoptimized properly by the walker.
TEST_F(MemorySSATest,WalkerReopt)798 TEST_F(MemorySSATest, WalkerReopt) {
799 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
800 GlobalValue::ExternalLinkage, "F", &M);
801 B.SetInsertPoint(BasicBlock::Create(C, "", F));
802 Type *Int8 = Type::getInt8Ty(C);
803 Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
804 Instruction *SIA = B.CreateStore(ConstantInt::get(Int8, 0), AllocaA);
805 Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
806 Instruction *SIB = B.CreateStore(ConstantInt::get(Int8, 0), AllocaB);
807 Instruction *LIA = B.CreateLoad(Int8, AllocaA);
808
809 setupAnalyses();
810 MemorySSA &MSSA = *Analyses->MSSA;
811 MemorySSAWalker *Walker = Analyses->Walker;
812 MemorySSAUpdater Updater(&MSSA);
813
814 MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LIA);
815 MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LIA));
816 EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SIA));
817 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SIA)));
818 Updater.removeMemoryAccess(LoadAccess);
819
820 // Create the load memory access pointing to an unoptimized place.
821 MemoryUse *NewLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
822 LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));
823 // This should it cause it to be optimized
824 EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);
825 EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);
826 }
827
828 // Test out MemorySSAUpdater::moveBefore
TEST_F(MemorySSATest,MoveAboveMemoryDef)829 TEST_F(MemorySSATest, MoveAboveMemoryDef) {
830 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
831 GlobalValue::ExternalLinkage, "F", &M);
832 B.SetInsertPoint(BasicBlock::Create(C, "", F));
833
834 Type *Int8 = Type::getInt8Ty(C);
835 Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
836 Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
837 Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");
838
839 StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);
840 StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);
841 LoadInst *LoadB = B.CreateLoad(Int8, B_);
842 StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);
843 StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);
844 StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);
845 LoadInst *LoadC = B.CreateLoad(Int8, C);
846
847 setupAnalyses();
848 MemorySSA &MSSA = *Analyses->MSSA;
849 MemorySSAWalker &Walker = *Analyses->Walker;
850
851 MemorySSAUpdater Updater(&MSSA);
852 StoreC->moveBefore(StoreB);
853 Updater.moveBefore(cast<MemoryDef>(MSSA.getMemoryAccess(StoreC)),
854 cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)));
855
856 MSSA.verifyMemorySSA();
857
858 EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),
859 MSSA.getMemoryAccess(StoreC));
860 EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),
861 MSSA.getMemoryAccess(StoreA0));
862 EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),
863 MSSA.getMemoryAccess(StoreA1));
864 EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),
865 MSSA.getMemoryAccess(StoreB));
866 EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),
867 MSSA.getMemoryAccess(StoreC));
868
869 // exercise block numbering
870 EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),
871 MSSA.getMemoryAccess(StoreB)));
872 EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),
873 MSSA.getMemoryAccess(StoreA2)));
874 }
875
TEST_F(MemorySSATest,Irreducible)876 TEST_F(MemorySSATest, Irreducible) {
877 // Create the equivalent of
878 // x = something
879 // if (...)
880 // goto second_loop_entry
881 // while (...) {
882 // second_loop_entry:
883 // }
884 // use(x)
885
886 SmallVector<PHINode *, 8> Inserted;
887 IRBuilder<> B(C);
888 F = Function::Create(
889 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
890 GlobalValue::ExternalLinkage, "F", &M);
891
892 // Make blocks
893 BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
894 BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);
895 BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);
896 BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);
897 B.SetInsertPoint(IfBB);
898 B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);
899 B.SetInsertPoint(LoopStartBB);
900 B.CreateBr(LoopMainBB);
901 B.SetInsertPoint(LoopMainBB);
902 B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);
903 B.SetInsertPoint(AfterLoopBB);
904 Argument *FirstArg = &*F->arg_begin();
905 setupAnalyses();
906 MemorySSA &MSSA = *Analyses->MSSA;
907 MemorySSAUpdater Updater(&MSSA);
908 // Create the load memory acccess
909 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), FirstArg);
910 MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
911 LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
912 Updater.insertUse(LoadAccess);
913 MSSA.verifyMemorySSA();
914 }
915
TEST_F(MemorySSATest,MoveToBeforeLiveOnEntryInvalidatesCache)916 TEST_F(MemorySSATest, MoveToBeforeLiveOnEntryInvalidatesCache) {
917 // Create:
918 // %1 = alloca i8
919 // ; 1 = MemoryDef(liveOnEntry)
920 // store i8 0, i8* %1
921 // ; 2 = MemoryDef(1)
922 // store i8 0, i8* %1
923 //
924 // ...And be sure that MSSA's caching doesn't give us `1` for the clobber of
925 // `2` after `1` is removed.
926 IRBuilder<> B(C);
927 F = Function::Create(
928 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
929 GlobalValue::ExternalLinkage, "F", &M);
930
931 BasicBlock *Entry = BasicBlock::Create(C, "if", F);
932 B.SetInsertPoint(Entry);
933
934 Value *A = B.CreateAlloca(B.getInt8Ty());
935 StoreInst *StoreA = B.CreateStore(B.getInt8(0), A);
936 StoreInst *StoreB = B.CreateStore(B.getInt8(0), A);
937
938 setupAnalyses();
939
940 MemorySSA &MSSA = *Analyses->MSSA;
941
942 auto *DefA = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA));
943 auto *DefB = cast<MemoryDef>(MSSA.getMemoryAccess(StoreB));
944
945 MemoryAccess *BClobber = MSSA.getWalker()->getClobberingMemoryAccess(DefB);
946 ASSERT_EQ(DefA, BClobber);
947
948 MemorySSAUpdater(&MSSA).removeMemoryAccess(DefA);
949 StoreA->eraseFromParent();
950
951 EXPECT_EQ(DefB->getDefiningAccess(), MSSA.getLiveOnEntryDef());
952
953 EXPECT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(DefB),
954 MSSA.getLiveOnEntryDef())
955 << "(DefA = " << DefA << ")";
956 }
957
TEST_F(MemorySSATest,RemovingDefInvalidatesCache)958 TEST_F(MemorySSATest, RemovingDefInvalidatesCache) {
959 // Create:
960 // %x = alloca i8
961 // %y = alloca i8
962 // ; 1 = MemoryDef(liveOnEntry)
963 // store i8 0, i8* %x
964 // ; 2 = MemoryDef(1)
965 // store i8 0, i8* %y
966 // ; 3 = MemoryDef(2)
967 // store i8 0, i8* %x
968 //
969 // And be sure that MSSA's caching handles the removal of def `1`
970 // appropriately.
971 IRBuilder<> B(C);
972 F = Function::Create(
973 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
974 GlobalValue::ExternalLinkage, "F", &M);
975
976 BasicBlock *Entry = BasicBlock::Create(C, "if", F);
977 B.SetInsertPoint(Entry);
978
979 Value *X = B.CreateAlloca(B.getInt8Ty());
980 Value *Y = B.CreateAlloca(B.getInt8Ty());
981 StoreInst *StoreX1 = B.CreateStore(B.getInt8(0), X);
982 StoreInst *StoreY = B.CreateStore(B.getInt8(0), Y);
983 StoreInst *StoreX2 = B.CreateStore(B.getInt8(0), X);
984
985 setupAnalyses();
986
987 MemorySSA &MSSA = *Analyses->MSSA;
988
989 auto *DefX1 = cast<MemoryDef>(MSSA.getMemoryAccess(StoreX1));
990 auto *DefY = cast<MemoryDef>(MSSA.getMemoryAccess(StoreY));
991 auto *DefX2 = cast<MemoryDef>(MSSA.getMemoryAccess(StoreX2));
992
993 EXPECT_EQ(DefX2->getDefiningAccess(), DefY);
994 MemoryAccess *X2Clobber = MSSA.getWalker()->getClobberingMemoryAccess(DefX2);
995 ASSERT_EQ(DefX1, X2Clobber);
996
997 MemorySSAUpdater(&MSSA).removeMemoryAccess(DefX1);
998 StoreX1->eraseFromParent();
999
1000 EXPECT_EQ(DefX2->getDefiningAccess(), DefY);
1001 EXPECT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(DefX2),
1002 MSSA.getLiveOnEntryDef())
1003 << "(DefX1 = " << DefX1 << ")";
1004 }
1005
1006 // Test Must alias for optimized uses
TEST_F(MemorySSATest,TestLoadMustAlias)1007 TEST_F(MemorySSATest, TestLoadMustAlias) {
1008 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
1009 GlobalValue::ExternalLinkage, "F", &M);
1010 B.SetInsertPoint(BasicBlock::Create(C, "", F));
1011 Type *Int8 = Type::getInt8Ty(C);
1012 Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
1013 Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
1014
1015 B.CreateStore(ConstantInt::get(Int8, 1), AllocaB);
1016 // Check load from LOE
1017 LoadInst *LA1 = B.CreateLoad(Int8, AllocaA, "");
1018 // Check load alias cached for second load
1019 LoadInst *LA2 = B.CreateLoad(Int8, AllocaA, "");
1020
1021 B.CreateStore(ConstantInt::get(Int8, 1), AllocaA);
1022 // Check load from store/def
1023 LoadInst *LA3 = B.CreateLoad(Int8, AllocaA, "");
1024 // Check load alias cached for second load
1025 LoadInst *LA4 = B.CreateLoad(Int8, AllocaA, "");
1026
1027 setupAnalyses();
1028 MemorySSA &MSSA = *Analyses->MSSA;
1029
1030 unsigned I = 0;
1031 for (LoadInst *V : {LA1, LA2}) {
1032 MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
1033 EXPECT_EQ(MemUse->getOptimizedAccessType(), None)
1034 << "Load " << I << " doesn't have the correct alias information";
1035 // EXPECT_EQ expands such that if we increment I above, it won't get
1036 // incremented except when we try to print the error message.
1037 ++I;
1038 }
1039 for (LoadInst *V : {LA3, LA4}) {
1040 MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
1041 EXPECT_EQ(MemUse->getOptimizedAccessType().getValue(),
1042 AliasResult::MustAlias)
1043 << "Load " << I << " doesn't have the correct alias information";
1044 // EXPECT_EQ expands such that if we increment I above, it won't get
1045 // incremented except when we try to print the error message.
1046 ++I;
1047 }
1048 }
1049
1050 // Test Must alias for optimized defs.
TEST_F(MemorySSATest,TestStoreMustAlias)1051 TEST_F(MemorySSATest, TestStoreMustAlias) {
1052 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
1053 GlobalValue::ExternalLinkage, "F", &M);
1054 B.SetInsertPoint(BasicBlock::Create(C, "", F));
1055 Type *Int8 = Type::getInt8Ty(C);
1056 Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
1057 Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
1058 StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaA);
1059 StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaB);
1060 StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaA);
1061 StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaB);
1062 StoreInst *SA3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaA);
1063 StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaB);
1064
1065 setupAnalyses();
1066 MemorySSA &MSSA = *Analyses->MSSA;
1067 MemorySSAWalker *Walker = Analyses->Walker;
1068
1069 unsigned I = 0;
1070 for (StoreInst *V : {SA1, SB1, SA2, SB2, SA3, SB3}) {
1071 MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
1072 EXPECT_EQ(MemDef->isOptimized(), false)
1073 << "Store " << I << " is optimized from the start?";
1074 EXPECT_EQ(MemDef->getOptimizedAccessType(), None)
1075 << "Store " << I
1076 << " has correct alias information before being optimized?";
1077 if (V == SA1)
1078 Walker->getClobberingMemoryAccess(V);
1079 else {
1080 MemoryAccess *Def = MemDef->getDefiningAccess();
1081 MemoryAccess *Clob = Walker->getClobberingMemoryAccess(V);
1082 EXPECT_NE(Def, Clob) << "Store " << I
1083 << " has Defining Access equal to Clobbering Access";
1084 }
1085 EXPECT_EQ(MemDef->isOptimized(), true)
1086 << "Store " << I << " was not optimized";
1087 if (I == 0 || I == 1)
1088 EXPECT_EQ(MemDef->getOptimizedAccessType(), None)
1089 << "Store " << I << " doesn't have the correct alias information";
1090 else
1091 EXPECT_EQ(MemDef->getOptimizedAccessType().getValue(),
1092 AliasResult::MustAlias)
1093 << "Store " << I << " doesn't have the correct alias information";
1094 // EXPECT_EQ expands such that if we increment I above, it won't get
1095 // incremented except when we try to print the error message.
1096 ++I;
1097 }
1098 }
1099
1100 // Test May alias for optimized uses.
TEST_F(MemorySSATest,TestLoadMayAlias)1101 TEST_F(MemorySSATest, TestLoadMayAlias) {
1102 F = Function::Create(FunctionType::get(B.getVoidTy(),
1103 {B.getInt8PtrTy(), B.getInt8PtrTy()},
1104 false),
1105 GlobalValue::ExternalLinkage, "F", &M);
1106 B.SetInsertPoint(BasicBlock::Create(C, "", F));
1107 Type *Int8 = Type::getInt8Ty(C);
1108 auto *ArgIt = F->arg_begin();
1109 Argument *PointerA = &*ArgIt;
1110 Argument *PointerB = &*(++ArgIt);
1111 B.CreateStore(ConstantInt::get(Int8, 1), PointerB);
1112 LoadInst *LA1 = B.CreateLoad(Int8, PointerA, "");
1113 B.CreateStore(ConstantInt::get(Int8, 0), PointerA);
1114 LoadInst *LB1 = B.CreateLoad(Int8, PointerB, "");
1115 B.CreateStore(ConstantInt::get(Int8, 0), PointerA);
1116 LoadInst *LA2 = B.CreateLoad(Int8, PointerA, "");
1117 B.CreateStore(ConstantInt::get(Int8, 0), PointerB);
1118 LoadInst *LB2 = B.CreateLoad(Int8, PointerB, "");
1119
1120 setupAnalyses();
1121 MemorySSA &MSSA = *Analyses->MSSA;
1122
1123 unsigned I = 0;
1124 for (LoadInst *V : {LA1, LB1}) {
1125 MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
1126 EXPECT_EQ(MemUse->getOptimizedAccessType().getValue(),
1127 AliasResult::MayAlias)
1128 << "Load " << I << " doesn't have the correct alias information";
1129 // EXPECT_EQ expands such that if we increment I above, it won't get
1130 // incremented except when we try to print the error message.
1131 ++I;
1132 }
1133 for (LoadInst *V : {LA2, LB2}) {
1134 MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
1135 EXPECT_EQ(MemUse->getOptimizedAccessType().getValue(),
1136 AliasResult::MustAlias)
1137 << "Load " << I << " doesn't have the correct alias information";
1138 // EXPECT_EQ expands such that if we increment I above, it won't get
1139 // incremented except when we try to print the error message.
1140 ++I;
1141 }
1142 }
1143
1144 // Test May alias for optimized defs.
TEST_F(MemorySSATest,TestStoreMayAlias)1145 TEST_F(MemorySSATest, TestStoreMayAlias) {
1146 F = Function::Create(FunctionType::get(B.getVoidTy(),
1147 {B.getInt8PtrTy(), B.getInt8PtrTy()},
1148 false),
1149 GlobalValue::ExternalLinkage, "F", &M);
1150 B.SetInsertPoint(BasicBlock::Create(C, "", F));
1151 Type *Int8 = Type::getInt8Ty(C);
1152 auto *ArgIt = F->arg_begin();
1153 Argument *PointerA = &*ArgIt;
1154 Argument *PointerB = &*(++ArgIt);
1155 Value *AllocaC = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");
1156 // Store into arg1, must alias because it's LOE => must
1157 StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 0), PointerA);
1158 // Store into arg2, may alias store to arg1 => may
1159 StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), PointerB);
1160 // Store into aloca, no alias with args, so must alias LOE => must
1161 StoreInst *SC1 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaC);
1162 // Store into arg1, may alias store to arg2 => may
1163 StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 3), PointerA);
1164 // Store into arg2, may alias store to arg1 => may
1165 StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 4), PointerB);
1166 // Store into aloca, no alias with args, so must alias SC1 => must
1167 StoreInst *SC2 = B.CreateStore(ConstantInt::get(Int8, 5), AllocaC);
1168 // Store into arg2, must alias store to arg2 => must
1169 StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 6), PointerB);
1170 std::initializer_list<StoreInst *> Sts = {SA1, SB1, SC1, SA2, SB2, SC2, SB3};
1171
1172 setupAnalyses();
1173 MemorySSA &MSSA = *Analyses->MSSA;
1174 MemorySSAWalker *Walker = Analyses->Walker;
1175
1176 unsigned I = 0;
1177 for (StoreInst *V : Sts) {
1178 MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
1179 EXPECT_EQ(MemDef->isOptimized(), false)
1180 << "Store " << I << " is optimized from the start?";
1181 EXPECT_EQ(MemDef->getOptimizedAccessType(), None)
1182 << "Store " << I
1183 << " has correct alias information before being optimized?";
1184 ++I;
1185 }
1186
1187 for (StoreInst *V : Sts)
1188 Walker->getClobberingMemoryAccess(V);
1189
1190 I = 0;
1191 for (StoreInst *V : Sts) {
1192 MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
1193 EXPECT_EQ(MemDef->isOptimized(), true)
1194 << "Store " << I << " was not optimized";
1195 if (I == 1 || I == 3 || I == 4)
1196 EXPECT_EQ(MemDef->getOptimizedAccessType().getValue(),
1197 AliasResult::MayAlias)
1198 << "Store " << I << " doesn't have the correct alias information";
1199 else if (I == 0 || I == 2)
1200 EXPECT_EQ(MemDef->getOptimizedAccessType(), None)
1201 << "Store " << I << " doesn't have the correct alias information";
1202 else
1203 EXPECT_EQ(MemDef->getOptimizedAccessType().getValue(),
1204 AliasResult::MustAlias)
1205 << "Store " << I << " doesn't have the correct alias information";
1206 // EXPECT_EQ expands such that if we increment I above, it won't get
1207 // incremented except when we try to print the error message.
1208 ++I;
1209 }
1210 }
1211
TEST_F(MemorySSATest,LifetimeMarkersAreClobbers)1212 TEST_F(MemorySSATest, LifetimeMarkersAreClobbers) {
1213 // Example code:
1214 // define void @a(i8* %foo) {
1215 // %bar = getelementptr i8, i8* %foo, i64 1
1216 // %baz = getelementptr i8, i8* %foo, i64 2
1217 // store i8 0, i8* %foo
1218 // store i8 0, i8* %bar
1219 // call void @llvm.lifetime.end.p0i8(i64 3, i8* %foo)
1220 // call void @llvm.lifetime.start.p0i8(i64 3, i8* %foo)
1221 // store i8 0, i8* %foo
1222 // store i8 0, i8* %bar
1223 // call void @llvm.memset.p0i8(i8* %baz, i8 0, i64 1)
1224 // ret void
1225 // }
1226 //
1227 // Patterns like this are possible after inlining; the stores to %foo and %bar
1228 // should both be clobbered by the lifetime.start call if they're dominated by
1229 // it.
1230
1231 IRBuilder<> B(C);
1232 F = Function::Create(
1233 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
1234 GlobalValue::ExternalLinkage, "F", &M);
1235
1236 // Make blocks
1237 BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
1238
1239 B.SetInsertPoint(Entry);
1240 Value *Foo = &*F->arg_begin();
1241
1242 Value *Bar = B.CreateGEP(B.getInt8Ty(), Foo, B.getInt64(1), "bar");
1243 Value *Baz = B.CreateGEP(B.getInt8Ty(), Foo, B.getInt64(2), "baz");
1244
1245 B.CreateStore(B.getInt8(0), Foo);
1246 B.CreateStore(B.getInt8(0), Bar);
1247
1248 auto GetLifetimeIntrinsic = [&](Intrinsic::ID ID) {
1249 return Intrinsic::getDeclaration(&M, ID, {Foo->getType()});
1250 };
1251
1252 B.CreateCall(GetLifetimeIntrinsic(Intrinsic::lifetime_end),
1253 {B.getInt64(3), Foo});
1254 Instruction *LifetimeStart = B.CreateCall(
1255 GetLifetimeIntrinsic(Intrinsic::lifetime_start), {B.getInt64(3), Foo});
1256
1257 Instruction *FooStore = B.CreateStore(B.getInt8(0), Foo);
1258 Instruction *BarStore = B.CreateStore(B.getInt8(0), Bar);
1259 Instruction *BazMemSet = B.CreateMemSet(Baz, B.getInt8(0), 1, Align(1));
1260
1261 setupAnalyses();
1262 MemorySSA &MSSA = *Analyses->MSSA;
1263
1264 MemoryAccess *LifetimeStartAccess = MSSA.getMemoryAccess(LifetimeStart);
1265 ASSERT_NE(LifetimeStartAccess, nullptr);
1266
1267 MemoryAccess *FooAccess = MSSA.getMemoryAccess(FooStore);
1268 ASSERT_NE(FooAccess, nullptr);
1269
1270 MemoryAccess *BarAccess = MSSA.getMemoryAccess(BarStore);
1271 ASSERT_NE(BarAccess, nullptr);
1272
1273 MemoryAccess *BazAccess = MSSA.getMemoryAccess(BazMemSet);
1274 ASSERT_NE(BazAccess, nullptr);
1275
1276 MemoryAccess *FooClobber =
1277 MSSA.getWalker()->getClobberingMemoryAccess(FooAccess);
1278 EXPECT_EQ(FooClobber, LifetimeStartAccess);
1279
1280 MemoryAccess *BarClobber =
1281 MSSA.getWalker()->getClobberingMemoryAccess(BarAccess);
1282 EXPECT_EQ(BarClobber, LifetimeStartAccess);
1283
1284 MemoryAccess *BazClobber =
1285 MSSA.getWalker()->getClobberingMemoryAccess(BazAccess);
1286 EXPECT_EQ(BazClobber, LifetimeStartAccess);
1287
1288 MemoryAccess *LifetimeStartClobber =
1289 MSSA.getWalker()->getClobberingMemoryAccess(
1290 LifetimeStartAccess, MemoryLocation::getAfter(Foo));
1291 EXPECT_EQ(LifetimeStartClobber, LifetimeStartAccess);
1292 }
1293
TEST_F(MemorySSATest,DefOptimizationsAreInvalidatedOnMoving)1294 TEST_F(MemorySSATest, DefOptimizationsAreInvalidatedOnMoving) {
1295 IRBuilder<> B(C);
1296 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getInt1Ty()}, false),
1297 GlobalValue::ExternalLinkage, "F", &M);
1298
1299 // Make a CFG like
1300 // entry
1301 // / \
1302 // a b
1303 // \ /
1304 // c
1305 //
1306 // Put a def in A and a def in B, move the def from A -> B, observe as the
1307 // optimization is invalidated.
1308 BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
1309 BasicBlock *BlockA = BasicBlock::Create(C, "a", F);
1310 BasicBlock *BlockB = BasicBlock::Create(C, "b", F);
1311 BasicBlock *BlockC = BasicBlock::Create(C, "c", F);
1312
1313 B.SetInsertPoint(Entry);
1314 Type *Int8 = Type::getInt8Ty(C);
1315 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "alloc");
1316 StoreInst *StoreEntry = B.CreateStore(B.getInt8(0), Alloca);
1317 B.CreateCondBr(B.getTrue(), BlockA, BlockB);
1318
1319 B.SetInsertPoint(BlockA);
1320 StoreInst *StoreA = B.CreateStore(B.getInt8(1), Alloca);
1321 B.CreateBr(BlockC);
1322
1323 B.SetInsertPoint(BlockB);
1324 StoreInst *StoreB = B.CreateStore(B.getInt8(2), Alloca);
1325 B.CreateBr(BlockC);
1326
1327 B.SetInsertPoint(BlockC);
1328 B.CreateUnreachable();
1329
1330 setupAnalyses();
1331 MemorySSA &MSSA = *Analyses->MSSA;
1332
1333 auto *AccessEntry = cast<MemoryDef>(MSSA.getMemoryAccess(StoreEntry));
1334 auto *StoreAEntry = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA));
1335 auto *StoreBEntry = cast<MemoryDef>(MSSA.getMemoryAccess(StoreB));
1336
1337 ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreAEntry),
1338 AccessEntry);
1339 ASSERT_TRUE(StoreAEntry->isOptimized());
1340
1341 ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreBEntry),
1342 AccessEntry);
1343 ASSERT_TRUE(StoreBEntry->isOptimized());
1344
1345 // Note that if we did InsertionPlace::Beginning, we don't go out of our way
1346 // to invalidate the cache for StoreBEntry. If the user wants to actually do
1347 // moves like these, it's up to them to ensure that nearby cache entries are
1348 // correctly invalidated (which, in general, requires walking all instructions
1349 // that the moved instruction dominates. So we probably shouldn't be doing
1350 // moves like this in general. Still, works as a test-case. ;) )
1351 MemorySSAUpdater(&MSSA).moveToPlace(StoreAEntry, BlockB,
1352 MemorySSA::InsertionPlace::End);
1353 ASSERT_FALSE(StoreAEntry->isOptimized());
1354 ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreAEntry),
1355 StoreBEntry);
1356 }
1357
TEST_F(MemorySSATest,TestOptimizedDefsAreProperUses)1358 TEST_F(MemorySSATest, TestOptimizedDefsAreProperUses) {
1359 F = Function::Create(FunctionType::get(B.getVoidTy(),
1360 {B.getInt8PtrTy(), B.getInt8PtrTy()},
1361 false),
1362 GlobalValue::ExternalLinkage, "F", &M);
1363 B.SetInsertPoint(BasicBlock::Create(C, "", F));
1364 Type *Int8 = Type::getInt8Ty(C);
1365 Value *AllocA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
1366 Value *AllocB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
1367
1368 StoreInst *StoreA = B.CreateStore(ConstantInt::get(Int8, 0), AllocA);
1369 StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 1), AllocB);
1370 StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocA);
1371
1372 setupAnalyses();
1373 MemorySSA &MSSA = *Analyses->MSSA;
1374 MemorySSAWalker *Walker = Analyses->Walker;
1375
1376 // If these don't hold, there's no chance of the test result being useful.
1377 ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreA),
1378 MSSA.getLiveOnEntryDef());
1379 ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreB),
1380 MSSA.getLiveOnEntryDef());
1381 auto *StoreAAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA));
1382 auto *StoreA2Access = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA2));
1383 ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreA2), StoreAAccess);
1384 ASSERT_EQ(StoreA2Access->getOptimized(), StoreAAccess);
1385
1386 auto *StoreBAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreB));
1387 ASSERT_LT(StoreAAccess->getID(), StoreBAccess->getID());
1388 ASSERT_LT(StoreBAccess->getID(), StoreA2Access->getID());
1389
1390 auto SortVecByID = [](std::vector<const MemoryDef *> &Defs) {
1391 llvm::sort(Defs, [](const MemoryDef *LHS, const MemoryDef *RHS) {
1392 return LHS->getID() < RHS->getID();
1393 });
1394 };
1395
1396 auto SortedUserList = [&](const MemoryDef *MD) {
1397 std::vector<const MemoryDef *> Result;
1398 transform(MD->users(), std::back_inserter(Result),
1399 [](const User *U) { return cast<MemoryDef>(U); });
1400 SortVecByID(Result);
1401 return Result;
1402 };
1403
1404 // Use std::vectors, since they have nice pretty-printing if the test fails.
1405 // Parens are necessary because EXPECT_EQ is a macro, and we have commas in
1406 // our init lists...
1407 EXPECT_EQ(SortedUserList(StoreAAccess),
1408 (std::vector<const MemoryDef *>{StoreBAccess, StoreA2Access}));
1409
1410 EXPECT_EQ(SortedUserList(StoreBAccess),
1411 std::vector<const MemoryDef *>{StoreA2Access});
1412
1413 // StoreAAccess should be present twice, since it uses liveOnEntry for both
1414 // its defining and optimized accesses. This is a bit awkward, and is not
1415 // relied upon anywhere at the moment. If this is painful, we can fix it.
1416 EXPECT_EQ(SortedUserList(cast<MemoryDef>(MSSA.getLiveOnEntryDef())),
1417 (std::vector<const MemoryDef *>{StoreAAccess, StoreAAccess,
1418 StoreBAccess}));
1419 }
1420
1421 // entry
1422 // |
1423 // header
1424 // / \
1425 // body |
1426 // \ /
1427 // exit
1428 // header:
1429 // ; 1 = MemoryDef(liveOnEntry)
1430 // body:
1431 // ; 2 = MemoryDef(1)
1432 // exit:
1433 // ; 3 = MemoryPhi({body, 2}, {header, 1})
1434 // ; 4 = MemoryDef(3); optimized to 3, cannot optimize thorugh phi.
1435 // Insert edge: entry -> exit, check mssa Update is correct.
TEST_F(MemorySSATest,TestAddedEdgeToBlockWithPhiNotOpt)1436 TEST_F(MemorySSATest, TestAddedEdgeToBlockWithPhiNotOpt) {
1437 F = Function::Create(
1438 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
1439 GlobalValue::ExternalLinkage, "F", &M);
1440 Argument *PointerArg = &*F->arg_begin();
1441 BasicBlock *Entry(BasicBlock::Create(C, "entry", F));
1442 BasicBlock *Header(BasicBlock::Create(C, "header", F));
1443 BasicBlock *Body(BasicBlock::Create(C, "body", F));
1444 BasicBlock *Exit(BasicBlock::Create(C, "exit", F));
1445 B.SetInsertPoint(Entry);
1446 BranchInst::Create(Header, Entry);
1447 B.SetInsertPoint(Header);
1448 B.CreateStore(B.getInt8(16), PointerArg);
1449 B.CreateCondBr(B.getTrue(), Exit, Body);
1450 B.SetInsertPoint(Body);
1451 B.CreateStore(B.getInt8(16), PointerArg);
1452 BranchInst::Create(Exit, Body);
1453 B.SetInsertPoint(Exit);
1454 StoreInst *S1 = B.CreateStore(B.getInt8(16), PointerArg);
1455
1456 setupAnalyses();
1457 MemorySSA &MSSA = *Analyses->MSSA;
1458 MemorySSAWalker *Walker = Analyses->Walker;
1459 std::unique_ptr<MemorySSAUpdater> MSSAU =
1460 std::make_unique<MemorySSAUpdater>(&MSSA);
1461
1462 MemoryPhi *Phi = MSSA.getMemoryAccess(Exit);
1463 EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S1));
1464
1465 // Alter CFG, add edge: entry -> exit
1466 Entry->getTerminator()->eraseFromParent();
1467 B.SetInsertPoint(Entry);
1468 B.CreateCondBr(B.getTrue(), Header, Exit);
1469 SmallVector<CFGUpdate, 1> Updates;
1470 Updates.push_back({cfg::UpdateKind::Insert, Entry, Exit});
1471 Analyses->DT.applyUpdates(Updates);
1472 MSSAU->applyInsertUpdates(Updates, Analyses->DT);
1473 EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S1));
1474 }
1475
1476 // entry
1477 // |
1478 // header
1479 // / \
1480 // body |
1481 // \ /
1482 // exit
1483 // header:
1484 // ; 1 = MemoryDef(liveOnEntry)
1485 // body:
1486 // ; 2 = MemoryDef(1)
1487 // exit:
1488 // ; 3 = MemoryPhi({body, 2}, {header, 1})
1489 // ; 4 = MemoryDef(3); optimize this to 1 now, added edge should invalidate
1490 // the optimized access.
1491 // Insert edge: entry -> exit, check mssa Update is correct.
TEST_F(MemorySSATest,TestAddedEdgeToBlockWithPhiOpt)1492 TEST_F(MemorySSATest, TestAddedEdgeToBlockWithPhiOpt) {
1493 F = Function::Create(
1494 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
1495 GlobalValue::ExternalLinkage, "F", &M);
1496 Argument *PointerArg = &*F->arg_begin();
1497 Type *Int8 = Type::getInt8Ty(C);
1498 BasicBlock *Entry(BasicBlock::Create(C, "entry", F));
1499 BasicBlock *Header(BasicBlock::Create(C, "header", F));
1500 BasicBlock *Body(BasicBlock::Create(C, "body", F));
1501 BasicBlock *Exit(BasicBlock::Create(C, "exit", F));
1502
1503 B.SetInsertPoint(Entry);
1504 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
1505 BranchInst::Create(Header, Entry);
1506
1507 B.SetInsertPoint(Header);
1508 StoreInst *S1 = B.CreateStore(B.getInt8(16), PointerArg);
1509 B.CreateCondBr(B.getTrue(), Exit, Body);
1510
1511 B.SetInsertPoint(Body);
1512 B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
1513 BranchInst::Create(Exit, Body);
1514
1515 B.SetInsertPoint(Exit);
1516 StoreInst *S2 = B.CreateStore(B.getInt8(16), PointerArg);
1517
1518 setupAnalyses();
1519 MemorySSA &MSSA = *Analyses->MSSA;
1520 MemorySSAWalker *Walker = Analyses->Walker;
1521 std::unique_ptr<MemorySSAUpdater> MSSAU =
1522 std::make_unique<MemorySSAUpdater>(&MSSA);
1523
1524 MemoryDef *DefS1 = cast<MemoryDef>(MSSA.getMemoryAccess(S1));
1525 EXPECT_EQ(DefS1, Walker->getClobberingMemoryAccess(S2));
1526
1527 // Alter CFG, add edge: entry -> exit
1528 Entry->getTerminator()->eraseFromParent();
1529 B.SetInsertPoint(Entry);
1530 B.CreateCondBr(B.getTrue(), Header, Exit);
1531 SmallVector<CFGUpdate, 1> Updates;
1532 Updates.push_back({cfg::UpdateKind::Insert, Entry, Exit});
1533 Analyses->DT.applyUpdates(Updates);
1534 MSSAU->applyInsertUpdates(Updates, Analyses->DT);
1535
1536 MemoryPhi *Phi = MSSA.getMemoryAccess(Exit);
1537 EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S2));
1538 }
1539
1540 // entry
1541 // / |
1542 // a |
1543 // / \ |
1544 // b c f
1545 // \ / |
1546 // d |
1547 // \ /
1548 // e
1549 // f:
1550 // ; 1 = MemoryDef(liveOnEntry)
1551 // e:
1552 // ; 2 = MemoryPhi({d, liveOnEntry}, {f, 1})
1553 //
1554 // Insert edge: f -> c, check update is correct.
1555 // After update:
1556 // f:
1557 // ; 1 = MemoryDef(liveOnEntry)
1558 // c:
1559 // ; 3 = MemoryPhi({a, liveOnEntry}, {f, 1})
1560 // d:
1561 // ; 4 = MemoryPhi({b, liveOnEntry}, {c, 3})
1562 // e:
1563 // ; 2 = MemoryPhi({d, 4}, {f, 1})
TEST_F(MemorySSATest,TestAddedEdgeToBlockWithNoPhiAddNewPhis)1564 TEST_F(MemorySSATest, TestAddedEdgeToBlockWithNoPhiAddNewPhis) {
1565 F = Function::Create(
1566 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
1567 GlobalValue::ExternalLinkage, "F", &M);
1568 Argument *PointerArg = &*F->arg_begin();
1569 BasicBlock *Entry(BasicBlock::Create(C, "entry", F));
1570 BasicBlock *ABlock(BasicBlock::Create(C, "a", F));
1571 BasicBlock *BBlock(BasicBlock::Create(C, "b", F));
1572 BasicBlock *CBlock(BasicBlock::Create(C, "c", F));
1573 BasicBlock *DBlock(BasicBlock::Create(C, "d", F));
1574 BasicBlock *EBlock(BasicBlock::Create(C, "e", F));
1575 BasicBlock *FBlock(BasicBlock::Create(C, "f", F));
1576
1577 B.SetInsertPoint(Entry);
1578 B.CreateCondBr(B.getTrue(), ABlock, FBlock);
1579 B.SetInsertPoint(ABlock);
1580 B.CreateCondBr(B.getTrue(), BBlock, CBlock);
1581 B.SetInsertPoint(BBlock);
1582 BranchInst::Create(DBlock, BBlock);
1583 B.SetInsertPoint(CBlock);
1584 BranchInst::Create(DBlock, CBlock);
1585 B.SetInsertPoint(DBlock);
1586 BranchInst::Create(EBlock, DBlock);
1587 B.SetInsertPoint(FBlock);
1588 B.CreateStore(B.getInt8(16), PointerArg);
1589 BranchInst::Create(EBlock, FBlock);
1590
1591 setupAnalyses();
1592 MemorySSA &MSSA = *Analyses->MSSA;
1593 std::unique_ptr<MemorySSAUpdater> MSSAU =
1594 std::make_unique<MemorySSAUpdater>(&MSSA);
1595
1596 // Alter CFG, add edge: f -> c
1597 FBlock->getTerminator()->eraseFromParent();
1598 B.SetInsertPoint(FBlock);
1599 B.CreateCondBr(B.getTrue(), CBlock, EBlock);
1600 SmallVector<CFGUpdate, 1> Updates;
1601 Updates.push_back({cfg::UpdateKind::Insert, FBlock, CBlock});
1602 Analyses->DT.applyUpdates(Updates);
1603 MSSAU->applyInsertUpdates(Updates, Analyses->DT);
1604
1605 MemoryPhi *MPC = MSSA.getMemoryAccess(CBlock);
1606 EXPECT_NE(MPC, nullptr);
1607 MemoryPhi *MPD = MSSA.getMemoryAccess(DBlock);
1608 EXPECT_NE(MPD, nullptr);
1609 MemoryPhi *MPE = MSSA.getMemoryAccess(EBlock);
1610 EXPECT_EQ(MPD, MPE->getIncomingValueForBlock(DBlock));
1611 }
1612
TEST_F(MemorySSATest,TestCallClobber)1613 TEST_F(MemorySSATest, TestCallClobber) {
1614 F = Function::Create(
1615 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
1616 GlobalValue::ExternalLinkage, "F", &M);
1617
1618 Value *Pointer1 = &*F->arg_begin();
1619 BasicBlock *Entry(BasicBlock::Create(C, "", F));
1620 B.SetInsertPoint(Entry);
1621 Value *Pointer2 = B.CreateGEP(B.getInt8Ty(), Pointer1, B.getInt64(1));
1622 Instruction *StorePointer1 = B.CreateStore(B.getInt8(0), Pointer1);
1623 Instruction *StorePointer2 = B.CreateStore(B.getInt8(0), Pointer2);
1624 Instruction *MemSet = B.CreateMemSet(Pointer2, B.getInt8(0), 1, Align(1));
1625
1626 setupAnalyses();
1627 MemorySSA &MSSA = *Analyses->MSSA;
1628 MemorySSAWalker *Walker = Analyses->Walker;
1629
1630 MemoryUseOrDef *Store1Access = MSSA.getMemoryAccess(StorePointer1);
1631 MemoryUseOrDef *Store2Access = MSSA.getMemoryAccess(StorePointer2);
1632 MemoryUseOrDef *MemSetAccess = MSSA.getMemoryAccess(MemSet);
1633
1634 MemoryAccess *Pointer1Clobber = Walker->getClobberingMemoryAccess(
1635 MemSetAccess, MemoryLocation(Pointer1, LocationSize::precise(1)));
1636 EXPECT_EQ(Pointer1Clobber, Store1Access);
1637
1638 MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(
1639 MemSetAccess, MemoryLocation(Pointer2, LocationSize::precise(1)));
1640 EXPECT_EQ(Pointer2Clobber, MemSetAccess);
1641
1642 MemoryAccess *MemSetClobber = Walker->getClobberingMemoryAccess(MemSetAccess);
1643 EXPECT_EQ(MemSetClobber, Store2Access);
1644 }
1645
TEST_F(MemorySSATest,TestLoadClobber)1646 TEST_F(MemorySSATest, TestLoadClobber) {
1647 F = Function::Create(
1648 FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
1649 GlobalValue::ExternalLinkage, "F", &M);
1650
1651 Value *Pointer1 = &*F->arg_begin();
1652 BasicBlock *Entry(BasicBlock::Create(C, "", F));
1653 B.SetInsertPoint(Entry);
1654 Value *Pointer2 = B.CreateGEP(B.getInt8Ty(), Pointer1, B.getInt64(1));
1655 Instruction *LoadPointer1 =
1656 B.CreateLoad(B.getInt8Ty(), Pointer1, /* Volatile */ true);
1657 Instruction *LoadPointer2 =
1658 B.CreateLoad(B.getInt8Ty(), Pointer2, /* Volatile */ true);
1659
1660 setupAnalyses();
1661 MemorySSA &MSSA = *Analyses->MSSA;
1662 MemorySSAWalker *Walker = Analyses->Walker;
1663
1664 MemoryUseOrDef *Load1Access = MSSA.getMemoryAccess(LoadPointer1);
1665 MemoryUseOrDef *Load2Access = MSSA.getMemoryAccess(LoadPointer2);
1666
1667 // When providing a memory location, we should never return a load as the
1668 // clobber.
1669 MemoryAccess *Pointer1Clobber = Walker->getClobberingMemoryAccess(
1670 Load2Access, MemoryLocation(Pointer1, LocationSize::precise(1)));
1671 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer1Clobber));
1672
1673 MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(
1674 Load2Access, MemoryLocation(Pointer2, LocationSize::precise(1)));
1675 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer2Clobber));
1676
1677 MemoryAccess *Load2Clobber = Walker->getClobberingMemoryAccess(Load2Access);
1678 EXPECT_EQ(Load2Clobber, Load1Access);
1679 }
1680
1681 // We want to test if the location information are retained
1682 // when the IsGuaranteedLoopInvariant function handles a
1683 // memory access referring to a pointer defined in the entry
1684 // block, hence automatically guaranteed to be loop invariant.
TEST_F(MemorySSATest,TestLoopInvariantEntryBlockPointer)1685 TEST_F(MemorySSATest, TestLoopInvariantEntryBlockPointer) {
1686 SMDiagnostic E;
1687 auto LocalM =
1688 parseAssemblyString("define void @test(i64 %a0, i8* %a1, i1* %a2) {\n"
1689 "entry:\n"
1690 "%v0 = getelementptr i8, i8* %a1, i64 %a0\n"
1691 "%v1 = bitcast i8* %v0 to i64*\n"
1692 "%v2 = bitcast i8* %v0 to i32*\n"
1693 "%v3 = load i1, i1* %a2\n"
1694 "br i1 %v3, label %body, label %exit\n"
1695 "body:\n"
1696 "store i32 1, i32* %v2\n"
1697 "br label %exit\n"
1698 "exit:\n"
1699 "store i64 0, i64* %v1\n"
1700 "ret void\n"
1701 "}",
1702 E, C);
1703 ASSERT_TRUE(LocalM);
1704 F = LocalM->getFunction("test");
1705 ASSERT_TRUE(F);
1706 // Setup the analysis
1707 setupAnalyses();
1708 MemorySSA &MSSA = *Analyses->MSSA;
1709 // Find the exit block
1710 for (auto &BB : *F) {
1711 if (BB.getName() == "exit") {
1712 // Get the store instruction
1713 auto *SI = BB.getFirstNonPHI();
1714 // Get the memory access and location
1715 MemoryAccess *MA = MSSA.getMemoryAccess(SI);
1716 MemoryLocation ML = MemoryLocation::get(SI);
1717 // Use the 'upward_defs_iterator' which internally calls
1718 // IsGuaranteedLoopInvariant
1719 auto ItA = upward_defs_begin({MA, ML}, MSSA.getDomTree());
1720 auto ItB =
1721 upward_defs_begin({ItA->first, ItA->second}, MSSA.getDomTree());
1722 // Check if the location information have been retained
1723 EXPECT_TRUE(ItB->second.Size.isPrecise());
1724 EXPECT_TRUE(ItB->second.Size.hasValue());
1725 EXPECT_TRUE(ItB->second.Size.getValue() == 8);
1726 }
1727 }
1728 }