384 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the MachineSSAUpdater class. It's based on SSAUpdater10// 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 33using namespace llvm;34 35#define DEBUG_TYPE "machine-ssaupdater"36 37using AvailableValsTy = DenseMap<MachineBasicBlock *, Register>;38 39static AvailableValsTy &getAvailableVals(void *AV) {40 return *static_cast<AvailableValsTy*>(AV);41}42 43MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,44 SmallVectorImpl<MachineInstr*> *NewPHI)45 : InsertedPHIs(NewPHI), TII(MF.getSubtarget().getInstrInfo()),46 MRI(&MF.getRegInfo()) {}47 48MachineSSAUpdater::~MachineSSAUpdater() {49 delete static_cast<AvailableValsTy*>(AV);50}51 52/// Initialize - Reset this object to get ready for a new set of SSA53/// updates.54void MachineSSAUpdater::Initialize(Register V) {55 if (!AV)56 AV = new AvailableValsTy();57 else58 getAvailableVals(AV).clear();59 60 RegAttrs = MRI->getVRegAttrs(V);61}62 63/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for64/// the specified block.65bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {66 return getAvailableVals(AV).count(BB);67}68 69/// AddAvailableValue - Indicate that a rewritten value is available in the70/// specified block with the specified value.71void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, Register V) {72 getAvailableVals(AV)[BB] = V;73}74 75/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is76/// live at the end of the specified block.77Register MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {78 return GetValueAtEndOfBlockInternal(BB);79}80 81static82Register LookForIdenticalPHI(MachineBasicBlock *BB,83 SmallVectorImpl<std::pair<MachineBasicBlock *, Register>> &PredValues) {84 if (BB->empty())85 return Register();86 87 MachineBasicBlock::iterator I = BB->begin();88 if (!I->isPHI())89 return Register();90 91 AvailableValsTy AVals;92 for (const auto &[SrcBB, SrcReg] : PredValues)93 AVals[SrcBB] = SrcReg;94 while (I != BB->end() && I->isPHI()) {95 bool Same = true;96 for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) {97 Register SrcReg = I->getOperand(i).getReg();98 MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();99 if (AVals[SrcBB] != SrcReg) {100 Same = false;101 break;102 }103 }104 if (Same)105 return I->getOperand(0).getReg();106 ++I;107 }108 return Register();109}110 111/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define112/// a value of the given register class at the start of the specified basic113/// block. It returns the virtual register defined by the instruction.114static MachineInstrBuilder InsertNewDef(unsigned Opcode, MachineBasicBlock *BB,115 MachineBasicBlock::iterator I,116 MachineRegisterInfo::VRegAttrs RegAttrs,117 MachineRegisterInfo *MRI,118 const TargetInstrInfo *TII) {119 Register NewVR = MRI->createVirtualRegister(RegAttrs);120 return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR);121}122 123/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that124/// is live in the middle of the specified block. If ExistingValueOnly is125/// true then this will only return an existing value or $noreg; otherwise new126/// instructions may be inserted to materialize a value.127///128/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one129/// important case: if there is a definition of the rewritten value after the130/// 'use' in BB. Consider code like this:131///132/// X1 = ...133/// SomeBB:134/// use(X)135/// X2 = ...136/// br Cond, SomeBB, OutBB137///138/// In this case, there are two values (X1 and X2) added to the AvailableVals139/// set by the client of the rewriter, and those values are both live out of140/// their respective blocks. However, the use of X happens in the *middle* of141/// a block. Because of this, we need to insert a new PHI node in SomeBB to142/// merge the appropriate values, and this value isn't live out of the block.143Register MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB,144 bool ExistingValueOnly) {145 // If there is no definition of the renamed variable in this block, just use146 // GetValueAtEndOfBlock to do our work.147 if (!HasValueForBlock(BB))148 return GetValueAtEndOfBlockInternal(BB, ExistingValueOnly);149 150 // If there are no predecessors, just return undef.151 if (BB->pred_empty()) {152 // If we cannot insert new instructions, just return $noreg.153 if (ExistingValueOnly)154 return Register();155 // Insert an implicit_def to represent an undef value.156 MachineInstr *NewDef =157 InsertNewDef(TargetOpcode::IMPLICIT_DEF, BB, BB->getFirstTerminator(),158 RegAttrs, MRI, TII);159 return NewDef->getOperand(0).getReg();160 }161 162 // Otherwise, we have the hard case. Get the live-in values for each163 // predecessor.164 SmallVector<std::pair<MachineBasicBlock*, Register>, 8> PredValues;165 Register SingularValue;166 167 bool isFirstPred = true;168 for (MachineBasicBlock *PredBB : BB->predecessors()) {169 Register PredVal = GetValueAtEndOfBlockInternal(PredBB, ExistingValueOnly);170 PredValues.push_back(std::make_pair(PredBB, PredVal));171 172 // Compute SingularValue.173 if (isFirstPred) {174 SingularValue = PredVal;175 isFirstPred = false;176 } else if (PredVal != SingularValue)177 SingularValue = Register();178 }179 180 // Otherwise, if all the merged values are the same, just use it.181 if (SingularValue)182 return SingularValue;183 184 // If an identical PHI is already in BB, just reuse it.185 Register DupPHI = LookForIdenticalPHI(BB, PredValues);186 if (DupPHI)187 return DupPHI;188 189 // If we cannot create new instructions, return $noreg now.190 if (ExistingValueOnly)191 return Register();192 193 // Otherwise, we do need a PHI: insert one now.194 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin();195 MachineInstrBuilder InsertedPHI =196 InsertNewDef(TargetOpcode::PHI, BB, Loc, RegAttrs, MRI, TII);197 198 // Fill in all the predecessors of the PHI.199 for (const auto &[SrcBB, SrcReg] : PredValues)200 InsertedPHI.addReg(SrcReg).addMBB(SrcBB);201 202 // See if the PHI node can be merged to a single value. This can happen in203 // loop cases when we get a PHI of itself and one other value.204 if (Register ConstVal = InsertedPHI->isConstantValuePHI()) {205 InsertedPHI->eraseFromParent();206 return ConstVal;207 }208 209 // If the client wants to know about all new instructions, tell it.210 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);211 212 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI);213 return InsertedPHI.getReg(0);214}215 216static217MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,218 MachineOperand *U) {219 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {220 if (&MI->getOperand(i) == U)221 return MI->getOperand(i+1).getMBB();222 }223 224 llvm_unreachable("MachineOperand::getParent() failure?");225}226 227/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,228/// which use their value in the corresponding predecessor.229void MachineSSAUpdater::RewriteUse(MachineOperand &U) {230 MachineInstr *UseMI = U.getParent();231 Register NewVR;232 if (UseMI->isPHI()) {233 MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);234 NewVR = GetValueAtEndOfBlockInternal(SourceBB);235 } else {236 NewVR = GetValueInMiddleOfBlock(UseMI->getParent());237 }238 239 // Insert a COPY if needed to satisfy register class constraints for the using240 // MO. Or, if possible, just constrain the class for NewVR to avoid the need241 // for a COPY.242 if (NewVR) {243 const TargetRegisterClass *UseRC =244 dyn_cast_or_null<const TargetRegisterClass *>(RegAttrs.RCOrRB);245 if (UseRC && !MRI->constrainRegClass(NewVR, UseRC)) {246 MachineBasicBlock *UseBB = UseMI->getParent();247 MachineInstr *InsertedCopy =248 InsertNewDef(TargetOpcode::COPY, UseBB, UseBB->getFirstNonPHI(),249 RegAttrs, MRI, TII)250 .addReg(NewVR);251 NewVR = InsertedCopy->getOperand(0).getReg();252 LLVM_DEBUG(dbgs() << " Inserted COPY: " << *InsertedCopy);253 }254 }255 U.setReg(NewVR);256}257 258namespace llvm {259 260/// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl261/// template, specialized for MachineSSAUpdater.262template<>263class SSAUpdaterTraits<MachineSSAUpdater> {264public:265 using BlkT = MachineBasicBlock;266 using ValT = Register;267 using PhiT = MachineInstr;268 using BlkSucc_iterator = MachineBasicBlock::succ_iterator;269 270 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }271 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }272 273 /// Iterator for PHI operands.274 class PHI_iterator {275 private:276 MachineInstr *PHI;277 unsigned idx;278 279 public:280 explicit PHI_iterator(MachineInstr *P) // begin iterator281 : PHI(P), idx(1) {}282 PHI_iterator(MachineInstr *P, bool) // end iterator283 : PHI(P), idx(PHI->getNumOperands()) {}284 285 PHI_iterator &operator++() { idx += 2; return *this; }286 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }287 bool operator!=(const PHI_iterator& x) const { return !operator==(x); }288 289 Register getIncomingValue() { return PHI->getOperand(idx).getReg(); }290 291 MachineBasicBlock *getIncomingBlock() {292 return PHI->getOperand(idx+1).getMBB();293 }294 };295 296 static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }297 298 static inline PHI_iterator PHI_end(PhiT *PHI) {299 return PHI_iterator(PHI, true);300 }301 302 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds303 /// vector.304 static void FindPredecessorBlocks(MachineBasicBlock *BB,305 SmallVectorImpl<MachineBasicBlock*> *Preds){306 append_range(*Preds, BB->predecessors());307 }308 309 /// GetPoisonVal - Create an IMPLICIT_DEF instruction with a new register.310 /// Add it into the specified block and return the register.311 static Register GetPoisonVal(MachineBasicBlock *BB,312 MachineSSAUpdater *Updater) {313 // Insert an implicit_def to represent a poison value.314 MachineInstr *NewDef =315 InsertNewDef(TargetOpcode::IMPLICIT_DEF, BB, BB->getFirstNonPHI(),316 Updater->RegAttrs, Updater->MRI, Updater->TII);317 return NewDef->getOperand(0).getReg();318 }319 320 /// CreateEmptyPHI - Create a PHI instruction that defines a new register.321 /// Add it into the specified block and return the register.322 static Register CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds,323 MachineSSAUpdater *Updater) {324 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin();325 MachineInstr *PHI =326 InsertNewDef(TargetOpcode::PHI, BB, Loc, Updater->RegAttrs,327 Updater->MRI, Updater->TII);328 return PHI->getOperand(0).getReg();329 }330 331 /// AddPHIOperand - Add the specified value as an operand of the PHI for332 /// the specified predecessor block.333 static void AddPHIOperand(MachineInstr *PHI, Register Val,334 MachineBasicBlock *Pred) {335 MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(Pred);336 }337 338 /// InstrIsPHI - Check if an instruction is a PHI.339 static MachineInstr *InstrIsPHI(MachineInstr *I) {340 if (I && I->isPHI())341 return I;342 return nullptr;343 }344 345 /// ValueIsPHI - Check if the instruction that defines the specified register346 /// is a PHI instruction.347 static MachineInstr *ValueIsPHI(Register Val, MachineSSAUpdater *Updater) {348 return InstrIsPHI(Updater->MRI->getVRegDef(Val));349 }350 351 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source352 /// operands, i.e., it was just added.353 static MachineInstr *ValueIsNewPHI(Register Val, MachineSSAUpdater *Updater) {354 MachineInstr *PHI = ValueIsPHI(Val, Updater);355 if (PHI && PHI->getNumOperands() <= 1)356 return PHI;357 return nullptr;358 }359 360 /// GetPHIValue - For the specified PHI instruction, return the register361 /// that it defines.362 static Register GetPHIValue(MachineInstr *PHI) {363 return PHI->getOperand(0).getReg();364 }365};366 367} // end namespace llvm368 369/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry370/// for the specified BB and if so, return it. If not, construct SSA form by371/// first calculating the required placement of PHIs and then inserting new372/// PHIs where needed.373Register374MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB,375 bool ExistingValueOnly) {376 AvailableValsTy &AvailableVals = getAvailableVals(AV);377 Register ExistingVal = AvailableVals.lookup(BB);378 if (ExistingVal || ExistingValueOnly)379 return ExistingVal;380 381 SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);382 return Impl.GetValue(BB);383}384