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