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" 30using namespace llvm; 31 32typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy; 33static AvailableValsTy &getAvailableVals(void *AV) { 34 return *static_cast<AvailableValsTy*>(AV); 35} 36 37MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, 38 SmallVectorImpl<MachineInstr*> *NewPHI) 39 : AV(0), InsertedPHIs(NewPHI) { 40 TII = MF.getTarget().getInstrInfo(); 41 MRI = &MF.getRegInfo(); 42} 43 44MachineSSAUpdater::~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. 50void 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. 62bool 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. 68void 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. 74unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { 75 return GetValueAtEndOfBlockInternal(BB); 76} 77 78static 79unsigned LookForIdenticalPHI(MachineBasicBlock *BB, 80 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) { 81 if (BB->empty()) 82 return 0; 83 84 MachineBasicBlock::iterator I = BB->begin(); 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. 111static 112MachineInstrBuilder 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/// 140unsigned 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->begin(); 186 MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, 187 Loc, VRC, MRI, TII); 188 189 // Fill in all the predecessors of the PHI. 190 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 191 InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first); 192 193 // See if the PHI node can be merged to a single value. This can happen in 194 // loop cases when we get a PHI of itself and one other value. 195 if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { 196 InsertedPHI->eraseFromParent(); 197 return ConstVal; 198 } 199 200 // If the client wants to know about all new instructions, tell it. 201 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 202 203 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 204 return InsertedPHI->getOperand(0).getReg(); 205} 206 207static 208MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, 209 MachineOperand *U) { 210 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 211 if (&MI->getOperand(i) == U) 212 return MI->getOperand(i+1).getMBB(); 213 } 214 215 llvm_unreachable("MachineOperand::getParent() failure?"); 216} 217 218/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 219/// which use their value in the corresponding predecessor. 220void MachineSSAUpdater::RewriteUse(MachineOperand &U) { 221 MachineInstr *UseMI = U.getParent(); 222 unsigned NewVR = 0; 223 if (UseMI->isPHI()) { 224 MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); 225 NewVR = GetValueAtEndOfBlockInternal(SourceBB); 226 } else { 227 NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); 228 } 229 230 U.setReg(NewVR); 231} 232 233void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) { 234 MRI->replaceRegWith(OldReg, NewReg); 235 236 AvailableValsTy &AvailableVals = getAvailableVals(AV); 237 for (DenseMap<MachineBasicBlock*, unsigned>::iterator 238 I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I) 239 if (I->second == OldReg) 240 I->second = NewReg; 241} 242 243/// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl 244/// template, specialized for MachineSSAUpdater. 245namespace llvm { 246template<> 247class SSAUpdaterTraits<MachineSSAUpdater> { 248public: 249 typedef MachineBasicBlock BlkT; 250 typedef unsigned ValT; 251 typedef MachineInstr PhiT; 252 253 typedef MachineBasicBlock::succ_iterator BlkSucc_iterator; 254 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } 255 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } 256 257 /// Iterator for PHI operands. 258 class PHI_iterator { 259 private: 260 MachineInstr *PHI; 261 unsigned idx; 262 263 public: 264 explicit PHI_iterator(MachineInstr *P) // begin iterator 265 : PHI(P), idx(1) {} 266 PHI_iterator(MachineInstr *P, bool) // end iterator 267 : PHI(P), idx(PHI->getNumOperands()) {} 268 269 PHI_iterator &operator++() { idx += 2; return *this; } 270 bool operator==(const PHI_iterator& x) const { return idx == x.idx; } 271 bool operator!=(const PHI_iterator& x) const { return !operator==(x); } 272 unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } 273 MachineBasicBlock *getIncomingBlock() { 274 return PHI->getOperand(idx+1).getMBB(); 275 } 276 }; 277 static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 278 static inline PHI_iterator PHI_end(PhiT *PHI) { 279 return PHI_iterator(PHI, true); 280 } 281 282 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds 283 /// vector. 284 static void FindPredecessorBlocks(MachineBasicBlock *BB, 285 SmallVectorImpl<MachineBasicBlock*> *Preds){ 286 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 287 E = BB->pred_end(); PI != E; ++PI) 288 Preds->push_back(*PI); 289 } 290 291 /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. 292 /// Add it into the specified block and return the register. 293 static unsigned GetUndefVal(MachineBasicBlock *BB, 294 MachineSSAUpdater *Updater) { 295 // Insert an implicit_def to represent an undef value. 296 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 297 BB, BB->getFirstTerminator(), 298 Updater->VRC, Updater->MRI, 299 Updater->TII); 300 return NewDef->getOperand(0).getReg(); 301 } 302 303 /// CreateEmptyPHI - Create a PHI instruction that defines a new register. 304 /// Add it into the specified block and return the register. 305 static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, 306 MachineSSAUpdater *Updater) { 307 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); 308 MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, 309 Updater->VRC, Updater->MRI, 310 Updater->TII); 311 return PHI->getOperand(0).getReg(); 312 } 313 314 /// AddPHIOperand - Add the specified value as an operand of the PHI for 315 /// the specified predecessor block. 316 static void AddPHIOperand(MachineInstr *PHI, unsigned Val, 317 MachineBasicBlock *Pred) { 318 MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(Pred); 319 } 320 321 /// InstrIsPHI - Check if an instruction is a PHI. 322 /// 323 static MachineInstr *InstrIsPHI(MachineInstr *I) { 324 if (I && I->isPHI()) 325 return I; 326 return 0; 327 } 328 329 /// ValueIsPHI - Check if the instruction that defines the specified register 330 /// is a PHI instruction. 331 static MachineInstr *ValueIsPHI(unsigned 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(unsigned Val, MachineSSAUpdater *Updater) { 338 MachineInstr *PHI = ValueIsPHI(Val, Updater); 339 if (PHI && PHI->getNumOperands() <= 1) 340 return PHI; 341 return 0; 342 } 343 344 /// GetPHIValue - For the specified PHI instruction, return the register 345 /// that it defines. 346 static unsigned GetPHIValue(MachineInstr *PHI) { 347 return PHI->getOperand(0).getReg(); 348 } 349}; 350 351} // End llvm namespace 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. 357unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ 358 AvailableValsTy &AvailableVals = getAvailableVals(AV); 359 if (unsigned V = AvailableVals[BB]) 360 return V; 361 362 SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 363 return Impl.GetValue(BB); 364} 365