(1) Added special register class containing (for now) %fsr.
[oota-llvm.git] / lib / CodeGen / PHIElimination.cpp
1 //===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===//
2 //
3 // This pass eliminates machine instruction PHI nodes by inserting copy
4 // instructions.  This destroys SSA information, but is the desired input for
5 // some register allocators.
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/CodeGen/MachineFunctionPass.h"
10 #include "llvm/CodeGen/MachineInstr.h"
11 #include "llvm/CodeGen/SSARegMap.h"
12 #include "llvm/CodeGen/LiveVariables.h"
13 #include "llvm/Target/TargetInstrInfo.h"
14 #include "llvm/Target/TargetMachine.h"
15 #include "llvm/Support/CFG.h"
16
17 namespace {
18   struct PNE : public MachineFunctionPass {
19     bool runOnMachineFunction(MachineFunction &Fn) {
20       bool Changed = false;
21
22       // Eliminate PHI instructions by inserting copies into predecessor blocks.
23       //
24       for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
25         Changed |= EliminatePHINodes(Fn, *I);
26
27       //std::cerr << "AFTER PHI NODE ELIM:\n";
28       //Fn.dump();
29       return Changed;
30     }
31
32     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
33       AU.addPreserved<LiveVariables>();
34       MachineFunctionPass::getAnalysisUsage(AU);
35     }
36
37   private:
38     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
39     /// in predecessor basic blocks.
40     ///
41     bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
42   };
43
44   RegisterPass<PNE> X("phi-node-elimination",
45                       "Eliminate PHI nodes for register allocation");
46 }
47
48 const PassInfo *PHIEliminationID = X.getPassInfo();
49
50 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
51 /// predecessor basic blocks.
52 ///
53 bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) {
54   if (MBB.empty() || MBB.front()->getOpcode() != TargetInstrInfo::PHI)
55     return false;   // Quick exit for normal case...
56
57   LiveVariables *LV = getAnalysisToUpdate<LiveVariables>();
58   const TargetInstrInfo &MII = MF.getTarget().getInstrInfo();
59   const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo();
60
61   while (MBB.front()->getOpcode() == TargetInstrInfo::PHI) {
62     MachineInstr *MI = MBB.front();
63     // Unlink the PHI node from the basic block... but don't delete the PHI yet
64     MBB.erase(MBB.begin());
65
66     assert(MI->getOperand(0).isVirtualRegister() &&
67            "PHI node doesn't write virt reg?");
68
69     unsigned DestReg = MI->getOperand(0).getAllocatedRegNum();
70     
71     // Create a new register for the incoming PHI arguments
72     const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg);
73     unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC);
74
75     // Insert a register to register copy in the top of the current block (but
76     // after any remaining phi nodes) which copies the new incoming register
77     // into the phi node destination.
78     //
79     MachineBasicBlock::iterator AfterPHIsIt = MBB.begin();
80     while (AfterPHIsIt != MBB.end() &&
81            (*AfterPHIsIt)->getOpcode() == TargetInstrInfo::PHI)
82       ++AfterPHIsIt;    // Skip over all of the PHI nodes...
83     RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC);
84     
85     // Update live variable information if there is any...
86     if (LV) {
87       MachineInstr *PHICopy = *(AfterPHIsIt-1);
88
89       // Add information to LiveVariables to know that the incoming value is
90       // killed.  Note that because the value is defined in several places (once
91       // each for each incoming block), the "def" block and instruction fields
92       // for the VarInfo is not filled in.
93       //
94       LV->addVirtualRegisterKilled(IncomingReg, &MBB, PHICopy);
95
96       // Since we are going to be deleting the PHI node, if it is the last use
97       // of any registers, or if the value itself is dead, we need to move this
98       // information over to the new copy we just inserted...
99       //
100       std::pair<LiveVariables::killed_iterator, LiveVariables::killed_iterator> 
101         RKs = LV->killed_range(MI);
102       std::vector<std::pair<MachineInstr*, unsigned> > Range;
103       if (RKs.first != RKs.second) {
104         // Copy the range into a vector...
105         Range.assign(RKs.first, RKs.second);
106
107         // Delete the range...
108         LV->removeVirtualRegistersKilled(RKs.first, RKs.second);
109
110         // Add all of the kills back, which will update the appropriate info...
111         for (unsigned i = 0, e = Range.size(); i != e; ++i)
112           LV->addVirtualRegisterKilled(Range[i].second, &MBB, PHICopy);
113       }
114
115       RKs = LV->dead_range(MI);
116       if (RKs.first != RKs.second) {
117         // Works as above...
118         Range.assign(RKs.first, RKs.second);
119         LV->removeVirtualRegistersDead(RKs.first, RKs.second);
120         for (unsigned i = 0, e = Range.size(); i != e; ++i)
121           LV->addVirtualRegisterDead(Range[i].second, &MBB, PHICopy);
122       }
123     }
124
125     // Now loop over all of the incoming arguments, changing them to copy into
126     // the IncomingReg register in the corresponding predecessor basic block.
127     //
128     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
129       MachineOperand &opVal = MI->getOperand(i-1);
130       
131       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
132       // source path the PHI.
133       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
134
135       // Figure out where to insert the copy, which is at the end of the
136       // predecessor basic block, but before any terminator/branch
137       // instructions...
138       MachineBasicBlock::iterator I = opBlock.end();
139       if (I != opBlock.begin()) {  // Handle empty blocks
140         --I;
141         // must backtrack over ALL the branches in the previous block
142         while (MII.isTerminatorInstr((*I)->getOpcode()) &&
143                I != opBlock.begin())
144           --I;
145         
146         // move back to the first branch instruction so new instructions
147         // are inserted right in front of it and not in front of a non-branch
148         if (!MII.isTerminatorInstr((*I)->getOpcode()))
149           ++I;
150       }
151       
152       // Check to make sure we haven't already emitted the copy for this block.
153       // This can happen because PHI nodes may have multiple entries for the
154       // same basic block.  It doesn't matter which entry we use though, because
155       // all incoming values are guaranteed to be the same for a particular bb.
156       //
157       // If we emitted a copy for this basic block already, it will be right
158       // where we want to insert one now.  Just check for a definition of the
159       // register we are interested in!
160       //
161       bool HaveNotEmitted = true;
162       
163       if (I != opBlock.begin()) {
164         MachineInstr *PrevInst = *(I-1);
165         for (unsigned i = 0, e = PrevInst->getNumOperands(); i != e; ++i) {
166           MachineOperand &MO = PrevInst->getOperand(i);
167           if (MO.isVirtualRegister() && MO.getReg() == IncomingReg)
168             if (MO.opIsDefOnly() || MO.opIsDefAndUse()) {
169               HaveNotEmitted = false;
170               break;
171             }             
172         }
173       }
174
175       if (HaveNotEmitted) { // If the copy has not already been emitted, do it.
176         assert(opVal.isVirtualRegister() &&
177                "Machine PHI Operands must all be virtual registers!");
178         unsigned SrcReg = opVal.getReg();
179         RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC);
180
181         // Now update live variable information if we have it.
182         if (LV) {
183           // We want to be able to insert a kill of the register if this PHI
184           // (aka, the copy we just inserted) is the last use of the source
185           // value.  Live variable analysis conservatively handles this by
186           // saying that the value is live until the end of the block the PHI
187           // entry lives in.  If the value really is dead at the PHI copy, there
188           // will be no successor blocks which have the value live-in.
189           //
190           // Check to see if the copy is the last use, and if so, update the
191           // live variables information so that it knows the copy source
192           // instruction kills the incoming value.
193           //
194           LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg);
195
196           // Loop over all of the successors of the basic block, checking to
197           // see if the value is either live in the block, or if it is killed
198           // in the block.
199           //
200           bool ValueIsLive = false;
201           BasicBlock *BB = opBlock.getBasicBlock();
202           for (succ_iterator SI = succ_begin(BB), E = succ_end(BB);
203                SI != E; ++SI) {
204             const std::pair<MachineBasicBlock*, unsigned> &
205               SuccInfo = LV->getBasicBlockInfo(*SI);
206             
207             // Is it alive in this successor?
208             unsigned SuccIdx = SuccInfo.second;
209             if (SuccIdx < InRegVI.AliveBlocks.size() &&
210                 InRegVI.AliveBlocks[SuccIdx]) {
211               ValueIsLive = true;
212               break;
213             }
214             
215             // Is it killed in this successor?
216             MachineBasicBlock *MBB = SuccInfo.first;
217             for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
218               if (InRegVI.Kills[i].first == MBB) {
219                 ValueIsLive = true;
220                 break;
221               }
222           }
223           
224           // Okay, if we now know that the value is not live out of the block,
225           // we can add a kill marker to the copy we inserted saying that it
226           // kills the incoming value!
227           //
228           if (!ValueIsLive) {
229             // One more complication to worry about.  There may actually be
230             // multiple PHI nodes using this value on this branch.  If we aren't
231             // careful, the first PHI node will end up killing the value, not
232             // letting it get the to the copy for the final PHI node in the
233             // block.  Therefore we have to check to see if there is already a
234             // kill in this block, and if so, extend the lifetime to our new
235             // copy.
236             //
237             for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
238               if (InRegVI.Kills[i].first == &opBlock) {
239                 std::pair<LiveVariables::killed_iterator,
240                           LiveVariables::killed_iterator> Range
241                   = LV->killed_range(InRegVI.Kills[i].second);
242                 LV->removeVirtualRegistersKilled(Range.first, Range.second);
243                 break;
244               }
245
246             LV->addVirtualRegisterKilled(SrcReg, &opBlock, *(I-1));
247           }
248         }
249       }
250     }
251     
252     // really delete the PHI instruction now!
253     delete MI;
254   }
255
256   return true;
257 }