1200581Srdivacky//===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===// 2200581Srdivacky// 3200581Srdivacky// The LLVM Compiler Infrastructure 4200581Srdivacky// 5200581Srdivacky// This file is distributed under the University of Illinois Open Source 6200581Srdivacky// License. See LICENSE.TXT for details. 7200581Srdivacky// 8200581Srdivacky//===----------------------------------------------------------------------===// 9200581Srdivacky// 10200581Srdivacky// This file implements the MachineSSAUpdater class. It's based on SSAUpdater 11200581Srdivacky// class in lib/Transforms/Utils. 12200581Srdivacky// 13200581Srdivacky//===----------------------------------------------------------------------===// 14200581Srdivacky 15200581Srdivacky#include "llvm/CodeGen/MachineSSAUpdater.h" 16249423Sdim#include "llvm/ADT/DenseMap.h" 17249423Sdim#include "llvm/ADT/SmallVector.h" 18200581Srdivacky#include "llvm/CodeGen/MachineInstr.h" 19200581Srdivacky#include "llvm/CodeGen/MachineInstrBuilder.h" 20200581Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 21207618Srdivacky#include "llvm/Support/AlignOf.h" 22207618Srdivacky#include "llvm/Support/Allocator.h" 23200581Srdivacky#include "llvm/Support/Debug.h" 24200581Srdivacky#include "llvm/Support/ErrorHandling.h" 25200581Srdivacky#include "llvm/Support/raw_ostream.h" 26249423Sdim#include "llvm/Target/TargetInstrInfo.h" 27249423Sdim#include "llvm/Target/TargetMachine.h" 28249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 29208599Srdivacky#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 30200581Srdivackyusing namespace llvm; 31200581Srdivacky 32200581Srdivackytypedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy; 33200581Srdivackystatic AvailableValsTy &getAvailableVals(void *AV) { 34200581Srdivacky return *static_cast<AvailableValsTy*>(AV); 35200581Srdivacky} 36200581Srdivacky 37200581SrdivackyMachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, 38200581Srdivacky SmallVectorImpl<MachineInstr*> *NewPHI) 39208599Srdivacky : AV(0), InsertedPHIs(NewPHI) { 40200581Srdivacky TII = MF.getTarget().getInstrInfo(); 41200581Srdivacky MRI = &MF.getRegInfo(); 42200581Srdivacky} 43200581Srdivacky 44200581SrdivackyMachineSSAUpdater::~MachineSSAUpdater() { 45239462Sdim delete static_cast<AvailableValsTy*>(AV); 46200581Srdivacky} 47200581Srdivacky 48200581Srdivacky/// Initialize - Reset this object to get ready for a new set of SSA 49200581Srdivacky/// updates. ProtoValue is the value used to name PHI nodes. 50200581Srdivackyvoid MachineSSAUpdater::Initialize(unsigned V) { 51200581Srdivacky if (AV == 0) 52200581Srdivacky AV = new AvailableValsTy(); 53200581Srdivacky else 54200581Srdivacky getAvailableVals(AV).clear(); 55200581Srdivacky 56200581Srdivacky VR = V; 57200581Srdivacky VRC = MRI->getRegClass(VR); 58200581Srdivacky} 59200581Srdivacky 60200581Srdivacky/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for 61200581Srdivacky/// the specified block. 62200581Srdivackybool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const { 63200581Srdivacky return getAvailableVals(AV).count(BB); 64200581Srdivacky} 65200581Srdivacky 66200581Srdivacky/// AddAvailableValue - Indicate that a rewritten value is available in the 67200581Srdivacky/// specified block with the specified value. 68200581Srdivackyvoid MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) { 69200581Srdivacky getAvailableVals(AV)[BB] = V; 70200581Srdivacky} 71200581Srdivacky 72200581Srdivacky/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 73200581Srdivacky/// live at the end of the specified block. 74200581Srdivackyunsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { 75200581Srdivacky return GetValueAtEndOfBlockInternal(BB); 76200581Srdivacky} 77200581Srdivacky 78200581Srdivackystatic 79200581Srdivackyunsigned LookForIdenticalPHI(MachineBasicBlock *BB, 80263508Sdim SmallVectorImpl<std::pair<MachineBasicBlock*, unsigned> > &PredValues) { 81200581Srdivacky if (BB->empty()) 82200581Srdivacky return 0; 83200581Srdivacky 84234353Sdim MachineBasicBlock::iterator I = BB->begin(); 85203954Srdivacky if (!I->isPHI()) 86200581Srdivacky return 0; 87200581Srdivacky 88200581Srdivacky AvailableValsTy AVals; 89200581Srdivacky for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 90200581Srdivacky AVals[PredValues[i].first] = PredValues[i].second; 91203954Srdivacky while (I != BB->end() && I->isPHI()) { 92200581Srdivacky bool Same = true; 93200581Srdivacky for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) { 94200581Srdivacky unsigned SrcReg = I->getOperand(i).getReg(); 95200581Srdivacky MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB(); 96200581Srdivacky if (AVals[SrcBB] != SrcReg) { 97200581Srdivacky Same = false; 98200581Srdivacky break; 99200581Srdivacky } 100200581Srdivacky } 101200581Srdivacky if (Same) 102200581Srdivacky return I->getOperand(0).getReg(); 103200581Srdivacky ++I; 104200581Srdivacky } 105200581Srdivacky return 0; 106200581Srdivacky} 107200581Srdivacky 108200581Srdivacky/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define 109200581Srdivacky/// a value of the given register class at the start of the specified basic 110200581Srdivacky/// block. It returns the virtual register defined by the instruction. 111200581Srdivackystatic 112249423SdimMachineInstrBuilder InsertNewDef(unsigned Opcode, 113200581Srdivacky MachineBasicBlock *BB, MachineBasicBlock::iterator I, 114200581Srdivacky const TargetRegisterClass *RC, 115208599Srdivacky MachineRegisterInfo *MRI, 116208599Srdivacky const TargetInstrInfo *TII) { 117200581Srdivacky unsigned NewVR = MRI->createVirtualRegister(RC); 118206124Srdivacky return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR); 119200581Srdivacky} 120207618Srdivacky 121200581Srdivacky/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 122200581Srdivacky/// is live in the middle of the specified block. 123200581Srdivacky/// 124200581Srdivacky/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 125200581Srdivacky/// important case: if there is a definition of the rewritten value after the 126200581Srdivacky/// 'use' in BB. Consider code like this: 127200581Srdivacky/// 128200581Srdivacky/// X1 = ... 129200581Srdivacky/// SomeBB: 130200581Srdivacky/// use(X) 131200581Srdivacky/// X2 = ... 132200581Srdivacky/// br Cond, SomeBB, OutBB 133200581Srdivacky/// 134200581Srdivacky/// In this case, there are two values (X1 and X2) added to the AvailableVals 135200581Srdivacky/// set by the client of the rewriter, and those values are both live out of 136200581Srdivacky/// their respective blocks. However, the use of X happens in the *middle* of 137200581Srdivacky/// a block. Because of this, we need to insert a new PHI node in SomeBB to 138200581Srdivacky/// merge the appropriate values, and this value isn't live out of the block. 139200581Srdivacky/// 140200581Srdivackyunsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { 141200581Srdivacky // If there is no definition of the renamed variable in this block, just use 142200581Srdivacky // GetValueAtEndOfBlock to do our work. 143207618Srdivacky if (!HasValueForBlock(BB)) 144200581Srdivacky return GetValueAtEndOfBlockInternal(BB); 145200581Srdivacky 146200581Srdivacky // If there are no predecessors, just return undef. 147200581Srdivacky if (BB->pred_empty()) { 148200581Srdivacky // Insert an implicit_def to represent an undef value. 149203954Srdivacky MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 150200581Srdivacky BB, BB->getFirstTerminator(), 151200581Srdivacky VRC, MRI, TII); 152200581Srdivacky return NewDef->getOperand(0).getReg(); 153200581Srdivacky } 154200581Srdivacky 155200581Srdivacky // Otherwise, we have the hard case. Get the live-in values for each 156200581Srdivacky // predecessor. 157200581Srdivacky SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues; 158200581Srdivacky unsigned SingularValue = 0; 159200581Srdivacky 160200581Srdivacky bool isFirstPred = true; 161200581Srdivacky for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 162200581Srdivacky E = BB->pred_end(); PI != E; ++PI) { 163200581Srdivacky MachineBasicBlock *PredBB = *PI; 164200581Srdivacky unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB); 165200581Srdivacky PredValues.push_back(std::make_pair(PredBB, PredVal)); 166200581Srdivacky 167200581Srdivacky // Compute SingularValue. 168200581Srdivacky if (isFirstPred) { 169200581Srdivacky SingularValue = PredVal; 170200581Srdivacky isFirstPred = false; 171200581Srdivacky } else if (PredVal != SingularValue) 172200581Srdivacky SingularValue = 0; 173200581Srdivacky } 174200581Srdivacky 175200581Srdivacky // Otherwise, if all the merged values are the same, just use it. 176200581Srdivacky if (SingularValue != 0) 177200581Srdivacky return SingularValue; 178200581Srdivacky 179200581Srdivacky // If an identical PHI is already in BB, just reuse it. 180200581Srdivacky unsigned DupPHI = LookForIdenticalPHI(BB, PredValues); 181200581Srdivacky if (DupPHI) 182200581Srdivacky return DupPHI; 183200581Srdivacky 184200581Srdivacky // Otherwise, we do need a PHI: insert one now. 185234353Sdim MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); 186249423Sdim MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, 187249423Sdim Loc, VRC, MRI, TII); 188200581Srdivacky 189200581Srdivacky // Fill in all the predecessors of the PHI. 190200581Srdivacky for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 191249423Sdim InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first); 192200581Srdivacky 193200581Srdivacky // See if the PHI node can be merged to a single value. This can happen in 194200581Srdivacky // loop cases when we get a PHI of itself and one other value. 195200581Srdivacky if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { 196200581Srdivacky InsertedPHI->eraseFromParent(); 197200581Srdivacky return ConstVal; 198200581Srdivacky } 199200581Srdivacky 200200581Srdivacky // If the client wants to know about all new instructions, tell it. 201200581Srdivacky if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 202200581Srdivacky 203202375Srdivacky DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 204200581Srdivacky return InsertedPHI->getOperand(0).getReg(); 205200581Srdivacky} 206200581Srdivacky 207200581Srdivackystatic 208200581SrdivackyMachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, 209200581Srdivacky MachineOperand *U) { 210200581Srdivacky for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 211200581Srdivacky if (&MI->getOperand(i) == U) 212200581Srdivacky return MI->getOperand(i+1).getMBB(); 213200581Srdivacky } 214200581Srdivacky 215200581Srdivacky llvm_unreachable("MachineOperand::getParent() failure?"); 216200581Srdivacky} 217200581Srdivacky 218200581Srdivacky/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 219200581Srdivacky/// which use their value in the corresponding predecessor. 220200581Srdivackyvoid MachineSSAUpdater::RewriteUse(MachineOperand &U) { 221200581Srdivacky MachineInstr *UseMI = U.getParent(); 222200581Srdivacky unsigned NewVR = 0; 223203954Srdivacky if (UseMI->isPHI()) { 224200581Srdivacky MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); 225200581Srdivacky NewVR = GetValueAtEndOfBlockInternal(SourceBB); 226200581Srdivacky } else { 227200581Srdivacky NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); 228200581Srdivacky } 229200581Srdivacky 230200581Srdivacky U.setReg(NewVR); 231200581Srdivacky} 232200581Srdivacky 233200581Srdivackyvoid MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) { 234200581Srdivacky MRI->replaceRegWith(OldReg, NewReg); 235200581Srdivacky 236200581Srdivacky AvailableValsTy &AvailableVals = getAvailableVals(AV); 237200581Srdivacky for (DenseMap<MachineBasicBlock*, unsigned>::iterator 238200581Srdivacky I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I) 239200581Srdivacky if (I->second == OldReg) 240200581Srdivacky I->second = NewReg; 241200581Srdivacky} 242200581Srdivacky 243208599Srdivacky/// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl 244208599Srdivacky/// template, specialized for MachineSSAUpdater. 245208599Srdivackynamespace llvm { 246208599Srdivackytemplate<> 247208599Srdivackyclass SSAUpdaterTraits<MachineSSAUpdater> { 248208599Srdivackypublic: 249208599Srdivacky typedef MachineBasicBlock BlkT; 250208599Srdivacky typedef unsigned ValT; 251208599Srdivacky typedef MachineInstr PhiT; 252200581Srdivacky 253208599Srdivacky typedef MachineBasicBlock::succ_iterator BlkSucc_iterator; 254208599Srdivacky static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } 255208599Srdivacky static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } 256207618Srdivacky 257239462Sdim /// Iterator for PHI operands. 258239462Sdim class PHI_iterator { 259239462Sdim private: 260239462Sdim MachineInstr *PHI; 261239462Sdim unsigned idx; 262239462Sdim 263239462Sdim public: 264239462Sdim explicit PHI_iterator(MachineInstr *P) // begin iterator 265239462Sdim : PHI(P), idx(1) {} 266239462Sdim PHI_iterator(MachineInstr *P, bool) // end iterator 267239462Sdim : PHI(P), idx(PHI->getNumOperands()) {} 268239462Sdim 269239462Sdim PHI_iterator &operator++() { idx += 2; return *this; } 270239462Sdim bool operator==(const PHI_iterator& x) const { return idx == x.idx; } 271239462Sdim bool operator!=(const PHI_iterator& x) const { return !operator==(x); } 272239462Sdim unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } 273239462Sdim MachineBasicBlock *getIncomingBlock() { 274239462Sdim return PHI->getOperand(idx+1).getMBB(); 275239462Sdim } 276239462Sdim }; 277208599Srdivacky static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 278208599Srdivacky static inline PHI_iterator PHI_end(PhiT *PHI) { 279208599Srdivacky return PHI_iterator(PHI, true); 280208599Srdivacky } 281207618Srdivacky 282208599Srdivacky /// FindPredecessorBlocks - Put the predecessors of BB into the Preds 283208599Srdivacky /// vector. 284208599Srdivacky static void FindPredecessorBlocks(MachineBasicBlock *BB, 285208599Srdivacky SmallVectorImpl<MachineBasicBlock*> *Preds){ 286208599Srdivacky for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 287208599Srdivacky E = BB->pred_end(); PI != E; ++PI) 288208599Srdivacky Preds->push_back(*PI); 289200581Srdivacky } 290200581Srdivacky 291208599Srdivacky /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. 292208599Srdivacky /// Add it into the specified block and return the register. 293208599Srdivacky static unsigned GetUndefVal(MachineBasicBlock *BB, 294208599Srdivacky MachineSSAUpdater *Updater) { 295208599Srdivacky // Insert an implicit_def to represent an undef value. 296208599Srdivacky MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 297208599Srdivacky BB, BB->getFirstTerminator(), 298208599Srdivacky Updater->VRC, Updater->MRI, 299208599Srdivacky Updater->TII); 300208599Srdivacky return NewDef->getOperand(0).getReg(); 301207618Srdivacky } 302207618Srdivacky 303208599Srdivacky /// CreateEmptyPHI - Create a PHI instruction that defines a new register. 304208599Srdivacky /// Add it into the specified block and return the register. 305208599Srdivacky static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, 306208599Srdivacky MachineSSAUpdater *Updater) { 307234353Sdim MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); 308208599Srdivacky MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, 309208599Srdivacky Updater->VRC, Updater->MRI, 310208599Srdivacky Updater->TII); 311208599Srdivacky return PHI->getOperand(0).getReg(); 312200581Srdivacky } 313200581Srdivacky 314208599Srdivacky /// AddPHIOperand - Add the specified value as an operand of the PHI for 315208599Srdivacky /// the specified predecessor block. 316208599Srdivacky static void AddPHIOperand(MachineInstr *PHI, unsigned Val, 317208599Srdivacky MachineBasicBlock *Pred) { 318249423Sdim MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(Pred); 319207618Srdivacky } 320200581Srdivacky 321208599Srdivacky /// InstrIsPHI - Check if an instruction is a PHI. 322208599Srdivacky /// 323208599Srdivacky static MachineInstr *InstrIsPHI(MachineInstr *I) { 324208599Srdivacky if (I && I->isPHI()) 325208599Srdivacky return I; 326208599Srdivacky return 0; 327200581Srdivacky } 328200581Srdivacky 329208599Srdivacky /// ValueIsPHI - Check if the instruction that defines the specified register 330208599Srdivacky /// is a PHI instruction. 331208599Srdivacky static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) { 332208599Srdivacky return InstrIsPHI(Updater->MRI->getVRegDef(Val)); 333207618Srdivacky } 334207618Srdivacky 335208599Srdivacky /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 336208599Srdivacky /// operands, i.e., it was just added. 337208599Srdivacky static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) { 338208599Srdivacky MachineInstr *PHI = ValueIsPHI(Val, Updater); 339208599Srdivacky if (PHI && PHI->getNumOperands() <= 1) 340208599Srdivacky return PHI; 341208599Srdivacky return 0; 342200581Srdivacky } 343200581Srdivacky 344208599Srdivacky /// GetPHIValue - For the specified PHI instruction, return the register 345208599Srdivacky /// that it defines. 346208599Srdivacky static unsigned GetPHIValue(MachineInstr *PHI) { 347208599Srdivacky return PHI->getOperand(0).getReg(); 348207618Srdivacky } 349208599Srdivacky}; 350207618Srdivacky 351208599Srdivacky} // End llvm namespace 352207618Srdivacky 353208599Srdivacky/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 354208599Srdivacky/// for the specified BB and if so, return it. If not, construct SSA form by 355208599Srdivacky/// first calculating the required placement of PHIs and then inserting new 356208599Srdivacky/// PHIs where needed. 357208599Srdivackyunsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ 358207618Srdivacky AvailableValsTy &AvailableVals = getAvailableVals(AV); 359208599Srdivacky if (unsigned V = AvailableVals[BB]) 360208599Srdivacky return V; 361207618Srdivacky 362208599Srdivacky SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 363208599Srdivacky return Impl.GetValue(BB); 364207618Srdivacky} 365