From be1b992213d91a58147265d3e63a6b14fdfcbae3 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Mon, 30 Jan 2017 11:35:39 +0000 Subject: [PATCH] Revert "[MemorySSA] Revert r293361 and r293363, as the tests fail under asan." This reverts commit r293471, reapplying r293361 and r293363 with a fix for an out-of-bounds read. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@293474 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/MemorySSA.h | 1 + include/llvm/Transforms/Utils/MemorySSAUpdater.h | 12 ++--- lib/Transforms/Utils/MemorySSA.cpp | 15 ++++--- lib/Transforms/Utils/MemorySSAUpdater.cpp | 34 +++++++++----- unittests/Transforms/Utils/MemorySSA.cpp | 56 ++++++++++++++++++++++++ 5 files changed, 98 insertions(+), 20 deletions(-) diff --git a/include/llvm/Transforms/Utils/MemorySSA.h b/include/llvm/Transforms/Utils/MemorySSA.h index 96006fd4b52..bad2a3b708c 100644 --- a/include/llvm/Transforms/Utils/MemorySSA.h +++ b/include/llvm/Transforms/Utils/MemorySSA.h @@ -689,6 +689,7 @@ protected: // for moves. It does not always leave the IR in a correct state, and relies // on the updater to fixup what it breaks, so it is not public. void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where); + void moveTo(MemoryUseOrDef *What, BasicBlock *BB, InsertionPlace Point); private: class CachingWalker; diff --git a/include/llvm/Transforms/Utils/MemorySSAUpdater.h b/include/llvm/Transforms/Utils/MemorySSAUpdater.h index 8fac9cf3f80..3fb759a891a 100644 --- a/include/llvm/Transforms/Utils/MemorySSAUpdater.h +++ b/include/llvm/Transforms/Utils/MemorySSAUpdater.h @@ -24,10 +24,9 @@ // That's it. // // For moving, first, move the instruction itself using the normal SSA -// instruction moving API, then just call moveBefore or moveAfter with the right -// arguments. +// instruction moving API, then just call moveBefore, moveAfter,or moveTo with +// the right arguments. // -// walk memory instructions using a use/def graph. //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H @@ -68,10 +67,13 @@ public: void insertUse(MemoryUse *Use); void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); - + void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, + MemorySSA::InsertionPlace Where); private: + // Move What before Where in the MemorySSA IR. + template void moveTo(MemoryUseOrDef *What, BasicBlock *BB, - MemorySSA::AccessList::iterator Where); + WhereType Where); MemoryAccess *getPreviousDef(MemoryAccess *); MemoryAccess *getPreviousDefInBlock(MemoryAccess *); MemoryAccess *getPreviousDefFromEnd(BasicBlock *); diff --git a/lib/Transforms/Utils/MemorySSA.cpp b/lib/Transforms/Utils/MemorySSA.cpp index 50006cef477..af4dc028b85 100644 --- a/lib/Transforms/Utils/MemorySSA.cpp +++ b/lib/Transforms/Utils/MemorySSA.cpp @@ -1597,6 +1597,7 @@ void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess, Defs->push_back(*NewAccess); } } + BlockNumberingValid.erase(BB); } void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB, @@ -1624,6 +1625,7 @@ void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB, Defs->insert(InsertPt->getDefsIterator(), *What); } } + BlockNumberingValid.erase(BB); } // Move What before Where in the IR. The end result is taht What will belong to @@ -1638,13 +1640,19 @@ void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, insertIntoListsBefore(What, BB, Where); } +void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, + InsertionPlace Point) { + removeFromLists(What, false); + What->setBlock(BB); + insertIntoListsForBlock(What, BB, Point); +} + MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) { assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB"); MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++); + // Phi's always are placed at the front of the block. insertIntoListsForBlock(Phi, BB, Beginning); ValueToMemoryAccess[BB] = Phi; - // Phi's always are placed at the front of the block. - BlockNumberingValid.erase(BB); return Phi; } @@ -1665,7 +1673,6 @@ MemoryAccess *MemorySSA::createMemoryAccessInBB(Instruction *I, InsertionPlace Point) { MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); insertIntoListsForBlock(NewAccess, BB, Point); - BlockNumberingValid.erase(BB); return NewAccess; } @@ -1675,7 +1682,6 @@ MemoryUseOrDef *MemorySSA::createMemoryAccessBefore(Instruction *I, assert(I->getParent() == InsertPt->getBlock() && "New and old access must be in the same block"); MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - BlockNumberingValid.erase(InsertPt->getBlock()); insertIntoListsBefore(NewAccess, InsertPt->getBlock(), InsertPt->getIterator()); return NewAccess; @@ -1687,7 +1693,6 @@ MemoryUseOrDef *MemorySSA::createMemoryAccessAfter(Instruction *I, assert(I->getParent() == InsertPt->getBlock() && "New and old access must be in the same block"); MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - BlockNumberingValid.erase(InsertPt->getBlock()); insertIntoListsBefore(NewAccess, InsertPt->getBlock(), ++(InsertPt->getIterator())); return NewAccess; diff --git a/lib/Transforms/Utils/MemorySSAUpdater.cpp b/lib/Transforms/Utils/MemorySSAUpdater.cpp index 792ddef4e70..21f286b8cde 100644 --- a/lib/Transforms/Utils/MemorySSAUpdater.cpp +++ b/lib/Transforms/Utils/MemorySSAUpdater.cpp @@ -210,15 +210,19 @@ void MemorySSAUpdater::insertUse(MemoryUse *MU) { // to do. } +// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef. void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB, MemoryAccess *NewDef) { // Replace any operand with us an incoming block with the new defining // access. int i = MP->getBasicBlockIndex(BB); assert(i != -1 && "Should have found the basic block in the phi"); - while (MP->getIncomingBlock(i) == BB) { - // Unlike above, there is already a phi node here, so we only need - // to set the right value. + // We can't just compare i against getNumOperands since one is signed and the + // other not. So use it to index into the block iterator. + for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end(); + ++BBIter) { + if (*BBIter != BB) + break; MP->setIncomingValue(i, NewDef); ++i; } @@ -243,13 +247,17 @@ void MemorySSAUpdater::insertDef(MemoryDef *MD) { // of that thing with us, since we are in the way of whatever was there // before. // We now define that def's memorydefs and memoryphis - for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end(); UI != UE;) { - Use &U = *UI++; - // Leave the uses alone - if (isa(U.getUser())) - continue; - U.set(MD); + if (DefBeforeSameBlock) { + for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end(); + UI != UE;) { + Use &U = *UI++; + // Leave the uses alone + if (isa(U.getUser())) + continue; + U.set(MD); + } } + // and that def is now our defining access. // We change them in this order otherwise we will appear in the use list // above and reset ourselves. @@ -345,8 +353,9 @@ void MemorySSAUpdater::fixupDefs(const SmallVectorImpl &Vars) { } // Move What before Where in the MemorySSA IR. +template void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, - MemorySSA::AccessList::iterator Where) { + WhereType Where) { // Replace all our users with our defining access. What->replaceAllUsesWith(What->getDefiningAccess()); @@ -359,6 +368,7 @@ void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, else insertUse(cast(What)); } + // Move What before Where in the MemorySSA IR. void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) { moveTo(What, Where->getBlock(), Where->getIterator()); @@ -369,4 +379,8 @@ void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) { moveTo(What, Where->getBlock(), ++Where->getIterator()); } +void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, + MemorySSA::InsertionPlace Where) { + return moveTo(What, BB, Where); +} } // namespace llvm diff --git a/unittests/Transforms/Utils/MemorySSA.cpp b/unittests/Transforms/Utils/MemorySSA.cpp index 95ec3ed55e6..0df476bc28c 100644 --- a/unittests/Transforms/Utils/MemorySSA.cpp +++ b/unittests/Transforms/Utils/MemorySSA.cpp @@ -365,6 +365,62 @@ TEST_F(MemorySSATest, MoveAStoreUpdaterMove) { MSSA.verifyMemorySSA(); } +TEST_F(MemorySSATest, MoveAStoreAllAround) { + // We create a diamond where there is a in the entry, a store on one side, and + // a load at the end. After building MemorySSA, we test updating by moving + // the store from the side block to the entry block, then to the other side + // block, then to before the load. This does not destroy the old access. + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), + GlobalValue::ExternalLinkage, "F", &M); + BasicBlock *Entry(BasicBlock::Create(C, "", F)); + BasicBlock *Left(BasicBlock::Create(C, "", F)); + BasicBlock *Right(BasicBlock::Create(C, "", F)); + BasicBlock *Merge(BasicBlock::Create(C, "", F)); + B.SetInsertPoint(Entry); + Argument *PointerArg = &*F->arg_begin(); + StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); + B.CreateCondBr(B.getTrue(), Left, Right); + B.SetInsertPoint(Left); + auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg); + BranchInst::Create(Merge, Left); + BranchInst::Create(Merge, Right); + B.SetInsertPoint(Merge); + auto *MergeLoad = B.CreateLoad(PointerArg); + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); + + // Move the store + auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); + auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore); + // Before, the load will point to a phi of the EntryStore and SideStore. + auto *LoadAccess = cast(MSSA.getMemoryAccess(MergeLoad)); + EXPECT_TRUE(isa(LoadAccess->getDefiningAccess())); + MemoryPhi *MergePhi = cast(LoadAccess->getDefiningAccess()); + EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); + // Move the store before the entry store + SideStore->moveBefore(*EntryStore->getParent(), EntryStore->getIterator()); + Updater.moveBefore(SideStoreAccess, EntryStoreAccess); + // After, it's a phi of the entry store. + EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); + MSSA.verifyMemorySSA(); + // Now move the store to the right branch + SideStore->moveBefore(*Right, Right->begin()); + Updater.moveToPlace(SideStoreAccess, Right, MemorySSA::Beginning); + MSSA.verifyMemorySSA(); + EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess); + // Now move it before the load + SideStore->moveBefore(MergeLoad); + Updater.moveBefore(SideStoreAccess, LoadAccess); + EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); + MSSA.verifyMemorySSA(); +} + TEST_F(MemorySSATest, RemoveAPhi) { // We create a diamond where there is a store on one side, and then a load // after the merge point. This enables us to test a bunch of different -- 2.11.0