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