diff options
| -rw-r--r-- | include/llvm/CodeGen/MachineSSAUpdater.h | 99 | ||||
| -rw-r--r-- | lib/CodeGen/MachineSSAUpdater.cpp | 108 |
2 files changed, 207 insertions, 0 deletions
diff --git a/include/llvm/CodeGen/MachineSSAUpdater.h b/include/llvm/CodeGen/MachineSSAUpdater.h new file mode 100644 index 0000000000..a785ab8cfa --- /dev/null +++ b/include/llvm/CodeGen/MachineSSAUpdater.h @@ -0,0 +1,99 @@ +//===-- MachineSSAUpdater.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 MachineSSAUpdater class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINESSAUPDATER_H +#define LLVM_CODEGEN_MACHINESSAUPDATER_H + +namespace llvm { + class MachineBasicBlock; + class MachineInstr; + template<typename T> class SmallVectorImpl; + +/// 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 MachineSSAUpdater { + /// 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. + //typedef DenseMap<MachineBasicBlock*, unsigned > AvailableValsTy; + void *AV; + + /// 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<std::pair<MachineBasicBlock*, unsigned > > IncomingPredInfo; + void *IPI; + + /// InsertedPHIs - If this is non-null, the MachineSSAUpdater adds all PHI + /// nodes that it creates to the vector. + SmallVectorImpl<MachineInstr*> *InsertedPHIs; +public: + /// MachineSSAUpdater constructor. If InsertedPHIs is specified, it will be + /// filled in with all PHI Nodes created by rewriting. + explicit MachineSSAUpdater(SmallVectorImpl<MachineInstr*> *InsertedPHIs = 0); + ~MachineSSAUpdater(); + + /// Initialize - Reset this object to get ready for a new set of SSA + /// updates. + void Initialize(); + + /// AddAvailableValue - Indicate that a rewritten value is available at the + /// end of the specified block with the specified value. + void AddAvailableValue(MachineBasicBlock *BB, unsigned V); + + /// HasValueForBlock - Return true if the MachineSSAUpdater already has a + /// value for the specified block. + bool HasValueForBlock(MachineBasicBlock *BB) const; + + /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is + /// live at the end of the specified block. + unsigned GetValueAtEndOfBlock(MachineBasicBlock *BB); + + /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that + /// is live in the middle of the specified block. + /// + /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one + /// important case: if there is a definition of the rewritten value after the + /// 'use' in BB. Consider code like this: + /// + /// X1 = ... + /// SomeBB: + /// use(X) + /// X2 = ... + /// br Cond, SomeBB, OutBB + /// + /// In this case, there are two values (X1 and X2) added to the AvailableVals + /// set by the client of the rewriter, and those values are both live out of + /// their respective blocks. However, the use of X happens in the *middle* of + /// a block. Because of this, we need to insert a new PHI node in SomeBB to + /// merge the appropriate values, and this value isn't live out of the block. + /// + unsigned GetValueInMiddleOfBlock(MachineBasicBlock *BB); + + /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, + /// which use their value in the corresponding predecessor. Note that this + /// will not work if the use is supposed to be rewritten to a value defined in + /// the same block as the use, but above it. Any 'AddAvailableValue's added + /// for the use's block will be considered to be below it. + void RewriteUse(unsigned &U); + +private: + unsigned GetValueAtEndOfBlockInternal(MachineBasicBlock *BB); + void operator=(const MachineSSAUpdater&); // DO NOT IMPLEMENT + MachineSSAUpdater(const MachineSSAUpdater&); // DO NOT IMPLEMENT +}; + +} // End llvm namespace + +#endif diff --git a/lib/CodeGen/MachineSSAUpdater.cpp b/lib/CodeGen/MachineSSAUpdater.cpp new file mode 100644 index 0000000000..c0eb170cfb --- /dev/null +++ b/lib/CodeGen/MachineSSAUpdater.cpp @@ -0,0 +1,108 @@ +//===- MachineSSAUpdater.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 MachineSSAUpdater class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineSSAUpdater.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/ADT/DenseMap.h" +using namespace llvm; + +typedef DenseMap<MachineBasicBlock*, unsigned > AvailableValsTy; +typedef std::vector<std::pair<MachineBasicBlock*, unsigned> > + IncomingPredInfoTy; + +static AvailableValsTy &getAvailableVals(void *AV) { + return *static_cast<AvailableValsTy*>(AV); +} + +static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { + return *static_cast<IncomingPredInfoTy*>(IPI); +} + + +MachineSSAUpdater::MachineSSAUpdater(SmallVectorImpl<MachineInstr*> *NewPHI) + : AV(0), IPI(0), InsertedPHIs(NewPHI) {} + +MachineSSAUpdater::~MachineSSAUpdater() { + 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 MachineSSAUpdater::Initialize() { + if (AV == 0) + AV = new AvailableValsTy(); + else + getAvailableVals(AV).clear(); + + if (IPI == 0) + IPI = new IncomingPredInfoTy(); + else + getIncomingPredInfo(IPI).clear(); +} + +/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for +/// the specified block. +bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const { + return getAvailableVals(AV).count(BB); +} + +/// AddAvailableValue - Indicate that a rewritten value is available in the +/// specified block with the specified value. +void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) { + getAvailableVals(AV)[BB] = V; +} + +/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is +/// live at the end of the specified block. +unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { + return GetValueAtEndOfBlockInternal(BB); +} + +/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that +/// is live in the middle of the specified block. +/// +/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one +/// important case: if there is a definition of the rewritten value after the +/// 'use' in BB. Consider code like this: +/// +/// X1 = ... +/// SomeBB: +/// use(X) +/// X2 = ... +/// br Cond, SomeBB, OutBB +/// +/// In this case, there are two values (X1 and X2) added to the AvailableVals +/// set by the client of the rewriter, and those values are both live out of +/// their respective blocks. However, the use of X happens in the *middle* of +/// a block. Because of this, we need to insert a new PHI node in SomeBB to +/// merge the appropriate values, and this value isn't live out of the block. +/// +unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { + return 0; +} + +/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, +/// which use their value in the corresponding predecessor. +void MachineSSAUpdater::RewriteUse(unsigned &U) { +} + + +/// GetValueAtEndOfBlockInternal - 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. +/// +unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ + return 0; +} |