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