SSAUpdater.cpp revision 4d588bceb035589ade874f432d70a41bb7ec6273
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#define DEBUG_TYPE "ssaupdater" 15#include "llvm/Instructions.h" 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/Support/AlignOf.h" 18#include "llvm/Support/Allocator.h" 19#include "llvm/Support/CFG.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/Support/raw_ostream.h" 22#include "llvm/Transforms/Utils/SSAUpdater.h" 23#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 24using namespace llvm; 25 26typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 27static AvailableValsTy &getAvailableVals(void *AV) { 28 return *static_cast<AvailableValsTy*>(AV); 29} 30 31SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 32 : AV(0), ProtoType(0), ProtoName(), InsertedPHIs(NewPHI) {} 33 34SSAUpdater::~SSAUpdater() { 35 delete &getAvailableVals(AV); 36} 37 38/// Initialize - Reset this object to get ready for a new set of SSA 39/// updates with type 'Ty'. PHI nodes get a name based on 'Name'. 40void SSAUpdater::Initialize(const Type *Ty, StringRef Name) { 41 if (AV == 0) 42 AV = new AvailableValsTy(); 43 else 44 getAvailableVals(AV).clear(); 45 ProtoType = Ty; 46 ProtoName = Name; 47} 48 49/// HasValueForBlock - Return true if the SSAUpdater already has a value for 50/// the specified block. 51bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 52 return getAvailableVals(AV).count(BB); 53} 54 55/// AddAvailableValue - Indicate that a rewritten value is available in the 56/// specified block with the specified value. 57void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 58 assert(ProtoType != 0 && "Need to initialize SSAUpdater"); 59 assert(ProtoType == V->getType() && 60 "All rewritten values must have the same type"); 61 getAvailableVals(AV)[BB] = V; 62} 63 64/// IsEquivalentPHI - Check if PHI has the same incoming value as specified 65/// in ValueMapping for each predecessor block. 66static bool IsEquivalentPHI(PHINode *PHI, 67 DenseMap<BasicBlock*, Value*> &ValueMapping) { 68 unsigned PHINumValues = PHI->getNumIncomingValues(); 69 if (PHINumValues != ValueMapping.size()) 70 return false; 71 72 // Scan the phi to see if it matches. 73 for (unsigned i = 0, e = PHINumValues; i != e; ++i) 74 if (ValueMapping[PHI->getIncomingBlock(i)] != 75 PHI->getIncomingValue(i)) { 76 return false; 77 } 78 79 return true; 80} 81 82/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 83/// live at the end of the specified block. 84Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 85 Value *Res = GetValueAtEndOfBlockInternal(BB); 86 return Res; 87} 88 89/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 90/// is live in the middle of the specified block. 91/// 92/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 93/// important case: if there is a definition of the rewritten value after the 94/// 'use' in BB. Consider code like this: 95/// 96/// X1 = ... 97/// SomeBB: 98/// use(X) 99/// X2 = ... 100/// br Cond, SomeBB, OutBB 101/// 102/// In this case, there are two values (X1 and X2) added to the AvailableVals 103/// set by the client of the rewriter, and those values are both live out of 104/// their respective blocks. However, the use of X happens in the *middle* of 105/// a block. Because of this, we need to insert a new PHI node in SomeBB to 106/// merge the appropriate values, and this value isn't live out of the block. 107/// 108Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 109 // If there is no definition of the renamed variable in this block, just use 110 // GetValueAtEndOfBlock to do our work. 111 if (!HasValueForBlock(BB)) 112 return GetValueAtEndOfBlock(BB); 113 114 // Otherwise, we have the hard case. Get the live-in values for each 115 // predecessor. 116 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 117 Value *SingularValue = 0; 118 119 // We can get our predecessor info by walking the pred_iterator list, but it 120 // is relatively slow. If we already have PHI nodes in this block, walk one 121 // of them to get the predecessor list instead. 122 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 123 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 124 BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 125 Value *PredVal = GetValueAtEndOfBlock(PredBB); 126 PredValues.push_back(std::make_pair(PredBB, PredVal)); 127 128 // Compute SingularValue. 129 if (i == 0) 130 SingularValue = PredVal; 131 else if (PredVal != SingularValue) 132 SingularValue = 0; 133 } 134 } else { 135 bool isFirstPred = true; 136 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 137 BasicBlock *PredBB = *PI; 138 Value *PredVal = GetValueAtEndOfBlock(PredBB); 139 PredValues.push_back(std::make_pair(PredBB, PredVal)); 140 141 // Compute SingularValue. 142 if (isFirstPred) { 143 SingularValue = PredVal; 144 isFirstPred = false; 145 } else if (PredVal != SingularValue) 146 SingularValue = 0; 147 } 148 } 149 150 // If there are no predecessors, just return undef. 151 if (PredValues.empty()) 152 return UndefValue::get(ProtoType); 153 154 // Otherwise, if all the merged values are the same, just use it. 155 if (SingularValue != 0) 156 return SingularValue; 157 158 // Otherwise, we do need a PHI: check to see if we already have one available 159 // in this block that produces the right value. 160 if (isa<PHINode>(BB->begin())) { 161 DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(), 162 PredValues.end()); 163 PHINode *SomePHI; 164 for (BasicBlock::iterator It = BB->begin(); 165 (SomePHI = dyn_cast<PHINode>(It)); ++It) { 166 if (IsEquivalentPHI(SomePHI, ValueMapping)) 167 return SomePHI; 168 } 169 } 170 171 // Ok, we have no way out, insert a new one now. 172 PHINode *InsertedPHI = PHINode::Create(ProtoType, ProtoName, &BB->front()); 173 InsertedPHI->reserveOperandSpace(PredValues.size()); 174 175 // Fill in all the predecessors of the PHI. 176 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 177 InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first); 178 179 // See if the PHI node can be merged to a single value. This can happen in 180 // loop cases when we get a PHI of itself and one other value. 181 if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 182 InsertedPHI->eraseFromParent(); 183 return ConstVal; 184 } 185 186 // If the client wants to know about all new instructions, tell it. 187 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 188 189 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 190 return InsertedPHI; 191} 192 193/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 194/// which use their value in the corresponding predecessor. 195void SSAUpdater::RewriteUse(Use &U) { 196 Instruction *User = cast<Instruction>(U.getUser()); 197 198 Value *V; 199 if (PHINode *UserPN = dyn_cast<PHINode>(User)) 200 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 201 else 202 V = GetValueInMiddleOfBlock(User->getParent()); 203 204 U.set(V); 205} 206 207/// RewriteUseAfterInsertions - Rewrite a use, just like RewriteUse. However, 208/// this version of the method can rewrite uses in the same block as a 209/// definition, because it assumes that all uses of a value are below any 210/// inserted values. 211void SSAUpdater::RewriteUseAfterInsertions(Use &U) { 212 Instruction *User = cast<Instruction>(U.getUser()); 213 214 Value *V; 215 if (PHINode *UserPN = dyn_cast<PHINode>(User)) 216 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 217 else 218 V = GetValueAtEndOfBlock(User->getParent()); 219 220 U.set(V); 221} 222 223/// PHIiter - Iterator for PHI operands. This is used for the PHI_iterator 224/// in the SSAUpdaterImpl template. 225namespace { 226 class PHIiter { 227 private: 228 PHINode *PHI; 229 unsigned idx; 230 231 public: 232 explicit PHIiter(PHINode *P) // begin iterator 233 : PHI(P), idx(0) {} 234 PHIiter(PHINode *P, bool) // end iterator 235 : PHI(P), idx(PHI->getNumIncomingValues()) {} 236 237 PHIiter &operator++() { ++idx; return *this; } 238 bool operator==(const PHIiter& x) const { return idx == x.idx; } 239 bool operator!=(const PHIiter& x) const { return !operator==(x); } 240 Value *getIncomingValue() { return PHI->getIncomingValue(idx); } 241 BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); } 242 }; 243} 244 245/// SSAUpdaterTraits<SSAUpdater> - Traits for the SSAUpdaterImpl template, 246/// specialized for SSAUpdater. 247namespace llvm { 248template<> 249class SSAUpdaterTraits<SSAUpdater> { 250public: 251 typedef BasicBlock BlkT; 252 typedef Value *ValT; 253 typedef PHINode PhiT; 254 255 typedef succ_iterator BlkSucc_iterator; 256 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); } 257 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); } 258 259 typedef PHIiter PHI_iterator; 260 static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 261 static inline PHI_iterator PHI_end(PhiT *PHI) { 262 return PHI_iterator(PHI, true); 263 } 264 265 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds 266 /// vector, set Info->NumPreds, and allocate space in Info->Preds. 267 static void FindPredecessorBlocks(BasicBlock *BB, 268 SmallVectorImpl<BasicBlock*> *Preds) { 269 // We can get our predecessor info by walking the pred_iterator list, 270 // but it is relatively slow. If we already have PHI nodes in this 271 // block, walk one of them to get the predecessor list instead. 272 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 273 for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI) 274 Preds->push_back(SomePhi->getIncomingBlock(PI)); 275 } else { 276 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 277 Preds->push_back(*PI); 278 } 279 } 280 281 /// GetUndefVal - Get an undefined value of the same type as the value 282 /// being handled. 283 static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) { 284 return UndefValue::get(Updater->ProtoType); 285 } 286 287 /// CreateEmptyPHI - Create a new PHI instruction in the specified block. 288 /// Reserve space for the operands but do not fill them in yet. 289 static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, 290 SSAUpdater *Updater) { 291 PHINode *PHI = PHINode::Create(Updater->ProtoType, Updater->ProtoName, 292 &BB->front()); 293 PHI->reserveOperandSpace(NumPreds); 294 return PHI; 295 } 296 297 /// AddPHIOperand - Add the specified value as an operand of the PHI for 298 /// the specified predecessor block. 299 static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) { 300 PHI->addIncoming(Val, Pred); 301 } 302 303 /// InstrIsPHI - Check if an instruction is a PHI. 304 /// 305 static PHINode *InstrIsPHI(Instruction *I) { 306 return dyn_cast<PHINode>(I); 307 } 308 309 /// ValueIsPHI - Check if a value is a PHI. 310 /// 311 static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) { 312 return dyn_cast<PHINode>(Val); 313 } 314 315 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 316 /// operands, i.e., it was just added. 317 static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) { 318 PHINode *PHI = ValueIsPHI(Val, Updater); 319 if (PHI && PHI->getNumIncomingValues() == 0) 320 return PHI; 321 return 0; 322 } 323 324 /// GetPHIValue - For the specified PHI instruction, return the value 325 /// that it defines. 326 static Value *GetPHIValue(PHINode *PHI) { 327 return PHI; 328 } 329}; 330 331} // End llvm namespace 332 333/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 334/// for the specified BB and if so, return it. If not, construct SSA form by 335/// first calculating the required placement of PHIs and then inserting new 336/// PHIs where needed. 337Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 338 AvailableValsTy &AvailableVals = getAvailableVals(AV); 339 if (Value *V = AvailableVals[BB]) 340 return V; 341 342 SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 343 return Impl.GetValue(BB); 344} 345