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