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