+ bool inserted = false;
+ for (DomForestNode::iterator CI = DFNode->begin(), CE = DFNode->end();
+ CI != CE; ++CI) {
+ DomForestNode* child = *CI;
+
+ // If the current node is live-out of the defining block of one of its
+ // children, insert a copy for it. NOTE: The paper actually calls for
+ // a more elaborate heuristic for determining whether to insert copies
+ // for the child or the parent. In the interest of simplicity, we're
+ // just always choosing the parent.
+ if (isLiveOut(DFNode->getReg(),
+ MRI.getVRegDef(child->getReg())->getParent(), MRI, LV)) {
+ // Insert copies for parent
+ for (int i = Inst->getNumOperands() - 1; i >= 2; i-=2) {
+ if (Inst->getOperand(i-1).getReg() == DFNode->getReg()) {
+ unsigned SrcReg = DFNode->getReg();
+ MachineBasicBlock* From = Inst->getOperand(i).getMBB();
+
+ Waiting[From].insert(std::make_pair(SrcReg, DestReg));
+ UsedByAnother.insert(SrcReg);
+
+ PHIUnion.erase(SrcReg);
+ }
+ }
+
+ // If a node is live-in to the defining block of one of its children, but
+ // not live-out, then we need to scan that block for local interferences.
+ } else if (isLiveIn(DFNode->getReg(),
+ MRI.getVRegDef(child->getReg())->getParent(),
+ MRI, LV) ||
+ MRI.getVRegDef(DFNode->getReg())->getParent() ==
+ MRI.getVRegDef(child->getReg())->getParent()) {
+ // Add (p, c) to possible local interferences
+ locals.push_back(std::make_pair(DFNode->getReg(), child->getReg()));
+ }
+
+ if (!visited.count(child)) {
+ worklist.push_back(child);
+ inserted = true;
+ }
+ }
+
+ if (!inserted) worklist.pop_back();
+ }
+}
+
+/// 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);
+ }