From 93f3bcf7f323069e40d9abb950da73d437b6f7da Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 10 Oct 2009 09:04:27 +0000 Subject: [PATCH] Implement an efficient and fully general SSA update mechanism that works on unstructured CFGs. This implements PR217, our oldest open PR. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83705 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/SSAUpdater.h | 71 +++++++ lib/Transforms/Utils/CMakeLists.txt | 1 + lib/Transforms/Utils/SSAUpdater.cpp | 232 +++++++++++++++++++++ 3 files changed, 304 insertions(+) create mode 100644 include/llvm/Transforms/Utils/SSAUpdater.h create mode 100644 lib/Transforms/Utils/SSAUpdater.cpp diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h new file mode 100644 index 00000000000..5e11984bf39 --- /dev/null +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -0,0 +1,71 @@ +//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the SSAUpdater class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H + +namespace llvm { + class Value; + class BasicBlock; + class Use; + +/// SSAUpdater - This class updates SSA form for a set of values defined in +/// multiple blocks. This is used when code duplication or another unstructured +/// transformation wants to rewrite a set of uses of one value with uses of a +/// set of values. +class SSAUpdater { + /// AvailableVals - This keeps track of which value to use on a per-block + /// basis. When we insert PHI nodes, we keep track of them here. We use + /// WeakVH's for the value of the map because we RAUW PHI nodes when we + /// eliminate them, and want the WeakVH to track this. + //typedef DenseMap > AvailableValsTy; + void *AV; + + /// PrototypeValue is an arbitrary representative value, which we derive names + /// and a type for PHI nodes. + Value *PrototypeValue; + + /// IncomingPredInfo - We use this as scratch space when doing our recursive + /// walk. This should only be used in GetValueInBlockInternal, normally it + /// should be empty. + //std::vector > > IncomingPredInfo; + void *IPI; +public: + SSAUpdater(); + ~SSAUpdater(); + + /// Initialize - Reset this object to get ready for a new set of SSA + /// updates. ProtoValue is the value used to name PHI nodes. + void Initialize(Value *ProtoValue); + + /// AddAvailableValue - Indicate that a rewritten value is available in the + /// specified block with the specified value. + void AddAvailableValue(BasicBlock *BB, Value *V); + + /// GetValueInBlock - Construct SSA form, materializing a value in the + /// specified block. + Value *GetValueInBlock(BasicBlock *BB); + + /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, + /// which use their value in the corresponding predecessor. + void RewriteUse(Use &U); + +private: + Value *GetValueInBlockInternal(BasicBlock *BB); + void operator=(const SSAUpdater&); // DO NOT IMPLEMENT + SSAUpdater(const SSAUpdater&); // DO NOT IMPLEMENT +}; + +} // End llvm namespace + +#endif diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt index aca4bca500b..9966b4dba7b 100644 --- a/lib/Transforms/Utils/CMakeLists.txt +++ b/lib/Transforms/Utils/CMakeLists.txt @@ -19,6 +19,7 @@ add_llvm_library(LLVMTransformUtils LowerSwitch.cpp Mem2Reg.cpp PromoteMemoryToRegister.cpp + SSAUpdater.cpp SSI.cpp SimplifyCFG.cpp UnifyFunctionExitNodes.cpp diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp new file mode 100644 index 00000000000..95e3ab8a474 --- /dev/null +++ b/lib/Transforms/Utils/SSAUpdater.cpp @@ -0,0 +1,232 @@ +//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===// +// +// 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 SSAUpdater class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/SSAUpdater.h" +#include "llvm/Instructions.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ValueHandle.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +typedef DenseMap > AvailableValsTy; +typedef std::vector > > + IncomingPredInfoTy; + +static AvailableValsTy &getAvailableVals(void *AV) { + return *static_cast(AV); +} + +static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { + return *static_cast(IPI); +} + + +SSAUpdater::SSAUpdater() : AV(0), PrototypeValue(0), IPI(0) {} + +SSAUpdater::~SSAUpdater() { + delete &getAvailableVals(AV); + delete &getIncomingPredInfo(IPI); +} + +/// Initialize - Reset this object to get ready for a new set of SSA +/// updates. ProtoValue is the value used to name PHI nodes. +void SSAUpdater::Initialize(Value *ProtoValue) { + if (AV == 0) + AV = new AvailableValsTy(); + else + getAvailableVals(AV).clear(); + + if (IPI == 0) + IPI = new IncomingPredInfoTy(); + else + getIncomingPredInfo(IPI).clear(); + PrototypeValue = ProtoValue; +} + +/// AddAvailableValue - Indicate that a rewritten value is available in the +/// specified block with the specified value. +void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { + assert(PrototypeValue != 0 && "Need to initialize SSAUpdater"); + assert(PrototypeValue->getType() == V->getType() && + "All rewritten values must have the same type"); + getAvailableVals(AV)[BB] = V; +} + +/// GetValueInBlock - Construct SSA form, materializing a value in the +/// specified block. +Value *SSAUpdater::GetValueInBlock(BasicBlock *BB) { + assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); + Value *Res = GetValueInBlockInternal(BB); + assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); + return Res; +} + +/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, +/// which use their value in the corresponding predecessor. +void SSAUpdater::RewriteUse(Use &U) { + Instruction *User = cast(U.getUser()); + BasicBlock *UseBB = User->getParent(); + if (PHINode *UserPN = dyn_cast(User)) + UseBB = UserPN->getIncomingBlock(U); + + U.set(GetValueInBlock(UseBB)); +} + + +/// GetValueInBlock - Check to see if AvailableVals has an entry for the +/// specified BB and if so, return it. If not, construct SSA form by walking +/// predecessors inserting PHI nodes as needed until we get to a block where the +/// value is available. +/// +Value *SSAUpdater::GetValueInBlockInternal(BasicBlock *BB) { + AvailableValsTy &AvailableVals = getAvailableVals(AV); + + // Query AvailableVals by doing an insertion of null. + std::pair InsertRes = + AvailableVals.insert(std::make_pair(BB, WeakVH())); + + // Handle the case when the insertion fails because we have already seen BB. + if (!InsertRes.second) { + // If the insertion failed, there are two cases. The first case is that the + // value is already available for the specified block. If we get this, just + // return the value. + if (InsertRes.first->second != 0) + return InsertRes.first->second; + + // Otherwise, if the value we find is null, then this is the value is not + // known but it is being computed elsewhere in our recursion. This means + // that we have a cycle. Handle this by inserting a PHI node and returning + // it. When we get back to the first instance of the recursion we will fill + // in the PHI node. + return InsertRes.first->second = + PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), + &BB->front()); + } + + // Okay, the value isn't in the map and we just inserted a null in the entry + // to indicate that we're processing the block. Since we have no idea what + // value is in this block, we have to recurse through our predecessors. + // + // While we're walking our predecessors, we keep track of them in a vector, + // then insert a PHI node in the end if we actually need one. We could use a + // smallvector here, but that would take a lot of stack space for every level + // of the recursion, just use IncomingPredInfo as an explicit stack. + IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); + unsigned FirstPredInfoEntry = IncomingPredInfo.size(); + + // As we're walking the predecessors, keep track of whether they are all + // producing the same value. If so, this value will capture it, if not, it + // will get reset to null. We distinguish the no-predecessor case explicitly + // below. + TrackingVH SingularValue; + + // We can get our predecessor info by walking the pred_iterator list, but it + // is relatively slow. If we already have PHI nodes in this block, walk one + // of them to get the predecessor list instead. + if (PHINode *SomePhi = dyn_cast(BB->begin())) { + for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { + BasicBlock *PredBB = SomePhi->getIncomingBlock(i); + Value *PredVal = GetValueInBlockInternal(PredBB); + IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); + + // Compute SingularValue. + if (i == 0) + SingularValue = PredVal; + else if (PredVal != SingularValue) + SingularValue = 0; + } + } else { + bool isFirstPred = true; + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *PredBB = *PI; + Value *PredVal = GetValueInBlockInternal(PredBB); + IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); + + // Compute SingularValue. + if (isFirstPred) { + SingularValue = PredVal; + isFirstPred = false; + } else if (PredVal != SingularValue) + SingularValue = 0; + } + } + + // If there are no predecessors, then we must have found an unreachable block + // just return 'undef'. Since there are no predecessors, InsertRes must not + // be invalidated. + if (IncomingPredInfo.size() == FirstPredInfoEntry) + return InsertRes.first->second = UndefValue::get(PrototypeValue->getType()); + + /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If + /// this block is involved in a loop, a no-entry PHI node will have been + /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted + /// above. + TrackingVH &InsertedVal = AvailableVals[BB]; + + // If all the predecessor values are the same then we don't need to insert a + // PHI. This is the simple and common case. + if (SingularValue) { + // If a PHI node got inserted, replace it with the singlar value and delete + // it. + if (InsertedVal) { + PHINode *OldVal = cast(InsertedVal); + // Be careful about dead loops. These RAUW's also update InsertedVal. + if (InsertedVal != SingularValue) + OldVal->replaceAllUsesWith(SingularValue); + else + OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType())); + OldVal->eraseFromParent(); + } else { + InsertedVal = SingularValue; + } + + // Drop the entries we added in IncomingPredInfo to restore the stack. + IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, + IncomingPredInfo.end()); + return InsertedVal; + } + + // Otherwise, we do need a PHI: insert one now if we don't already have one. + if (InsertedVal == 0) + InsertedVal = PHINode::Create(PrototypeValue->getType(), + PrototypeValue->getName(), &BB->front()); + + PHINode *InsertedPHI = cast(InsertedVal); + InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry); + + // Fill in all the predecessors of the PHI. + for (std::vector > >::iterator I = + IncomingPredInfo.begin()+FirstPredInfoEntry, E = IncomingPredInfo.end(); + I != E; ++I) + InsertedPHI->addIncoming(I->second, I->first); + + // Drop the entries we added in IncomingPredInfo to restore the stack. + IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, + IncomingPredInfo.end()); + + // See if the PHI node can be merged to a single value. This can happen in + // loop cases when we get a PHI of itself and one other value. + if (Value *ConstVal = InsertedPHI->hasConstantValue()) { + InsertedPHI->replaceAllUsesWith(ConstVal); + InsertedPHI->eraseFromParent(); + InsertedVal = ConstVal; + } else { + DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n"); + } + + return InsertedVal; +} + + -- 2.34.1