1 //===- MachineSSAUpdater.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 MachineSSAUpdater class. It's based on SSAUpdater 11 // class in lib/Transforms/Utils. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/CodeGen/MachineSSAUpdater.h" 16 #include "llvm/CodeGen/MachineInstr.h" 17 #include "llvm/CodeGen/MachineInstrBuilder.h" 18 #include "llvm/CodeGen/MachineRegisterInfo.h" 19 #include "llvm/Target/TargetInstrInfo.h" 20 #include "llvm/Target/TargetMachine.h" 21 #include "llvm/Target/TargetRegisterInfo.h" 22 #include "llvm/ADT/DenseMap.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/Support/AlignOf.h" 25 #include "llvm/Support/Allocator.h" 26 #include "llvm/Support/Debug.h" 27 #include "llvm/Support/ErrorHandling.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 30 using namespace llvm; 31 32 typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy; 33 static AvailableValsTy &getAvailableVals(void *AV) { 34 return *static_cast<AvailableValsTy*>(AV); 35 } 36 37 MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, 38 SmallVectorImpl<MachineInstr*> *NewPHI) 39 : AV(0), InsertedPHIs(NewPHI) { 40 TII = MF.getTarget().getInstrInfo(); 41 MRI = &MF.getRegInfo(); 42 } 43 44 MachineSSAUpdater::~MachineSSAUpdater() { 45 delete static_cast<AvailableValsTy*>(AV); 46 } 47 48 /// Initialize - Reset this object to get ready for a new set of SSA 49 /// updates. ProtoValue is the value used to name PHI nodes. 50 void MachineSSAUpdater::Initialize(unsigned V) { 51 if (AV == 0) 52 AV = new AvailableValsTy(); 53 else 54 getAvailableVals(AV).clear(); 55 56 VR = V; 57 VRC = MRI->getRegClass(VR); 58 } 59 60 /// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for 61 /// the specified block. 62 bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const { 63 return getAvailableVals(AV).count(BB); 64 } 65 66 /// AddAvailableValue - Indicate that a rewritten value is available in the 67 /// specified block with the specified value. 68 void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) { 69 getAvailableVals(AV)[BB] = V; 70 } 71 72 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 73 /// live at the end of the specified block. 74 unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { 75 return GetValueAtEndOfBlockInternal(BB); 76 } 77 78 static 79 unsigned LookForIdenticalPHI(MachineBasicBlock *BB, 80 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) { 81 if (BB->empty()) 82 return 0; 83 84 MachineBasicBlock::iterator I = BB->front(); 85 if (!I->isPHI()) 86 return 0; 87 88 AvailableValsTy AVals; 89 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 90 AVals[PredValues[i].first] = PredValues[i].second; 91 while (I != BB->end() && I->isPHI()) { 92 bool Same = true; 93 for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) { 94 unsigned SrcReg = I->getOperand(i).getReg(); 95 MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB(); 96 if (AVals[SrcBB] != SrcReg) { 97 Same = false; 98 break; 99 } 100 } 101 if (Same) 102 return I->getOperand(0).getReg(); 103 ++I; 104 } 105 return 0; 106 } 107 108 /// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define 109 /// a value of the given register class at the start of the specified basic 110 /// block. It returns the virtual register defined by the instruction. 111 static 112 MachineInstr *InsertNewDef(unsigned Opcode, 113 MachineBasicBlock *BB, MachineBasicBlock::iterator I, 114 const TargetRegisterClass *RC, 115 MachineRegisterInfo *MRI, 116 const TargetInstrInfo *TII) { 117 unsigned NewVR = MRI->createVirtualRegister(RC); 118 return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR); 119 } 120 121 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 122 /// is live in the middle of the specified block. 123 /// 124 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 125 /// important case: if there is a definition of the rewritten value after the 126 /// 'use' in BB. Consider code like this: 127 /// 128 /// X1 = ... 129 /// SomeBB: 130 /// use(X) 131 /// X2 = ... 132 /// br Cond, SomeBB, OutBB 133 /// 134 /// In this case, there are two values (X1 and X2) added to the AvailableVals 135 /// set by the client of the rewriter, and those values are both live out of 136 /// their respective blocks. However, the use of X happens in the *middle* of 137 /// a block. Because of this, we need to insert a new PHI node in SomeBB to 138 /// merge the appropriate values, and this value isn't live out of the block. 139 /// 140 unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { 141 // If there is no definition of the renamed variable in this block, just use 142 // GetValueAtEndOfBlock to do our work. 143 if (!HasValueForBlock(BB)) 144 return GetValueAtEndOfBlockInternal(BB); 145 146 // If there are no predecessors, just return undef. 147 if (BB->pred_empty()) { 148 // Insert an implicit_def to represent an undef value. 149 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 150 BB, BB->getFirstTerminator(), 151 VRC, MRI, TII); 152 return NewDef->getOperand(0).getReg(); 153 } 154 155 // Otherwise, we have the hard case. Get the live-in values for each 156 // predecessor. 157 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues; 158 unsigned SingularValue = 0; 159 160 bool isFirstPred = true; 161 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 162 E = BB->pred_end(); PI != E; ++PI) { 163 MachineBasicBlock *PredBB = *PI; 164 unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB); 165 PredValues.push_back(std::make_pair(PredBB, PredVal)); 166 167 // Compute SingularValue. 168 if (isFirstPred) { 169 SingularValue = PredVal; 170 isFirstPred = false; 171 } else if (PredVal != SingularValue) 172 SingularValue = 0; 173 } 174 175 // Otherwise, if all the merged values are the same, just use it. 176 if (SingularValue != 0) 177 return SingularValue; 178 179 // If an identical PHI is already in BB, just reuse it. 180 unsigned DupPHI = LookForIdenticalPHI(BB, PredValues); 181 if (DupPHI) 182 return DupPHI; 183 184 // Otherwise, we do need a PHI: insert one now. 185 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front(); 186 MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, 187 Loc, VRC, MRI, TII); 188 189 // Fill in all the predecessors of the PHI. 190 MachineInstrBuilder MIB(InsertedPHI); 191 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 192 MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first); 193 194 // See if the PHI node can be merged to a single value. This can happen in 195 // loop cases when we get a PHI of itself and one other value. 196 if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { 197 InsertedPHI->eraseFromParent(); 198 return ConstVal; 199 } 200 201 // If the client wants to know about all new instructions, tell it. 202 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 203 204 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 205 return InsertedPHI->getOperand(0).getReg(); 206 } 207 208 static 209 MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, 210 MachineOperand *U) { 211 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 212 if (&MI->getOperand(i) == U) 213 return MI->getOperand(i+1).getMBB(); 214 } 215 216 llvm_unreachable("MachineOperand::getParent() failure?"); 217 return 0; 218 } 219 220 /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 221 /// which use their value in the corresponding predecessor. 222 void MachineSSAUpdater::RewriteUse(MachineOperand &U) { 223 MachineInstr *UseMI = U.getParent(); 224 unsigned NewVR = 0; 225 if (UseMI->isPHI()) { 226 MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); 227 NewVR = GetValueAtEndOfBlockInternal(SourceBB); 228 } else { 229 NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); 230 } 231 232 U.setReg(NewVR); 233 } 234 235 void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) { 236 MRI->replaceRegWith(OldReg, NewReg); 237 238 AvailableValsTy &AvailableVals = getAvailableVals(AV); 239 for (DenseMap<MachineBasicBlock*, unsigned>::iterator 240 I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I) 241 if (I->second == OldReg) 242 I->second = NewReg; 243 } 244 245 /// MachinePHIiter - Iterator for PHI operands. This is used for the 246 /// PHI_iterator in the SSAUpdaterImpl template. 247 namespace { 248 class MachinePHIiter { 249 private: 250 MachineInstr *PHI; 251 unsigned idx; 252 253 public: 254 explicit MachinePHIiter(MachineInstr *P) // begin iterator 255 : PHI(P), idx(1) {} 256 MachinePHIiter(MachineInstr *P, bool) // end iterator 257 : PHI(P), idx(PHI->getNumOperands()) {} 258 259 MachinePHIiter &operator++() { idx += 2; return *this; } 260 bool operator==(const MachinePHIiter& x) const { return idx == x.idx; } 261 bool operator!=(const MachinePHIiter& x) const { return !operator==(x); } 262 unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } 263 MachineBasicBlock *getIncomingBlock() { 264 return PHI->getOperand(idx+1).getMBB(); 265 } 266 }; 267 } 268 269 /// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl 270 /// template, specialized for MachineSSAUpdater. 271 namespace llvm { 272 template<> 273 class SSAUpdaterTraits<MachineSSAUpdater> { 274 public: 275 typedef MachineBasicBlock BlkT; 276 typedef unsigned ValT; 277 typedef MachineInstr PhiT; 278 279 typedef MachineBasicBlock::succ_iterator BlkSucc_iterator; 280 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } 281 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } 282 283 typedef MachinePHIiter PHI_iterator; 284 static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 285 static inline PHI_iterator PHI_end(PhiT *PHI) { 286 return PHI_iterator(PHI, true); 287 } 288 289 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds 290 /// vector. 291 static void FindPredecessorBlocks(MachineBasicBlock *BB, 292 SmallVectorImpl<MachineBasicBlock*> *Preds){ 293 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 294 E = BB->pred_end(); PI != E; ++PI) 295 Preds->push_back(*PI); 296 } 297 298 /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. 299 /// Add it into the specified block and return the register. 300 static unsigned GetUndefVal(MachineBasicBlock *BB, 301 MachineSSAUpdater *Updater) { 302 // Insert an implicit_def to represent an undef value. 303 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 304 BB, BB->getFirstTerminator(), 305 Updater->VRC, Updater->MRI, 306 Updater->TII); 307 return NewDef->getOperand(0).getReg(); 308 } 309 310 /// CreateEmptyPHI - Create a PHI instruction that defines a new register. 311 /// Add it into the specified block and return the register. 312 static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, 313 MachineSSAUpdater *Updater) { 314 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front(); 315 MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, 316 Updater->VRC, Updater->MRI, 317 Updater->TII); 318 return PHI->getOperand(0).getReg(); 319 } 320 321 /// AddPHIOperand - Add the specified value as an operand of the PHI for 322 /// the specified predecessor block. 323 static void AddPHIOperand(MachineInstr *PHI, unsigned Val, 324 MachineBasicBlock *Pred) { 325 PHI->addOperand(MachineOperand::CreateReg(Val, false)); 326 PHI->addOperand(MachineOperand::CreateMBB(Pred)); 327 } 328 329 /// InstrIsPHI - Check if an instruction is a PHI. 330 /// 331 static MachineInstr *InstrIsPHI(MachineInstr *I) { 332 if (I && I->isPHI()) 333 return I; 334 return 0; 335 } 336 337 /// ValueIsPHI - Check if the instruction that defines the specified register 338 /// is a PHI instruction. 339 static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) { 340 return InstrIsPHI(Updater->MRI->getVRegDef(Val)); 341 } 342 343 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 344 /// operands, i.e., it was just added. 345 static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) { 346 MachineInstr *PHI = ValueIsPHI(Val, Updater); 347 if (PHI && PHI->getNumOperands() <= 1) 348 return PHI; 349 return 0; 350 } 351 352 /// GetPHIValue - For the specified PHI instruction, return the register 353 /// that it defines. 354 static unsigned GetPHIValue(MachineInstr *PHI) { 355 return PHI->getOperand(0).getReg(); 356 } 357 }; 358 359 } // End llvm namespace 360 361 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 362 /// for the specified BB and if so, return it. If not, construct SSA form by 363 /// first calculating the required placement of PHIs and then inserting new 364 /// PHIs where needed. 365 unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ 366 AvailableValsTy &AvailableVals = getAvailableVals(AV); 367 if (unsigned V = AvailableVals[BB]) 368 return V; 369 370 SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 371 return Impl.GetValue(BB); 372 } 373
