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" 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->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. 111static 112MachineInstr *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->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 208static 209MachineBasicBlock *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. 222void 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 235void 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. 247namespace { 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. 271namespace llvm { 272template<> 273class SSAUpdaterTraits<MachineSSAUpdater> { 274public: 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. 365unsigned 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