lib/CodeGen/MachineSSAUpdater.cpp

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