1200581Srdivacky//===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===// 2200581Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6200581Srdivacky// 7200581Srdivacky//===----------------------------------------------------------------------===// 8200581Srdivacky// 9200581Srdivacky// This file implements the MachineSSAUpdater class. It's based on SSAUpdater 10200581Srdivacky// class in lib/Transforms/Utils. 11200581Srdivacky// 12200581Srdivacky//===----------------------------------------------------------------------===// 13200581Srdivacky 14200581Srdivacky#include "llvm/CodeGen/MachineSSAUpdater.h" 15249423Sdim#include "llvm/ADT/DenseMap.h" 16249423Sdim#include "llvm/ADT/SmallVector.h" 17327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 18327952Sdim#include "llvm/CodeGen/MachineFunction.h" 19200581Srdivacky#include "llvm/CodeGen/MachineInstr.h" 20200581Srdivacky#include "llvm/CodeGen/MachineInstrBuilder.h" 21327952Sdim#include "llvm/CodeGen/MachineOperand.h" 22200581Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 23327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 24327952Sdim#include "llvm/CodeGen/TargetOpcodes.h" 25327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 26327952Sdim#include "llvm/IR/DebugLoc.h" 27200581Srdivacky#include "llvm/Support/Debug.h" 28200581Srdivacky#include "llvm/Support/ErrorHandling.h" 29200581Srdivacky#include "llvm/Support/raw_ostream.h" 30208599Srdivacky#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 31327952Sdim#include <utility> 32327952Sdim 33200581Srdivackyusing namespace llvm; 34200581Srdivacky 35276479Sdim#define DEBUG_TYPE "machine-ssaupdater" 36276479Sdim 37327952Sdimusing AvailableValsTy = DenseMap<MachineBasicBlock *, unsigned>; 38327952Sdim 39200581Srdivackystatic AvailableValsTy &getAvailableVals(void *AV) { 40200581Srdivacky return *static_cast<AvailableValsTy*>(AV); 41200581Srdivacky} 42200581Srdivacky 43200581SrdivackyMachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, 44200581Srdivacky SmallVectorImpl<MachineInstr*> *NewPHI) 45327952Sdim : InsertedPHIs(NewPHI), TII(MF.getSubtarget().getInstrInfo()), 46327952Sdim MRI(&MF.getRegInfo()) {} 47200581Srdivacky 48200581SrdivackyMachineSSAUpdater::~MachineSSAUpdater() { 49239462Sdim delete static_cast<AvailableValsTy*>(AV); 50200581Srdivacky} 51200581Srdivacky 52200581Srdivacky/// Initialize - Reset this object to get ready for a new set of SSA 53200581Srdivacky/// updates. ProtoValue is the value used to name PHI nodes. 54200581Srdivackyvoid MachineSSAUpdater::Initialize(unsigned V) { 55276479Sdim if (!AV) 56200581Srdivacky AV = new AvailableValsTy(); 57200581Srdivacky else 58200581Srdivacky getAvailableVals(AV).clear(); 59200581Srdivacky 60200581Srdivacky VR = V; 61200581Srdivacky VRC = MRI->getRegClass(VR); 62200581Srdivacky} 63200581Srdivacky 64200581Srdivacky/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for 65200581Srdivacky/// the specified block. 66200581Srdivackybool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const { 67200581Srdivacky return getAvailableVals(AV).count(BB); 68200581Srdivacky} 69200581Srdivacky 70200581Srdivacky/// AddAvailableValue - Indicate that a rewritten value is available in the 71200581Srdivacky/// specified block with the specified value. 72200581Srdivackyvoid MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) { 73200581Srdivacky getAvailableVals(AV)[BB] = V; 74200581Srdivacky} 75200581Srdivacky 76200581Srdivacky/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 77200581Srdivacky/// live at the end of the specified block. 78200581Srdivackyunsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { 79200581Srdivacky return GetValueAtEndOfBlockInternal(BB); 80200581Srdivacky} 81200581Srdivacky 82200581Srdivackystatic 83200581Srdivackyunsigned LookForIdenticalPHI(MachineBasicBlock *BB, 84327952Sdim SmallVectorImpl<std::pair<MachineBasicBlock *, unsigned>> &PredValues) { 85200581Srdivacky if (BB->empty()) 86200581Srdivacky return 0; 87200581Srdivacky 88234353Sdim MachineBasicBlock::iterator I = BB->begin(); 89203954Srdivacky if (!I->isPHI()) 90200581Srdivacky return 0; 91200581Srdivacky 92200581Srdivacky AvailableValsTy AVals; 93200581Srdivacky for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 94200581Srdivacky AVals[PredValues[i].first] = PredValues[i].second; 95203954Srdivacky while (I != BB->end() && I->isPHI()) { 96200581Srdivacky bool Same = true; 97200581Srdivacky for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) { 98360784Sdim Register SrcReg = I->getOperand(i).getReg(); 99200581Srdivacky MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB(); 100200581Srdivacky if (AVals[SrcBB] != SrcReg) { 101200581Srdivacky Same = false; 102200581Srdivacky break; 103200581Srdivacky } 104200581Srdivacky } 105200581Srdivacky if (Same) 106200581Srdivacky return I->getOperand(0).getReg(); 107200581Srdivacky ++I; 108200581Srdivacky } 109200581Srdivacky return 0; 110200581Srdivacky} 111200581Srdivacky 112200581Srdivacky/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define 113200581Srdivacky/// a value of the given register class at the start of the specified basic 114200581Srdivacky/// block. It returns the virtual register defined by the instruction. 115200581Srdivackystatic 116249423SdimMachineInstrBuilder InsertNewDef(unsigned Opcode, 117200581Srdivacky MachineBasicBlock *BB, MachineBasicBlock::iterator I, 118200581Srdivacky const TargetRegisterClass *RC, 119208599Srdivacky MachineRegisterInfo *MRI, 120208599Srdivacky const TargetInstrInfo *TII) { 121360784Sdim Register NewVR = MRI->createVirtualRegister(RC); 122206124Srdivacky return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR); 123200581Srdivacky} 124207618Srdivacky 125200581Srdivacky/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 126200581Srdivacky/// is live in the middle of the specified block. 127200581Srdivacky/// 128200581Srdivacky/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 129200581Srdivacky/// important case: if there is a definition of the rewritten value after the 130200581Srdivacky/// 'use' in BB. Consider code like this: 131200581Srdivacky/// 132200581Srdivacky/// X1 = ... 133200581Srdivacky/// SomeBB: 134200581Srdivacky/// use(X) 135200581Srdivacky/// X2 = ... 136200581Srdivacky/// br Cond, SomeBB, OutBB 137200581Srdivacky/// 138200581Srdivacky/// In this case, there are two values (X1 and X2) added to the AvailableVals 139200581Srdivacky/// set by the client of the rewriter, and those values are both live out of 140200581Srdivacky/// their respective blocks. However, the use of X happens in the *middle* of 141200581Srdivacky/// a block. Because of this, we need to insert a new PHI node in SomeBB to 142200581Srdivacky/// merge the appropriate values, and this value isn't live out of the block. 143200581Srdivackyunsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { 144200581Srdivacky // If there is no definition of the renamed variable in this block, just use 145200581Srdivacky // GetValueAtEndOfBlock to do our work. 146207618Srdivacky if (!HasValueForBlock(BB)) 147200581Srdivacky return GetValueAtEndOfBlockInternal(BB); 148200581Srdivacky 149200581Srdivacky // If there are no predecessors, just return undef. 150200581Srdivacky if (BB->pred_empty()) { 151200581Srdivacky // Insert an implicit_def to represent an undef value. 152203954Srdivacky MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 153200581Srdivacky BB, BB->getFirstTerminator(), 154200581Srdivacky VRC, MRI, TII); 155200581Srdivacky return NewDef->getOperand(0).getReg(); 156200581Srdivacky } 157200581Srdivacky 158200581Srdivacky // Otherwise, we have the hard case. Get the live-in values for each 159200581Srdivacky // predecessor. 160200581Srdivacky SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues; 161200581Srdivacky unsigned SingularValue = 0; 162200581Srdivacky 163200581Srdivacky bool isFirstPred = true; 164200581Srdivacky for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 165200581Srdivacky E = BB->pred_end(); PI != E; ++PI) { 166200581Srdivacky MachineBasicBlock *PredBB = *PI; 167200581Srdivacky unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB); 168200581Srdivacky PredValues.push_back(std::make_pair(PredBB, PredVal)); 169200581Srdivacky 170200581Srdivacky // Compute SingularValue. 171200581Srdivacky if (isFirstPred) { 172200581Srdivacky SingularValue = PredVal; 173200581Srdivacky isFirstPred = false; 174200581Srdivacky } else if (PredVal != SingularValue) 175200581Srdivacky SingularValue = 0; 176200581Srdivacky } 177200581Srdivacky 178200581Srdivacky // Otherwise, if all the merged values are the same, just use it. 179200581Srdivacky if (SingularValue != 0) 180200581Srdivacky return SingularValue; 181200581Srdivacky 182200581Srdivacky // If an identical PHI is already in BB, just reuse it. 183200581Srdivacky unsigned DupPHI = LookForIdenticalPHI(BB, PredValues); 184200581Srdivacky if (DupPHI) 185200581Srdivacky return DupPHI; 186200581Srdivacky 187200581Srdivacky // Otherwise, we do need a PHI: insert one now. 188234353Sdim MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); 189249423Sdim MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, 190249423Sdim Loc, VRC, MRI, TII); 191200581Srdivacky 192200581Srdivacky // Fill in all the predecessors of the PHI. 193200581Srdivacky for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 194249423Sdim InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first); 195200581Srdivacky 196200581Srdivacky // See if the PHI node can be merged to a single value. This can happen in 197200581Srdivacky // loop cases when we get a PHI of itself and one other value. 198200581Srdivacky if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { 199200581Srdivacky InsertedPHI->eraseFromParent(); 200200581Srdivacky return ConstVal; 201200581Srdivacky } 202200581Srdivacky 203200581Srdivacky // If the client wants to know about all new instructions, tell it. 204200581Srdivacky if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 205200581Srdivacky 206341825Sdim LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 207200581Srdivacky return InsertedPHI->getOperand(0).getReg(); 208200581Srdivacky} 209200581Srdivacky 210200581Srdivackystatic 211200581SrdivackyMachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, 212200581Srdivacky MachineOperand *U) { 213200581Srdivacky for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 214200581Srdivacky if (&MI->getOperand(i) == U) 215200581Srdivacky return MI->getOperand(i+1).getMBB(); 216200581Srdivacky } 217200581Srdivacky 218200581Srdivacky llvm_unreachable("MachineOperand::getParent() failure?"); 219200581Srdivacky} 220200581Srdivacky 221200581Srdivacky/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 222200581Srdivacky/// which use their value in the corresponding predecessor. 223200581Srdivackyvoid MachineSSAUpdater::RewriteUse(MachineOperand &U) { 224200581Srdivacky MachineInstr *UseMI = U.getParent(); 225200581Srdivacky unsigned NewVR = 0; 226203954Srdivacky if (UseMI->isPHI()) { 227200581Srdivacky MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); 228200581Srdivacky NewVR = GetValueAtEndOfBlockInternal(SourceBB); 229200581Srdivacky } else { 230200581Srdivacky NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); 231200581Srdivacky } 232200581Srdivacky 233200581Srdivacky U.setReg(NewVR); 234200581Srdivacky} 235200581Srdivacky 236208599Srdivacky/// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl 237208599Srdivacky/// template, specialized for MachineSSAUpdater. 238208599Srdivackynamespace llvm { 239327952Sdim 240208599Srdivackytemplate<> 241208599Srdivackyclass SSAUpdaterTraits<MachineSSAUpdater> { 242208599Srdivackypublic: 243327952Sdim using BlkT = MachineBasicBlock; 244327952Sdim using ValT = unsigned; 245327952Sdim using PhiT = MachineInstr; 246327952Sdim using BlkSucc_iterator = MachineBasicBlock::succ_iterator; 247200581Srdivacky 248208599Srdivacky static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } 249208599Srdivacky static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } 250207618Srdivacky 251239462Sdim /// Iterator for PHI operands. 252239462Sdim class PHI_iterator { 253239462Sdim private: 254239462Sdim MachineInstr *PHI; 255239462Sdim unsigned idx; 256341825Sdim 257239462Sdim public: 258239462Sdim explicit PHI_iterator(MachineInstr *P) // begin iterator 259239462Sdim : PHI(P), idx(1) {} 260239462Sdim PHI_iterator(MachineInstr *P, bool) // end iterator 261239462Sdim : PHI(P), idx(PHI->getNumOperands()) {} 262239462Sdim 263341825Sdim PHI_iterator &operator++() { idx += 2; return *this; } 264239462Sdim bool operator==(const PHI_iterator& x) const { return idx == x.idx; } 265239462Sdim bool operator!=(const PHI_iterator& x) const { return !operator==(x); } 266327952Sdim 267239462Sdim unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } 268327952Sdim 269239462Sdim MachineBasicBlock *getIncomingBlock() { 270239462Sdim return PHI->getOperand(idx+1).getMBB(); 271239462Sdim } 272239462Sdim }; 273327952Sdim 274208599Srdivacky static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 275327952Sdim 276208599Srdivacky static inline PHI_iterator PHI_end(PhiT *PHI) { 277208599Srdivacky return PHI_iterator(PHI, true); 278208599Srdivacky } 279207618Srdivacky 280208599Srdivacky /// FindPredecessorBlocks - Put the predecessors of BB into the Preds 281208599Srdivacky /// vector. 282208599Srdivacky static void FindPredecessorBlocks(MachineBasicBlock *BB, 283208599Srdivacky SmallVectorImpl<MachineBasicBlock*> *Preds){ 284208599Srdivacky for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 285208599Srdivacky E = BB->pred_end(); PI != E; ++PI) 286208599Srdivacky Preds->push_back(*PI); 287200581Srdivacky } 288200581Srdivacky 289208599Srdivacky /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. 290208599Srdivacky /// Add it into the specified block and return the register. 291208599Srdivacky static unsigned GetUndefVal(MachineBasicBlock *BB, 292208599Srdivacky MachineSSAUpdater *Updater) { 293208599Srdivacky // Insert an implicit_def to represent an undef value. 294208599Srdivacky MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 295360784Sdim BB, BB->getFirstNonPHI(), 296208599Srdivacky Updater->VRC, Updater->MRI, 297208599Srdivacky Updater->TII); 298208599Srdivacky return NewDef->getOperand(0).getReg(); 299207618Srdivacky } 300207618Srdivacky 301208599Srdivacky /// CreateEmptyPHI - Create a PHI instruction that defines a new register. 302208599Srdivacky /// Add it into the specified block and return the register. 303208599Srdivacky static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, 304208599Srdivacky MachineSSAUpdater *Updater) { 305234353Sdim MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); 306208599Srdivacky MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, 307208599Srdivacky Updater->VRC, Updater->MRI, 308208599Srdivacky Updater->TII); 309208599Srdivacky return PHI->getOperand(0).getReg(); 310200581Srdivacky } 311200581Srdivacky 312208599Srdivacky /// AddPHIOperand - Add the specified value as an operand of the PHI for 313208599Srdivacky /// the specified predecessor block. 314208599Srdivacky static void AddPHIOperand(MachineInstr *PHI, unsigned Val, 315208599Srdivacky MachineBasicBlock *Pred) { 316249423Sdim MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(Pred); 317207618Srdivacky } 318200581Srdivacky 319208599Srdivacky /// InstrIsPHI - Check if an instruction is a PHI. 320208599Srdivacky static MachineInstr *InstrIsPHI(MachineInstr *I) { 321208599Srdivacky if (I && I->isPHI()) 322208599Srdivacky return I; 323276479Sdim return nullptr; 324200581Srdivacky } 325200581Srdivacky 326208599Srdivacky /// ValueIsPHI - Check if the instruction that defines the specified register 327208599Srdivacky /// is a PHI instruction. 328208599Srdivacky static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) { 329208599Srdivacky return InstrIsPHI(Updater->MRI->getVRegDef(Val)); 330207618Srdivacky } 331207618Srdivacky 332208599Srdivacky /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 333208599Srdivacky /// operands, i.e., it was just added. 334208599Srdivacky static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) { 335208599Srdivacky MachineInstr *PHI = ValueIsPHI(Val, Updater); 336208599Srdivacky if (PHI && PHI->getNumOperands() <= 1) 337208599Srdivacky return PHI; 338276479Sdim return nullptr; 339200581Srdivacky } 340200581Srdivacky 341208599Srdivacky /// GetPHIValue - For the specified PHI instruction, return the register 342208599Srdivacky /// that it defines. 343208599Srdivacky static unsigned GetPHIValue(MachineInstr *PHI) { 344208599Srdivacky return PHI->getOperand(0).getReg(); 345207618Srdivacky } 346208599Srdivacky}; 347207618Srdivacky 348327952Sdim} // end namespace llvm 349207618Srdivacky 350208599Srdivacky/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 351208599Srdivacky/// for the specified BB and if so, return it. If not, construct SSA form by 352208599Srdivacky/// first calculating the required placement of PHIs and then inserting new 353208599Srdivacky/// PHIs where needed. 354208599Srdivackyunsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ 355207618Srdivacky AvailableValsTy &AvailableVals = getAvailableVals(AV); 356208599Srdivacky if (unsigned V = AvailableVals[BB]) 357208599Srdivacky return V; 358207618Srdivacky 359208599Srdivacky SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 360208599Srdivacky return Impl.GetValue(BB); 361207618Srdivacky} 362