SSAUpdater.cpp revision 93f3bcf7f323069e40d9abb950da73d437b6f7da
1//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the SSAUpdater class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Transforms/Utils/SSAUpdater.h" 15#include "llvm/Instructions.h" 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/Support/CFG.h" 18#include "llvm/Support/Debug.h" 19#include "llvm/Support/ValueHandle.h" 20#include "llvm/Support/raw_ostream.h" 21using namespace llvm; 22 23typedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy; 24typedef std::vector<std::pair<BasicBlock*, TrackingVH<Value> > > 25 IncomingPredInfoTy; 26 27static AvailableValsTy &getAvailableVals(void *AV) { 28 return *static_cast<AvailableValsTy*>(AV); 29} 30 31static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { 32 return *static_cast<IncomingPredInfoTy*>(IPI); 33} 34 35 36SSAUpdater::SSAUpdater() : AV(0), PrototypeValue(0), IPI(0) {} 37 38SSAUpdater::~SSAUpdater() { 39 delete &getAvailableVals(AV); 40 delete &getIncomingPredInfo(IPI); 41} 42 43/// Initialize - Reset this object to get ready for a new set of SSA 44/// updates. ProtoValue is the value used to name PHI nodes. 45void SSAUpdater::Initialize(Value *ProtoValue) { 46 if (AV == 0) 47 AV = new AvailableValsTy(); 48 else 49 getAvailableVals(AV).clear(); 50 51 if (IPI == 0) 52 IPI = new IncomingPredInfoTy(); 53 else 54 getIncomingPredInfo(IPI).clear(); 55 PrototypeValue = ProtoValue; 56} 57 58/// AddAvailableValue - Indicate that a rewritten value is available in the 59/// specified block with the specified value. 60void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 61 assert(PrototypeValue != 0 && "Need to initialize SSAUpdater"); 62 assert(PrototypeValue->getType() == V->getType() && 63 "All rewritten values must have the same type"); 64 getAvailableVals(AV)[BB] = V; 65} 66 67/// GetValueInBlock - Construct SSA form, materializing a value in the 68/// specified block. 69Value *SSAUpdater::GetValueInBlock(BasicBlock *BB) { 70 assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 71 Value *Res = GetValueInBlockInternal(BB); 72 assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 73 return Res; 74} 75 76/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 77/// which use their value in the corresponding predecessor. 78void SSAUpdater::RewriteUse(Use &U) { 79 Instruction *User = cast<Instruction>(U.getUser()); 80 BasicBlock *UseBB = User->getParent(); 81 if (PHINode *UserPN = dyn_cast<PHINode>(User)) 82 UseBB = UserPN->getIncomingBlock(U); 83 84 U.set(GetValueInBlock(UseBB)); 85} 86 87 88/// GetValueInBlock - Check to see if AvailableVals has an entry for the 89/// specified BB and if so, return it. If not, construct SSA form by walking 90/// predecessors inserting PHI nodes as needed until we get to a block where the 91/// value is available. 92/// 93Value *SSAUpdater::GetValueInBlockInternal(BasicBlock *BB) { 94 AvailableValsTy &AvailableVals = getAvailableVals(AV); 95 96 // Query AvailableVals by doing an insertion of null. 97 std::pair<AvailableValsTy::iterator, bool> InsertRes = 98 AvailableVals.insert(std::make_pair(BB, WeakVH())); 99 100 // Handle the case when the insertion fails because we have already seen BB. 101 if (!InsertRes.second) { 102 // If the insertion failed, there are two cases. The first case is that the 103 // value is already available for the specified block. If we get this, just 104 // return the value. 105 if (InsertRes.first->second != 0) 106 return InsertRes.first->second; 107 108 // Otherwise, if the value we find is null, then this is the value is not 109 // known but it is being computed elsewhere in our recursion. This means 110 // that we have a cycle. Handle this by inserting a PHI node and returning 111 // it. When we get back to the first instance of the recursion we will fill 112 // in the PHI node. 113 return InsertRes.first->second = 114 PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), 115 &BB->front()); 116 } 117 118 // Okay, the value isn't in the map and we just inserted a null in the entry 119 // to indicate that we're processing the block. Since we have no idea what 120 // value is in this block, we have to recurse through our predecessors. 121 // 122 // While we're walking our predecessors, we keep track of them in a vector, 123 // then insert a PHI node in the end if we actually need one. We could use a 124 // smallvector here, but that would take a lot of stack space for every level 125 // of the recursion, just use IncomingPredInfo as an explicit stack. 126 IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); 127 unsigned FirstPredInfoEntry = IncomingPredInfo.size(); 128 129 // As we're walking the predecessors, keep track of whether they are all 130 // producing the same value. If so, this value will capture it, if not, it 131 // will get reset to null. We distinguish the no-predecessor case explicitly 132 // below. 133 TrackingVH<Value> SingularValue; 134 135 // We can get our predecessor info by walking the pred_iterator list, but it 136 // is relatively slow. If we already have PHI nodes in this block, walk one 137 // of them to get the predecessor list instead. 138 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 139 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 140 BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 141 Value *PredVal = GetValueInBlockInternal(PredBB); 142 IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 143 144 // Compute SingularValue. 145 if (i == 0) 146 SingularValue = PredVal; 147 else if (PredVal != SingularValue) 148 SingularValue = 0; 149 } 150 } else { 151 bool isFirstPred = true; 152 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 153 BasicBlock *PredBB = *PI; 154 Value *PredVal = GetValueInBlockInternal(PredBB); 155 IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 156 157 // Compute SingularValue. 158 if (isFirstPred) { 159 SingularValue = PredVal; 160 isFirstPred = false; 161 } else if (PredVal != SingularValue) 162 SingularValue = 0; 163 } 164 } 165 166 // If there are no predecessors, then we must have found an unreachable block 167 // just return 'undef'. Since there are no predecessors, InsertRes must not 168 // be invalidated. 169 if (IncomingPredInfo.size() == FirstPredInfoEntry) 170 return InsertRes.first->second = UndefValue::get(PrototypeValue->getType()); 171 172 /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If 173 /// this block is involved in a loop, a no-entry PHI node will have been 174 /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted 175 /// above. 176 TrackingVH<Value> &InsertedVal = AvailableVals[BB]; 177 178 // If all the predecessor values are the same then we don't need to insert a 179 // PHI. This is the simple and common case. 180 if (SingularValue) { 181 // If a PHI node got inserted, replace it with the singlar value and delete 182 // it. 183 if (InsertedVal) { 184 PHINode *OldVal = cast<PHINode>(InsertedVal); 185 // Be careful about dead loops. These RAUW's also update InsertedVal. 186 if (InsertedVal != SingularValue) 187 OldVal->replaceAllUsesWith(SingularValue); 188 else 189 OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType())); 190 OldVal->eraseFromParent(); 191 } else { 192 InsertedVal = SingularValue; 193 } 194 195 // Drop the entries we added in IncomingPredInfo to restore the stack. 196 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 197 IncomingPredInfo.end()); 198 return InsertedVal; 199 } 200 201 // Otherwise, we do need a PHI: insert one now if we don't already have one. 202 if (InsertedVal == 0) 203 InsertedVal = PHINode::Create(PrototypeValue->getType(), 204 PrototypeValue->getName(), &BB->front()); 205 206 PHINode *InsertedPHI = cast<PHINode>(InsertedVal); 207 InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry); 208 209 // Fill in all the predecessors of the PHI. 210 for (std::vector<std::pair<BasicBlock*, TrackingVH<Value> > >::iterator I = 211 IncomingPredInfo.begin()+FirstPredInfoEntry, E = IncomingPredInfo.end(); 212 I != E; ++I) 213 InsertedPHI->addIncoming(I->second, I->first); 214 215 // Drop the entries we added in IncomingPredInfo to restore the stack. 216 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 217 IncomingPredInfo.end()); 218 219 // See if the PHI node can be merged to a single value. This can happen in 220 // loop cases when we get a PHI of itself and one other value. 221 if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 222 InsertedPHI->replaceAllUsesWith(ConstVal); 223 InsertedPHI->eraseFromParent(); 224 InsertedVal = ConstVal; 225 } else { 226 DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n"); 227 } 228 229 return InsertedVal; 230} 231 232 233