1 //===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the MachineSSAUpdater class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineSSAUpdater.h"
15 #include "llvm/CodeGen/MachineInstr.h"
16 #include "llvm/ADT/DenseMap.h"
19 typedef DenseMap<MachineBasicBlock*, unsigned > AvailableValsTy;
20 typedef std::vector<std::pair<MachineBasicBlock*, unsigned> >
23 static AvailableValsTy &getAvailableVals(void *AV) {
24 return *static_cast<AvailableValsTy*>(AV);
27 static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) {
28 return *static_cast<IncomingPredInfoTy*>(IPI);
32 MachineSSAUpdater::MachineSSAUpdater(SmallVectorImpl<MachineInstr*> *NewPHI)
33 : AV(0), IPI(0), InsertedPHIs(NewPHI) {}
35 MachineSSAUpdater::~MachineSSAUpdater() {
36 delete &getAvailableVals(AV);
37 delete &getIncomingPredInfo(IPI);
40 /// Initialize - Reset this object to get ready for a new set of SSA
41 /// updates. ProtoValue is the value used to name PHI nodes.
42 void MachineSSAUpdater::Initialize() {
44 AV = new AvailableValsTy();
46 getAvailableVals(AV).clear();
49 IPI = new IncomingPredInfoTy();
51 getIncomingPredInfo(IPI).clear();
54 /// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for
55 /// the specified block.
56 bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {
57 return getAvailableVals(AV).count(BB);
60 /// AddAvailableValue - Indicate that a rewritten value is available in the
61 /// specified block with the specified value.
62 void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {
63 getAvailableVals(AV)[BB] = V;
66 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
67 /// live at the end of the specified block.
68 unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {
69 return GetValueAtEndOfBlockInternal(BB);
72 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
73 /// is live in the middle of the specified block.
75 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
76 /// important case: if there is a definition of the rewritten value after the
77 /// 'use' in BB. Consider code like this:
83 /// br Cond, SomeBB, OutBB
85 /// In this case, there are two values (X1 and X2) added to the AvailableVals
86 /// set by the client of the rewriter, and those values are both live out of
87 /// their respective blocks. However, the use of X happens in the *middle* of
88 /// a block. Because of this, we need to insert a new PHI node in SomeBB to
89 /// merge the appropriate values, and this value isn't live out of the block.
91 unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
95 /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,
96 /// which use their value in the corresponding predecessor.
97 void MachineSSAUpdater::RewriteUse(unsigned &U) {
101 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
102 /// for the specified BB and if so, return it. If not, construct SSA form by
103 /// walking predecessors inserting PHI nodes as needed until we get to a block
104 /// where the value is available.
106 unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){