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