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