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