Iterating over sets of pointers in a heuristic was a bad idea. Switching
[oota-llvm.git] / 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/CodeGen/MachineInstr.h"
17 #include "llvm/CodeGen/MachineInstrBuilder.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Target/TargetMachine.h"
21 #include "llvm/Target/TargetRegisterInfo.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/Support/AlignOf.h"
25 #include "llvm/Support/Allocator.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/raw_ostream.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 &getAvailableVals(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->front();
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->front();
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   return 0;
218 }
219
220 /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
221 /// which use their value in the corresponding predecessor.
222 void 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 void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) {
236   MRI->replaceRegWith(OldReg, NewReg);
237
238   AvailableValsTy &AvailableVals = getAvailableVals(AV);
239   for (DenseMap<MachineBasicBlock*, unsigned>::iterator
240          I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I)
241     if (I->second == OldReg)
242       I->second = NewReg;
243 }
244
245 /// MachinePHIiter - Iterator for PHI operands.  This is used for the
246 /// PHI_iterator in the SSAUpdaterImpl template.
247 namespace {
248   class MachinePHIiter {
249   private:
250     MachineInstr *PHI;
251     unsigned idx;
252  
253   public:
254     explicit MachinePHIiter(MachineInstr *P) // begin iterator
255       : PHI(P), idx(1) {}
256     MachinePHIiter(MachineInstr *P, bool) // end iterator
257       : PHI(P), idx(PHI->getNumOperands()) {}
258
259     MachinePHIiter &operator++() { idx += 2; return *this; } 
260     bool operator==(const MachinePHIiter& x) const { return idx == x.idx; }
261     bool operator!=(const MachinePHIiter& x) const { return !operator==(x); }
262     unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); }
263     MachineBasicBlock *getIncomingBlock() {
264       return PHI->getOperand(idx+1).getMBB();
265     }
266   };
267 }
268
269 /// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl
270 /// template, specialized for MachineSSAUpdater.
271 namespace llvm {
272 template<>
273 class SSAUpdaterTraits<MachineSSAUpdater> {
274 public:
275   typedef MachineBasicBlock BlkT;
276   typedef unsigned ValT;
277   typedef MachineInstr PhiT;
278
279   typedef MachineBasicBlock::succ_iterator BlkSucc_iterator;
280   static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
281   static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
282
283   typedef MachinePHIiter PHI_iterator;
284   static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
285   static inline PHI_iterator PHI_end(PhiT *PHI) {
286     return PHI_iterator(PHI, true);
287   }
288
289   /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
290   /// vector.
291   static void FindPredecessorBlocks(MachineBasicBlock *BB,
292                                     SmallVectorImpl<MachineBasicBlock*> *Preds){
293     for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
294            E = BB->pred_end(); PI != E; ++PI)
295       Preds->push_back(*PI);
296   }
297
298   /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register.
299   /// Add it into the specified block and return the register.
300   static unsigned GetUndefVal(MachineBasicBlock *BB,
301                               MachineSSAUpdater *Updater) {
302     // Insert an implicit_def to represent an undef value.
303     MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
304                                         BB, BB->getFirstTerminator(),
305                                         Updater->VRC, Updater->MRI,
306                                         Updater->TII);
307     return NewDef->getOperand(0).getReg();
308   }
309
310   /// CreateEmptyPHI - Create a PHI instruction that defines a new register.
311   /// Add it into the specified block and return the register.
312   static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds,
313                                  MachineSSAUpdater *Updater) {
314     MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
315     MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
316                                      Updater->VRC, Updater->MRI,
317                                      Updater->TII);
318     return PHI->getOperand(0).getReg();
319   }
320
321   /// AddPHIOperand - Add the specified value as an operand of the PHI for
322   /// the specified predecessor block.
323   static void AddPHIOperand(MachineInstr *PHI, unsigned Val,
324                             MachineBasicBlock *Pred) {
325     PHI->addOperand(MachineOperand::CreateReg(Val, false));
326     PHI->addOperand(MachineOperand::CreateMBB(Pred));
327   }
328
329   /// InstrIsPHI - Check if an instruction is a PHI.
330   ///
331   static MachineInstr *InstrIsPHI(MachineInstr *I) {
332     if (I && I->isPHI())
333       return I;
334     return 0;
335   }
336
337   /// ValueIsPHI - Check if the instruction that defines the specified register
338   /// is a PHI instruction.
339   static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) {
340     return InstrIsPHI(Updater->MRI->getVRegDef(Val));
341   }
342
343   /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
344   /// operands, i.e., it was just added.
345   static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) {
346     MachineInstr *PHI = ValueIsPHI(Val, Updater);
347     if (PHI && PHI->getNumOperands() <= 1)
348       return PHI;
349     return 0;
350   }
351
352   /// GetPHIValue - For the specified PHI instruction, return the register
353   /// that it defines.
354   static unsigned GetPHIValue(MachineInstr *PHI) {
355     return PHI->getOperand(0).getReg();
356   }
357 };
358
359 } // End llvm namespace
360
361 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
362 /// for the specified BB and if so, return it.  If not, construct SSA form by
363 /// first calculating the required placement of PHIs and then inserting new
364 /// PHIs where needed.
365 unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
366   AvailableValsTy &AvailableVals = getAvailableVals(AV);
367   if (unsigned V = AvailableVals[BB])
368     return V;
369
370   SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
371   return Impl.GetValue(BB);
372 }