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