From 92cf58ee368511a9ef8a97cd7ff2702effcc745c Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Sat, 28 Jan 2017 01:35:02 +0000 Subject: [PATCH] MemorySSA: Move updater to its own file git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@293357 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/MemorySSA.h | 45 --- .../llvm/Transforms/Utils/MemorySSAUpdater.h | 86 ++++ lib/Transforms/Utils/CMakeLists.txt | 1 + lib/Transforms/Utils/MemorySSA.cpp | 339 ---------------- lib/Transforms/Utils/MemorySSAUpdater.cpp | 372 ++++++++++++++++++ unittests/Transforms/Utils/MemorySSA.cpp | 1 + 6 files changed, 460 insertions(+), 384 deletions(-) create mode 100644 include/llvm/Transforms/Utils/MemorySSAUpdater.h create mode 100644 lib/Transforms/Utils/MemorySSAUpdater.cpp diff --git a/include/llvm/Transforms/Utils/MemorySSA.h b/include/llvm/Transforms/Utils/MemorySSA.h index 80822712a0d..96006fd4b52 100644 --- a/include/llvm/Transforms/Utils/MemorySSA.h +++ b/include/llvm/Transforms/Utils/MemorySSA.h @@ -752,51 +752,6 @@ private: unsigned NextID; }; -// An automatic updater for MemorySSA that handles arbitrary insertion, -// deletion, and moves. It performs phi insertion where necessary, and -// automatically updates the MemorySSA IR to be correct. -// While updating loads or removing instructions is often easy enough to not -// need this, updating stores should generally not be attemped outside this -// API. -// -// Basic API usage: -// Create the memory access you want for the instruction (this is mainly so -// we know where it is, without having to duplicate the entire set of create -// functions MemorySSA supports). -// Call insertDef or insertUse depending on whether it's a MemoryUse or a -// MemoryDef. -// 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. -// -class MemorySSAUpdater { -private: - MemorySSA *MSSA; - SmallVector InsertedPHIs; - SmallPtrSet VisitedBlocks; - -public: - MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} - void insertDef(MemoryDef *Def); - void insertUse(MemoryUse *Use); - void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); - void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); - -private: - void moveTo(MemoryUseOrDef *What, BasicBlock *BB, - MemorySSA::AccessList::iterator Where); - MemoryAccess *getPreviousDef(MemoryAccess *); - MemoryAccess *getPreviousDefInBlock(MemoryAccess *); - MemoryAccess *getPreviousDefFromEnd(BasicBlock *); - MemoryAccess *getPreviousDefRecursive(BasicBlock *); - MemoryAccess *recursePhi(MemoryAccess *Phi); - template - MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); - void fixupDefs(const SmallVectorImpl &); -}; - // This pass does eager building and then printing of MemorySSA. It is used by // the tests to be able to build, dump, and verify Memory SSA. class MemorySSAPrinterLegacyPass : public FunctionPass { diff --git a/include/llvm/Transforms/Utils/MemorySSAUpdater.h b/include/llvm/Transforms/Utils/MemorySSAUpdater.h new file mode 100644 index 00000000000..8fac9cf3f80 --- /dev/null +++ b/include/llvm/Transforms/Utils/MemorySSAUpdater.h @@ -0,0 +1,86 @@ +//===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// \file +// \brief An automatic updater for MemorySSA that handles arbitrary insertion, +// deletion, and moves. It performs phi insertion where necessary, and +// automatically updates the MemorySSA IR to be correct. +// While updating loads or removing instructions is often easy enough to not +// need this, updating stores should generally not be attemped outside this +// API. +// +// Basic API usage: +// Create the memory access you want for the instruction (this is mainly so +// we know where it is, without having to duplicate the entire set of create +// functions MemorySSA supports). +// Call insertDef or insertUse depending on whether it's a MemoryUse or a +// MemoryDef. +// 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. +// +// walk memory instructions using a use/def graph. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H +#define LLVM_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H + +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/OperandTraits.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Transforms/Utils/MemorySSA.h" + +namespace llvm { + +class Function; +class Instruction; +class MemoryAccess; +class LLVMContext; +class raw_ostream; + +class MemorySSAUpdater { +private: + MemorySSA *MSSA; + SmallVector InsertedPHIs; + SmallPtrSet VisitedBlocks; + +public: + MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} + void insertDef(MemoryDef *Def); + void insertUse(MemoryUse *Use); + void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); + void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); + +private: + void moveTo(MemoryUseOrDef *What, BasicBlock *BB, + MemorySSA::AccessList::iterator Where); + MemoryAccess *getPreviousDef(MemoryAccess *); + MemoryAccess *getPreviousDefInBlock(MemoryAccess *); + MemoryAccess *getPreviousDefFromEnd(BasicBlock *); + MemoryAccess *getPreviousDefRecursive(BasicBlock *); + MemoryAccess *recursePhi(MemoryAccess *Phi); + template + MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); + void fixupDefs(const SmallVectorImpl &); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt index 69889ec72f9..f8a1b4d2f49 100644 --- a/lib/Transforms/Utils/CMakeLists.txt +++ b/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_library(LLVMTransformUtils LowerSwitch.cpp Mem2Reg.cpp MemorySSA.cpp + MemorySSAUpdater.cpp MetaRenamer.cpp ModuleUtils.cpp NameAnonGlobals.cpp diff --git a/lib/Transforms/Utils/MemorySSA.cpp b/lib/Transforms/Utils/MemorySSA.cpp index f80f34ef294..e93bc0ecc5b 100644 --- a/lib/Transforms/Utils/MemorySSA.cpp +++ b/lib/Transforms/Utils/MemorySSA.cpp @@ -2397,343 +2397,4 @@ MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess( return Use->getDefiningAccess(); return StartingAccess; } -// This is the marker algorithm from "Simple and Efficient Construction of -// Static Single Assignment Form" -// The simple, non-marker algorithm places phi nodes at any join -// Here, we place markers, and only place phi nodes if they end up necessary. -// They are only necessary if they break a cycle (IE we recursively visit -// ourselves again), or we discover, while getting the value of the operands, -// that there are two or more definitions needing to be merged. -// This still will leave non-minimal form in the case of irreducible control -// flow, where phi nodes may be in cycles with themselves, but unnecessary. -MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) { - // Single predecessor case, just recurse, we can only have one definition. - if (BasicBlock *Pred = BB->getSinglePredecessor()) { - return getPreviousDefFromEnd(Pred); - } else if (VisitedBlocks.count(BB)) { - // We hit our node again, meaning we had a cycle, we must insert a phi - // node to break it so we have an operand. The only case this will - // insert useless phis is if we have irreducible control flow. - return MSSA->createMemoryPhi(BB); - } else if (VisitedBlocks.insert(BB).second) { - // Mark us visited so we can detect a cycle - SmallVector PhiOps; - - // Recurse to get the values in our predecessors for placement of a - // potential phi node. This will insert phi nodes if we cycle in order to - // break the cycle and have an operand. - for (auto *Pred : predecessors(BB)) - PhiOps.push_back(getPreviousDefFromEnd(Pred)); - - // Now try to simplify the ops to avoid placing a phi. - // This may return null if we never created a phi yet, that's okay - MemoryPhi *Phi = dyn_cast_or_null(MSSA->getMemoryAccess(BB)); - bool PHIExistsButNeedsUpdate = false; - // See if the existing phi operands match what we need. - // Unlike normal SSA, we only allow one phi node per block, so we can't just - // create a new one. - if (Phi && Phi->getNumOperands() != 0) - if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) { - PHIExistsButNeedsUpdate = true; - } - - // See if we can avoid the phi by simplifying it. - auto *Result = tryRemoveTrivialPhi(Phi, PhiOps); - // If we couldn't simplify, we may have to create a phi - if (Result == Phi) { - if (!Phi) - Phi = MSSA->createMemoryPhi(BB); - - // These will have been filled in by the recursive read we did above. - if (PHIExistsButNeedsUpdate) { - std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin()); - std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin()); - } else { - unsigned i = 0; - for (auto *Pred : predecessors(BB)) - Phi->addIncoming(PhiOps[i++], Pred); - } - - Result = Phi; - } - if (MemoryPhi *MP = dyn_cast(Result)) - InsertedPHIs.push_back(MP); - // Set ourselves up for the next variable by resetting visited state. - VisitedBlocks.erase(BB); - return Result; - } - llvm_unreachable("Should have hit one of the three cases above"); -} - -// This starts at the memory access, and goes backwards in the block to find the -// previous definition. If a definition is not found the block of the access, -// it continues globally, creating phi nodes to ensure we have a single -// definition. -MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) { - auto *LocalResult = getPreviousDefInBlock(MA); - - return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock()); -} - -// This starts at the memory access, and goes backwards in the block to the find -// the previous definition. If the definition is not found in the block of the -// access, it returns nullptr. -MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) { - auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock()); - - // It's possible there are no defs, or we got handed the first def to start. - if (Defs) { - // If this is a def, we can just use the def iterators. - if (!isa(MA)) { - auto Iter = MA->getReverseDefsIterator(); - ++Iter; - if (Iter != Defs->rend()) - return &*Iter; - } else { - // Otherwise, have to walk the all access iterator. - auto Iter = MA->getReverseIterator(); - ++Iter; - while (&*Iter != &*Defs->begin()) { - if (!isa(*Iter)) - return &*Iter; - --Iter; - } - // At this point it must be pointing at firstdef - assert(&*Iter == &*Defs->begin() && - "Should have hit first def walking backwards"); - return &*Iter; - } - } - return nullptr; -} - -// This starts at the end of block -MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) { - auto *Defs = MSSA->getWritableBlockDefs(BB); - - if (Defs) - return &*Defs->rbegin(); - - return getPreviousDefRecursive(BB); -} -// Recurse over a set of phi uses to eliminate the trivial ones -MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) { - if (!Phi) - return nullptr; - TrackingVH Res(Phi); - SmallVector, 8> Uses; - std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses)); - for (auto &U : Uses) { - if (MemoryPhi *UsePhi = dyn_cast(&*U)) { - auto OperRange = UsePhi->operands(); - tryRemoveTrivialPhi(UsePhi, OperRange); - } - } - return Res; -} - -// Eliminate trivial phis -// Phis are trivial if they are defined either by themselves, or all the same -// argument. -// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c) -// We recursively try to remove them. -template -MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi, - RangeType &Operands) { - // Detect equal or self arguments - MemoryAccess *Same = nullptr; - for (auto &Op : Operands) { - // If the same or self, good so far - if (Op == Phi || Op == Same) - continue; - // not the same, return the phi since it's not eliminatable by us - if (Same) - return Phi; - Same = cast(Op); - } - // Never found a non-self reference, the phi is undef - if (Same == nullptr) - return MSSA->getLiveOnEntryDef(); - if (Phi) { - Phi->replaceAllUsesWith(Same); - MSSA->removeMemoryAccess(Phi); - } - - // We should only end up recursing in case we replaced something, in which - // case, we may have made other Phis trivial. - return recursePhi(Same); -} - -void MemorySSAUpdater::insertUse(MemoryUse *MU) { - InsertedPHIs.clear(); - MU->setDefiningAccess(getPreviousDef(MU)); - // Unlike for defs, there is no extra work to do. Because uses do not create - // new may-defs, there are only two cases: - // - // 1. There was a def already below us, and therefore, we should not have - // created a phi node because it was already needed for the def. - // - // 2. There is no def below us, and therefore, there is no extra renaming work - // to do. -} - -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. - MP->setIncomingValue(i, NewDef); - ++i; - } -} - -// A brief description of the algorithm: -// First, we compute what should define the new def, using the SSA -// construction algorithm. -// Then, we update the defs below us (and any new phi nodes) in the graph to -// point to the correct new defs, to ensure we only have one variable, and no -// disconnected stores. -void MemorySSAUpdater::insertDef(MemoryDef *MD) { - InsertedPHIs.clear(); - - // See if we had a local def, and if not, go hunting. - MemoryAccess *DefBefore = getPreviousDefInBlock(MD); - bool DefBeforeSameBlock = DefBefore != nullptr; - if (!DefBefore) - DefBefore = getPreviousDefRecursive(MD->getBlock()); - - // There is a def before us, which means we can replace any store/phi uses - // 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); - } - // 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. - MD->setDefiningAccess(DefBefore); - - SmallVector FixupList(InsertedPHIs.begin(), - InsertedPHIs.end()); - if (!DefBeforeSameBlock) { - // If there was a local def before us, we must have the same effect it - // did. Because every may-def is the same, any phis/etc we would create, it - // would also have created. If there was no local def before us, we - // performed a global update, and have to search all successors and make - // sure we update the first def in each of them (following all paths until - // we hit the first def along each path). This may also insert phi nodes. - // TODO: There are other cases we can skip this work, such as when we have a - // single successor, and only used a straight line of single pred blocks - // backwards to find the def. To make that work, we'd have to track whether - // getDefRecursive only ever used the single predecessor case. These types - // of paths also only exist in between CFG simplifications. - FixupList.push_back(MD); - } - - while (!FixupList.empty()) { - unsigned StartingPHISize = InsertedPHIs.size(); - fixupDefs(FixupList); - FixupList.clear(); - // Put any new phis on the fixup list, and process them - FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end()); - } -} - -void MemorySSAUpdater::fixupDefs(const SmallVectorImpl &Vars) { - SmallPtrSet Seen; - SmallVector Worklist; - for (auto *NewDef : Vars) { - // First, see if there is a local def after the operand. - auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock()); - auto DefIter = NewDef->getDefsIterator(); - - // If there is a local def after us, we only have to rename that. - if (++DefIter != Defs->end()) { - cast(DefIter)->setDefiningAccess(NewDef); - continue; - } - - // Otherwise, we need to search down through the CFG. - // For each of our successors, handle it directly if their is a phi, or - // place on the fixup worklist. - for (const auto *S : successors(NewDef->getBlock())) { - if (auto *MP = MSSA->getMemoryAccess(S)) - setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef); - else - Worklist.push_back(S); - } - - while (!Worklist.empty()) { - const BasicBlock *FixupBlock = Worklist.back(); - Worklist.pop_back(); - - // Get the first def in the block that isn't a phi node. - if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) { - auto *FirstDef = &*Defs->begin(); - // The loop above and below should have taken care of phi nodes - assert(!isa(FirstDef) && - "Should have already handled phi nodes!"); - // We are now this def's defining access, make sure we actually dominate - // it - assert(MSSA->dominates(NewDef, FirstDef) && - "Should have dominated the new access"); - - // This may insert new phi nodes, because we are not guaranteed the - // block we are processing has a single pred, and depending where the - // store was inserted, it may require phi nodes below it. - cast(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef)); - return; - } - // We didn't find a def, so we must continue. - for (const auto *S : successors(FixupBlock)) { - // If there is a phi node, handle it. - // Otherwise, put the block on the worklist - if (auto *MP = MSSA->getMemoryAccess(S)) - setMemoryPhiValueForBlock(MP, FixupBlock, NewDef); - else { - // If we cycle, we should have ended up at a phi node that we already - // processed. FIXME: Double check this - if (!Seen.insert(S).second) - continue; - Worklist.push_back(S); - } - } - } - } -} - -// Move What before Where in the MemorySSA IR. -void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, - MemorySSA::AccessList::iterator Where) { - // Replace all our users with our defining access. - What->replaceAllUsesWith(What->getDefiningAccess()); - - // Let MemorySSA take care of moving it around in the lists. - MSSA->moveTo(What, BB, Where); - - // Now reinsert it into the IR and do whatever fixups needed. - if (auto *MD = dyn_cast(What)) - insertDef(MD); - 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()); -} - -// Move What after Where in the MemorySSA IR. -void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) { - moveTo(What, Where->getBlock(), ++Where->getIterator()); -} - } // namespace llvm diff --git a/lib/Transforms/Utils/MemorySSAUpdater.cpp b/lib/Transforms/Utils/MemorySSAUpdater.cpp new file mode 100644 index 00000000000..792ddef4e70 --- /dev/null +++ b/lib/Transforms/Utils/MemorySSAUpdater.cpp @@ -0,0 +1,372 @@ +//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------===// +// +// This file implements the MemorySSAUpdater class. +// +//===----------------------------------------------------------------===// +#include "llvm/Transforms/Utils/MemorySSAUpdater.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FormattedStream.h" +#include "llvm/Transforms/Utils/MemorySSA.h" +#include + +#define DEBUG_TYPE "memoryssa" +using namespace llvm; +namespace llvm { +// This is the marker algorithm from "Simple and Efficient Construction of +// Static Single Assignment Form" +// The simple, non-marker algorithm places phi nodes at any join +// Here, we place markers, and only place phi nodes if they end up necessary. +// They are only necessary if they break a cycle (IE we recursively visit +// ourselves again), or we discover, while getting the value of the operands, +// that there are two or more definitions needing to be merged. +// This still will leave non-minimal form in the case of irreducible control +// flow, where phi nodes may be in cycles with themselves, but unnecessary. +MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) { + // Single predecessor case, just recurse, we can only have one definition. + if (BasicBlock *Pred = BB->getSinglePredecessor()) { + return getPreviousDefFromEnd(Pred); + } else if (VisitedBlocks.count(BB)) { + // We hit our node again, meaning we had a cycle, we must insert a phi + // node to break it so we have an operand. The only case this will + // insert useless phis is if we have irreducible control flow. + return MSSA->createMemoryPhi(BB); + } else if (VisitedBlocks.insert(BB).second) { + // Mark us visited so we can detect a cycle + SmallVector PhiOps; + + // Recurse to get the values in our predecessors for placement of a + // potential phi node. This will insert phi nodes if we cycle in order to + // break the cycle and have an operand. + for (auto *Pred : predecessors(BB)) + PhiOps.push_back(getPreviousDefFromEnd(Pred)); + + // Now try to simplify the ops to avoid placing a phi. + // This may return null if we never created a phi yet, that's okay + MemoryPhi *Phi = dyn_cast_or_null(MSSA->getMemoryAccess(BB)); + bool PHIExistsButNeedsUpdate = false; + // See if the existing phi operands match what we need. + // Unlike normal SSA, we only allow one phi node per block, so we can't just + // create a new one. + if (Phi && Phi->getNumOperands() != 0) + if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) { + PHIExistsButNeedsUpdate = true; + } + + // See if we can avoid the phi by simplifying it. + auto *Result = tryRemoveTrivialPhi(Phi, PhiOps); + // If we couldn't simplify, we may have to create a phi + if (Result == Phi) { + if (!Phi) + Phi = MSSA->createMemoryPhi(BB); + + // These will have been filled in by the recursive read we did above. + if (PHIExistsButNeedsUpdate) { + std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin()); + std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin()); + } else { + unsigned i = 0; + for (auto *Pred : predecessors(BB)) + Phi->addIncoming(PhiOps[i++], Pred); + } + + Result = Phi; + } + if (MemoryPhi *MP = dyn_cast(Result)) + InsertedPHIs.push_back(MP); + // Set ourselves up for the next variable by resetting visited state. + VisitedBlocks.erase(BB); + return Result; + } + llvm_unreachable("Should have hit one of the three cases above"); +} + +// This starts at the memory access, and goes backwards in the block to find the +// previous definition. If a definition is not found the block of the access, +// it continues globally, creating phi nodes to ensure we have a single +// definition. +MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) { + auto *LocalResult = getPreviousDefInBlock(MA); + + return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock()); +} + +// This starts at the memory access, and goes backwards in the block to the find +// the previous definition. If the definition is not found in the block of the +// access, it returns nullptr. +MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) { + auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock()); + + // It's possible there are no defs, or we got handed the first def to start. + if (Defs) { + // If this is a def, we can just use the def iterators. + if (!isa(MA)) { + auto Iter = MA->getReverseDefsIterator(); + ++Iter; + if (Iter != Defs->rend()) + return &*Iter; + } else { + // Otherwise, have to walk the all access iterator. + auto Iter = MA->getReverseIterator(); + ++Iter; + while (&*Iter != &*Defs->begin()) { + if (!isa(*Iter)) + return &*Iter; + --Iter; + } + // At this point it must be pointing at firstdef + assert(&*Iter == &*Defs->begin() && + "Should have hit first def walking backwards"); + return &*Iter; + } + } + return nullptr; +} + +// This starts at the end of block +MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) { + auto *Defs = MSSA->getWritableBlockDefs(BB); + + if (Defs) + return &*Defs->rbegin(); + + return getPreviousDefRecursive(BB); +} +// Recurse over a set of phi uses to eliminate the trivial ones +MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) { + if (!Phi) + return nullptr; + TrackingVH Res(Phi); + SmallVector, 8> Uses; + std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses)); + for (auto &U : Uses) { + if (MemoryPhi *UsePhi = dyn_cast(&*U)) { + auto OperRange = UsePhi->operands(); + tryRemoveTrivialPhi(UsePhi, OperRange); + } + } + return Res; +} + +// Eliminate trivial phis +// Phis are trivial if they are defined either by themselves, or all the same +// argument. +// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c) +// We recursively try to remove them. +template +MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi, + RangeType &Operands) { + // Detect equal or self arguments + MemoryAccess *Same = nullptr; + for (auto &Op : Operands) { + // If the same or self, good so far + if (Op == Phi || Op == Same) + continue; + // not the same, return the phi since it's not eliminatable by us + if (Same) + return Phi; + Same = cast(Op); + } + // Never found a non-self reference, the phi is undef + if (Same == nullptr) + return MSSA->getLiveOnEntryDef(); + if (Phi) { + Phi->replaceAllUsesWith(Same); + MSSA->removeMemoryAccess(Phi); + } + + // We should only end up recursing in case we replaced something, in which + // case, we may have made other Phis trivial. + return recursePhi(Same); +} + +void MemorySSAUpdater::insertUse(MemoryUse *MU) { + InsertedPHIs.clear(); + MU->setDefiningAccess(getPreviousDef(MU)); + // Unlike for defs, there is no extra work to do. Because uses do not create + // new may-defs, there are only two cases: + // + // 1. There was a def already below us, and therefore, we should not have + // created a phi node because it was already needed for the def. + // + // 2. There is no def below us, and therefore, there is no extra renaming work + // to do. +} + +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. + MP->setIncomingValue(i, NewDef); + ++i; + } +} + +// A brief description of the algorithm: +// First, we compute what should define the new def, using the SSA +// construction algorithm. +// Then, we update the defs below us (and any new phi nodes) in the graph to +// point to the correct new defs, to ensure we only have one variable, and no +// disconnected stores. +void MemorySSAUpdater::insertDef(MemoryDef *MD) { + InsertedPHIs.clear(); + + // See if we had a local def, and if not, go hunting. + MemoryAccess *DefBefore = getPreviousDefInBlock(MD); + bool DefBeforeSameBlock = DefBefore != nullptr; + if (!DefBefore) + DefBefore = getPreviousDefRecursive(MD->getBlock()); + + // There is a def before us, which means we can replace any store/phi uses + // 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); + } + // 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. + MD->setDefiningAccess(DefBefore); + + SmallVector FixupList(InsertedPHIs.begin(), + InsertedPHIs.end()); + if (!DefBeforeSameBlock) { + // If there was a local def before us, we must have the same effect it + // did. Because every may-def is the same, any phis/etc we would create, it + // would also have created. If there was no local def before us, we + // performed a global update, and have to search all successors and make + // sure we update the first def in each of them (following all paths until + // we hit the first def along each path). This may also insert phi nodes. + // TODO: There are other cases we can skip this work, such as when we have a + // single successor, and only used a straight line of single pred blocks + // backwards to find the def. To make that work, we'd have to track whether + // getDefRecursive only ever used the single predecessor case. These types + // of paths also only exist in between CFG simplifications. + FixupList.push_back(MD); + } + + while (!FixupList.empty()) { + unsigned StartingPHISize = InsertedPHIs.size(); + fixupDefs(FixupList); + FixupList.clear(); + // Put any new phis on the fixup list, and process them + FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end()); + } +} + +void MemorySSAUpdater::fixupDefs(const SmallVectorImpl &Vars) { + SmallPtrSet Seen; + SmallVector Worklist; + for (auto *NewDef : Vars) { + // First, see if there is a local def after the operand. + auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock()); + auto DefIter = NewDef->getDefsIterator(); + + // If there is a local def after us, we only have to rename that. + if (++DefIter != Defs->end()) { + cast(DefIter)->setDefiningAccess(NewDef); + continue; + } + + // Otherwise, we need to search down through the CFG. + // For each of our successors, handle it directly if their is a phi, or + // place on the fixup worklist. + for (const auto *S : successors(NewDef->getBlock())) { + if (auto *MP = MSSA->getMemoryAccess(S)) + setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef); + else + Worklist.push_back(S); + } + + while (!Worklist.empty()) { + const BasicBlock *FixupBlock = Worklist.back(); + Worklist.pop_back(); + + // Get the first def in the block that isn't a phi node. + if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) { + auto *FirstDef = &*Defs->begin(); + // The loop above and below should have taken care of phi nodes + assert(!isa(FirstDef) && + "Should have already handled phi nodes!"); + // We are now this def's defining access, make sure we actually dominate + // it + assert(MSSA->dominates(NewDef, FirstDef) && + "Should have dominated the new access"); + + // This may insert new phi nodes, because we are not guaranteed the + // block we are processing has a single pred, and depending where the + // store was inserted, it may require phi nodes below it. + cast(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef)); + return; + } + // We didn't find a def, so we must continue. + for (const auto *S : successors(FixupBlock)) { + // If there is a phi node, handle it. + // Otherwise, put the block on the worklist + if (auto *MP = MSSA->getMemoryAccess(S)) + setMemoryPhiValueForBlock(MP, FixupBlock, NewDef); + else { + // If we cycle, we should have ended up at a phi node that we already + // processed. FIXME: Double check this + if (!Seen.insert(S).second) + continue; + Worklist.push_back(S); + } + } + } + } +} + +// Move What before Where in the MemorySSA IR. +void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, + MemorySSA::AccessList::iterator Where) { + // Replace all our users with our defining access. + What->replaceAllUsesWith(What->getDefiningAccess()); + + // Let MemorySSA take care of moving it around in the lists. + MSSA->moveTo(What, BB, Where); + + // Now reinsert it into the IR and do whatever fixups needed. + if (auto *MD = dyn_cast(What)) + insertDef(MD); + 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()); +} + +// Move What after Where in the MemorySSA IR. +void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) { + moveTo(What, Where->getBlock(), ++Where->getIterator()); +} + +} // namespace llvm diff --git a/unittests/Transforms/Utils/MemorySSA.cpp b/unittests/Transforms/Utils/MemorySSA.cpp index 74f8d247f83..95ec3ed55e6 100644 --- a/unittests/Transforms/Utils/MemorySSA.cpp +++ b/unittests/Transforms/Utils/MemorySSA.cpp @@ -15,6 +15,7 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/Transforms/Utils/MemorySSAUpdater.h" #include "gtest/gtest.h" using namespace llvm; -- 2.50.1