SSAUpdater.cpp revision 49c283fd3f8f81e04b84dc848981b4bf17b2d706
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(SmallVectorImpl<PHINode*> *NewPHI) 37 : AV(0), PrototypeValue(0), IPI(0), InsertedPHIs(NewPHI) {} 38 39SSAUpdater::~SSAUpdater() { 40 delete &getAvailableVals(AV); 41 delete &getIncomingPredInfo(IPI); 42} 43 44/// Initialize - Reset this object to get ready for a new set of SSA 45/// updates. ProtoValue is the value used to name PHI nodes. 46void SSAUpdater::Initialize(Value *ProtoValue) { 47 if (AV == 0) 48 AV = new AvailableValsTy(); 49 else 50 getAvailableVals(AV).clear(); 51 52 if (IPI == 0) 53 IPI = new IncomingPredInfoTy(); 54 else 55 getIncomingPredInfo(IPI).clear(); 56 PrototypeValue = ProtoValue; 57} 58 59/// HasValueForBlock - Return true if the SSAUpdater already has a value for 60/// the specified block. 61bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 62 return getAvailableVals(AV).count(BB); 63} 64 65/// AddAvailableValue - Indicate that a rewritten value is available in the 66/// specified block with the specified value. 67void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 68 assert(PrototypeValue != 0 && "Need to initialize SSAUpdater"); 69 assert(PrototypeValue->getType() == V->getType() && 70 "All rewritten values must have the same type"); 71 getAvailableVals(AV)[BB] = V; 72} 73 74/// IsEquivalentPHI - Check if PHI has the same incoming value as specified 75/// in ValueMapping for each predecessor block. 76static bool IsEquivalentPHI(PHINode *PHI, 77 DenseMap<BasicBlock*, Value*> &ValueMapping) { 78 unsigned PHINumValues = PHI->getNumIncomingValues(); 79 if (PHINumValues != ValueMapping.size()) 80 return false; 81 82 // Scan the phi to see if it matches. 83 for (unsigned i = 0, e = PHINumValues; i != e; ++i) 84 if (ValueMapping[PHI->getIncomingBlock(i)] != 85 PHI->getIncomingValue(i)) { 86 return false; 87 } 88 89 return true; 90} 91 92/// GetExistingPHI - Check if BB already contains a phi node that is equivalent 93/// to the specified mapping from predecessor blocks to incoming values. 94static Value *GetExistingPHI(BasicBlock *BB, 95 DenseMap<BasicBlock*, Value*> &ValueMapping) { 96 PHINode *SomePHI; 97 for (BasicBlock::iterator It = BB->begin(); 98 (SomePHI = dyn_cast<PHINode>(It)); ++It) { 99 if (IsEquivalentPHI(SomePHI, ValueMapping)) 100 return SomePHI; 101 } 102 return 0; 103} 104 105/// GetExistingPHI - Check if BB already contains an equivalent phi node. 106/// The InputIt type must be an iterator over std::pair<BasicBlock*, Value*> 107/// objects that specify the mapping from predecessor blocks to incoming values. 108template<typename InputIt> 109static Value *GetExistingPHI(BasicBlock *BB, const InputIt &I, 110 const InputIt &E) { 111 // Avoid create the mapping if BB has no phi nodes at all. 112 if (!isa<PHINode>(BB->begin())) 113 return 0; 114 DenseMap<BasicBlock*, Value*> ValueMapping(I, E); 115 return GetExistingPHI(BB, ValueMapping); 116} 117 118/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 119/// live at the end of the specified block. 120Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 121 assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 122 Value *Res = GetValueAtEndOfBlockInternal(BB); 123 assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 124 return Res; 125} 126 127/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 128/// is live in the middle of the specified block. 129/// 130/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 131/// important case: if there is a definition of the rewritten value after the 132/// 'use' in BB. Consider code like this: 133/// 134/// X1 = ... 135/// SomeBB: 136/// use(X) 137/// X2 = ... 138/// br Cond, SomeBB, OutBB 139/// 140/// In this case, there are two values (X1 and X2) added to the AvailableVals 141/// set by the client of the rewriter, and those values are both live out of 142/// their respective blocks. However, the use of X happens in the *middle* of 143/// a block. Because of this, we need to insert a new PHI node in SomeBB to 144/// merge the appropriate values, and this value isn't live out of the block. 145/// 146Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 147 // If there is no definition of the renamed variable in this block, just use 148 // GetValueAtEndOfBlock to do our work. 149 if (!getAvailableVals(AV).count(BB)) 150 return GetValueAtEndOfBlock(BB); 151 152 // Otherwise, we have the hard case. Get the live-in values for each 153 // predecessor. 154 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 155 Value *SingularValue = 0; 156 157 // We can get our predecessor info by walking the pred_iterator list, but it 158 // is relatively slow. If we already have PHI nodes in this block, walk one 159 // of them to get the predecessor list instead. 160 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 161 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 162 BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 163 Value *PredVal = GetValueAtEndOfBlock(PredBB); 164 PredValues.push_back(std::make_pair(PredBB, PredVal)); 165 166 // Compute SingularValue. 167 if (i == 0) 168 SingularValue = PredVal; 169 else if (PredVal != SingularValue) 170 SingularValue = 0; 171 } 172 } else { 173 bool isFirstPred = true; 174 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 175 BasicBlock *PredBB = *PI; 176 Value *PredVal = GetValueAtEndOfBlock(PredBB); 177 PredValues.push_back(std::make_pair(PredBB, PredVal)); 178 179 // Compute SingularValue. 180 if (isFirstPred) { 181 SingularValue = PredVal; 182 isFirstPred = false; 183 } else if (PredVal != SingularValue) 184 SingularValue = 0; 185 } 186 } 187 188 // If there are no predecessors, just return undef. 189 if (PredValues.empty()) 190 return UndefValue::get(PrototypeValue->getType()); 191 192 // Otherwise, if all the merged values are the same, just use it. 193 if (SingularValue != 0) 194 return SingularValue; 195 196 // Otherwise, we do need a PHI. 197 if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(), 198 PredValues.end())) 199 return ExistingPHI; 200 201 // Ok, we have no way out, insert a new one now. 202 PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), 203 PrototypeValue->getName(), 204 &BB->front()); 205 InsertedPHI->reserveOperandSpace(PredValues.size()); 206 207 // Fill in all the predecessors of the PHI. 208 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 209 InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first); 210 211 // See if the PHI node can be merged to a single value. This can happen in 212 // loop cases when we get a PHI of itself and one other value. 213 if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 214 InsertedPHI->eraseFromParent(); 215 return ConstVal; 216 } 217 218 // If the client wants to know about all new instructions, tell it. 219 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 220 221 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 222 return InsertedPHI; 223} 224 225/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 226/// which use their value in the corresponding predecessor. 227void SSAUpdater::RewriteUse(Use &U) { 228 Instruction *User = cast<Instruction>(U.getUser()); 229 230 Value *V; 231 if (PHINode *UserPN = dyn_cast<PHINode>(User)) 232 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 233 else 234 V = GetValueInMiddleOfBlock(User->getParent()); 235 236 U.set(V); 237} 238 239 240/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 241/// for the specified BB and if so, return it. If not, construct SSA form by 242/// walking predecessors inserting PHI nodes as needed until we get to a block 243/// where the value is available. 244/// 245Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 246 AvailableValsTy &AvailableVals = getAvailableVals(AV); 247 248 // Query AvailableVals by doing an insertion of null. 249 std::pair<AvailableValsTy::iterator, bool> InsertRes = 250 AvailableVals.insert(std::make_pair(BB, TrackingVH<Value>())); 251 252 // Handle the case when the insertion fails because we have already seen BB. 253 if (!InsertRes.second) { 254 // If the insertion failed, there are two cases. The first case is that the 255 // value is already available for the specified block. If we get this, just 256 // return the value. 257 if (InsertRes.first->second != 0) 258 return InsertRes.first->second; 259 260 // Otherwise, if the value we find is null, then this is the value is not 261 // known but it is being computed elsewhere in our recursion. This means 262 // that we have a cycle. Handle this by inserting a PHI node and returning 263 // it. When we get back to the first instance of the recursion we will fill 264 // in the PHI node. 265 return InsertRes.first->second = 266 PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), 267 &BB->front()); 268 } 269 270 // Okay, the value isn't in the map and we just inserted a null in the entry 271 // to indicate that we're processing the block. Since we have no idea what 272 // value is in this block, we have to recurse through our predecessors. 273 // 274 // While we're walking our predecessors, we keep track of them in a vector, 275 // then insert a PHI node in the end if we actually need one. We could use a 276 // smallvector here, but that would take a lot of stack space for every level 277 // of the recursion, just use IncomingPredInfo as an explicit stack. 278 IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); 279 unsigned FirstPredInfoEntry = IncomingPredInfo.size(); 280 281 // As we're walking the predecessors, keep track of whether they are all 282 // producing the same value. If so, this value will capture it, if not, it 283 // will get reset to null. We distinguish the no-predecessor case explicitly 284 // below. 285 TrackingVH<Value> ExistingValue; 286 287 // We can get our predecessor info by walking the pred_iterator list, but it 288 // is relatively slow. If we already have PHI nodes in this block, walk one 289 // of them to get the predecessor list instead. 290 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 291 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 292 BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 293 Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); 294 IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 295 296 // Set ExistingValue to singular value from all predecessors so far. 297 if (i == 0) 298 ExistingValue = PredVal; 299 else if (PredVal != ExistingValue) 300 ExistingValue = 0; 301 } 302 } else { 303 bool isFirstPred = true; 304 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 305 BasicBlock *PredBB = *PI; 306 Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); 307 IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 308 309 // Set ExistingValue to singular value from all predecessors so far. 310 if (isFirstPred) { 311 ExistingValue = PredVal; 312 isFirstPred = false; 313 } else if (PredVal != ExistingValue) 314 ExistingValue = 0; 315 } 316 } 317 318 // If there are no predecessors, then we must have found an unreachable block 319 // just return 'undef'. Since there are no predecessors, InsertRes must not 320 // be invalidated. 321 if (IncomingPredInfo.size() == FirstPredInfoEntry) 322 return InsertRes.first->second = UndefValue::get(PrototypeValue->getType()); 323 324 /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If 325 /// this block is involved in a loop, a no-entry PHI node will have been 326 /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted 327 /// above. 328 TrackingVH<Value> &InsertedVal = AvailableVals[BB]; 329 330 // If the predecessor values are not all the same, then check to see if there 331 // is an existing PHI that can be used. 332 if (!ExistingValue) 333 ExistingValue = GetExistingPHI(BB, 334 IncomingPredInfo.begin()+FirstPredInfoEntry, 335 IncomingPredInfo.end()); 336 337 // If there is an existing value we can use, then we don't need to insert a 338 // PHI. This is the simple and common case. 339 if (ExistingValue) { 340 // If a PHI node got inserted, replace it with the existing value and delete 341 // it. 342 if (InsertedVal) { 343 PHINode *OldVal = cast<PHINode>(InsertedVal); 344 // Be careful about dead loops. These RAUW's also update InsertedVal. 345 if (InsertedVal != ExistingValue) 346 OldVal->replaceAllUsesWith(ExistingValue); 347 else 348 OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType())); 349 OldVal->eraseFromParent(); 350 } else { 351 InsertedVal = ExistingValue; 352 } 353 354 // Either path through the 'if' should have set InsertedVal -> ExistingVal. 355 assert((InsertedVal == ExistingValue || isa<UndefValue>(InsertedVal)) && 356 "RAUW didn't change InsertedVal to be ExistingValue"); 357 358 // Drop the entries we added in IncomingPredInfo to restore the stack. 359 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 360 IncomingPredInfo.end()); 361 return ExistingValue; 362 } 363 364 // Otherwise, we do need a PHI: insert one now if we don't already have one. 365 if (InsertedVal == 0) 366 InsertedVal = PHINode::Create(PrototypeValue->getType(), 367 PrototypeValue->getName(), &BB->front()); 368 369 PHINode *InsertedPHI = cast<PHINode>(InsertedVal); 370 InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry); 371 372 // Fill in all the predecessors of the PHI. 373 for (IncomingPredInfoTy::iterator I = 374 IncomingPredInfo.begin()+FirstPredInfoEntry, 375 E = IncomingPredInfo.end(); I != E; ++I) 376 InsertedPHI->addIncoming(I->second, I->first); 377 378 // Drop the entries we added in IncomingPredInfo to restore the stack. 379 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 380 IncomingPredInfo.end()); 381 382 // See if the PHI node can be merged to a single value. This can happen in 383 // loop cases when we get a PHI of itself and one other value. 384 if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 385 InsertedPHI->replaceAllUsesWith(ConstVal); 386 InsertedPHI->eraseFromParent(); 387 InsertedVal = ConstVal; 388 } else { 389 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 390 391 // If the client wants to know about all new instructions, tell it. 392 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 393 } 394 395 return InsertedVal; 396} 397