+/// ScheduleCopies - Insert copies into predecessor blocks, scheduling
+/// them properly so as to avoid the 'lost copy' and the 'virtual swap'
+/// problems.
+///
+/// Based on "Practical Improvements to the Construction and Destruction
+/// of Static Single Assignment Form" by Briggs, et al.
+void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
+ std::set<unsigned>& pushed) {
+ // FIXME: This function needs to update LiveVariables
+ std::map<unsigned, unsigned>& copy_set= Waiting[MBB];
+
+ std::map<unsigned, unsigned> worklist;
+ std::map<unsigned, unsigned> map;
+
+ // Setup worklist of initial copies
+ for (std::map<unsigned, unsigned>::iterator I = copy_set.begin(),
+ E = copy_set.end(); I != E; ) {
+ map.insert(std::make_pair(I->first, I->first));
+ map.insert(std::make_pair(I->second, I->second));
+
+ if (!UsedByAnother.count(I->first)) {
+ worklist.insert(*I);
+
+ // Avoid iterator invalidation
+ unsigned first = I->first;
+ ++I;
+ copy_set.erase(first);
+ } else {
+ ++I;
+ }
+ }
+
+ LiveVariables& LV = getAnalysis<LiveVariables>();
+ MachineFunction* MF = MBB->getParent();
+ MachineRegisterInfo& MRI = MF->getRegInfo();
+ const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
+
+ // Iterate over the worklist, inserting copies
+ while (!worklist.empty() || !copy_set.empty()) {
+ while (!worklist.empty()) {
+ std::pair<unsigned, unsigned> curr = *worklist.begin();
+ worklist.erase(curr.first);
+
+ const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first);
+
+ if (isLiveOut(curr.second, MBB, MRI, LV)) {
+ // Create a temporary
+ unsigned t = MF->getRegInfo().createVirtualRegister(RC);
+
+ // Insert copy from curr.second to a temporary at
+ // the Phi defining curr.second
+ MachineBasicBlock::iterator PI = MRI.getVRegDef(curr.second);
+ TII->copyRegToReg(*PI->getParent(), PI, t,
+ curr.second, RC, RC);
+
+ // Push temporary on Stacks
+ Stacks[curr.second].push_back(t);
+
+ // Insert curr.second in pushed
+ pushed.insert(curr.second);
+ }
+
+ // Insert copy from map[curr.first] to curr.second
+ TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second,
+ map[curr.first], RC, RC);
+ map[curr.first] = curr.second;
+
+ // If curr.first is a destination in copy_set...
+ for (std::map<unsigned, unsigned>::iterator I = copy_set.begin(),
+ E = copy_set.end(); I != E; )
+ if (curr.first == I->second) {
+ std::pair<unsigned, unsigned> temp = *I;
+
+ // Avoid iterator invalidation
+ ++I;
+ copy_set.erase(temp.first);
+ worklist.insert(temp);
+
+ break;
+ } else {
+ ++I;
+ }
+ }
+
+ if (!copy_set.empty()) {
+ std::pair<unsigned, unsigned> curr = *copy_set.begin();
+ copy_set.erase(curr.first);
+
+ const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first);
+
+ // Insert a copy from dest to a new temporary t at the end of b
+ unsigned t = MF->getRegInfo().createVirtualRegister(RC);
+ TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), t,
+ curr.second, RC, RC);
+ map[curr.second] = t;
+
+ worklist.insert(curr);
+ }
+ }
+}
+
+/// InsertCopies - insert copies into MBB and all of its successors
+void StrongPHIElimination::InsertCopies(MachineBasicBlock* MBB,
+ std::set<MachineBasicBlock*>& visited) {
+ visited.insert(MBB);
+
+ std::set<unsigned> pushed;
+
+ // Rewrite register uses from Stacks
+ for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
+ I != E; ++I)
+ for (unsigned i = 0; i < I->getNumOperands(); ++i)
+ if (I->getOperand(i).isRegister() &&
+ Stacks[I->getOperand(i).getReg()].size()) {
+ I->getOperand(i).setReg(Stacks[I->getOperand(i).getReg()].back());
+ }
+
+ // Schedule the copies for this block
+ ScheduleCopies(MBB, pushed);
+
+ // Recur to our successors
+ for (GraphTraits<MachineBasicBlock*>::ChildIteratorType I =
+ GraphTraits<MachineBasicBlock*>::child_begin(MBB), E =
+ GraphTraits<MachineBasicBlock*>::child_end(MBB); I != E; ++I)
+ if (!visited.count(*I))
+ InsertCopies(*I, visited);
+
+ // As we exit this block, pop the names we pushed while processing it
+ for (std::set<unsigned>::iterator I = pushed.begin(),
+ E = pushed.end(); I != E; ++I)
+ Stacks[*I].pop_back();
+}
+