//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Owen Anderson and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#define DEBUG_TYPE "strongphielim"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/BreakCriticalMachineEdge.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Compiler.h"
using namespace llvm;
StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
DenseMap<MachineBasicBlock*,
- SmallVector<std::pair<unsigned, unsigned>, 2> > Waiting;
+ std::map<unsigned, unsigned> > Waiting;
+
+ std::map<unsigned, std::vector<unsigned> > Stacks;
+ std::set<unsigned> UsedByAnother;
bool runOnMachineFunction(MachineFunction &Fn);
preorder.clear();
maxpreorder.clear();
- waiting.clear();
+ Waiting.clear();
}
private:
DenseMap<MachineBasicBlock*, unsigned> preorder;
DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
- DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > waiting;
-
void computeDFS(MachineFunction& MF);
void processBlock(MachineBasicBlock* MBB);
std::set<unsigned>& PHIUnion,
std::vector<StrongPHIElimination::DomForestNode*>& DF,
std::vector<std::pair<unsigned, unsigned> >& locals);
- void breakCriticalEdges(MachineFunction &Fn);
-
+ void ScheduleCopies(MachineBasicBlock* MBB, std::set<unsigned>& pushed);
+ void InsertCopies(MachineBasicBlock* MBB);
};
char StrongPHIElimination::ID = 0;
return false;
}
+/// isKillInst - helper method that determines, from a VarInfo, if an
+/// instruction kills a given register
+bool isKillInst(LiveVariables::VarInfo& V, MachineInstr* MI) {
+ return std::find(V.Kills.begin(), V.Kills.end(), MI) != V.Kills.end();
+}
+
+/// interferes - checks for local interferences by scanning a block. The only
+/// trick parameter is 'mode' which tells it the relationship of the two
+/// registers. 0 - defined in the same block, 1 - first properly dominates
+/// second, 2 - second properly dominates first
+bool interferes(LiveVariables::VarInfo& First, LiveVariables::VarInfo& Second,
+ MachineBasicBlock* scan, unsigned mode) {
+ MachineInstr* def = 0;
+ MachineInstr* kill = 0;
+
+ bool interference = false;
+
+ // Wallk the block, checking for interferences
+ for (MachineBasicBlock::iterator MBI = scan->begin(), MBE = scan->end();
+ MBI != MBE; ++MBI) {
+ MachineInstr* curr = MBI;
+
+ // Same defining block...
+ if (mode == 0) {
+ if (curr == First.DefInst) {
+ // If we find our first DefInst, save it
+ if (!def) {
+ def = curr;
+ // If there's already an unkilled DefInst, then
+ // this is an interference
+ } else if (!kill) {
+ interference = true;
+ break;
+ // If there's a DefInst followed by a KillInst, then
+ // they can't interfere
+ } else {
+ interference = false;
+ break;
+ }
+ // Symmetric with the above
+ } else if (curr == Second.DefInst ) {
+ if (!def) {
+ def = curr;
+ } else if (!kill) {
+ interference = true;
+ break;
+ } else {
+ interference = false;
+ break;
+ }
+ // Store KillInsts if they match up with the DefInst
+ } else if (isKillInst(First, curr)) {
+ if (def == First.DefInst) {
+ kill = curr;
+ } else if (isKillInst(Second, curr)) {
+ if (def == Second.DefInst) {
+ kill = curr;
+ }
+ }
+ }
+ // First properly dominates second...
+ } else if (mode == 1) {
+ if (curr == Second.DefInst) {
+ // DefInst of second without kill of first is an interference
+ if (!kill) {
+ interference = true;
+ break;
+ // DefInst after a kill is a non-interference
+ } else {
+ interference = false;
+ break;
+ }
+ // Save KillInsts of First
+ } else if (isKillInst(First, curr)) {
+ kill = curr;
+ }
+ // Symmetric with the above
+ } else if (mode == 2) {
+ if (curr == First.DefInst) {
+ if (!kill) {
+ interference = true;
+ break;
+ } else {
+ interference = false;
+ break;
+ }
+ } else if (isKillInst(Second, curr)) {
+ kill = curr;
+ }
+ }
+ }
+
+ return interference;
+}
+
/// processBlock - Eliminate PHIs in the given block
void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
LiveVariables& LV = getAnalysis<LiveVariables>();
UnionedBlocks.count(SrcInfo.DefInst->getParent())) {
// add a copy from a_i to p in Waiting[From[a_i]]
- MachineBasicBlock* From = P->getOperand(i).getMachineBasicBlock();
- Waiting[From].push_back(std::make_pair(SrcReg, DestReg));
+ MachineBasicBlock* From = P->getOperand(i).getMBB();
+ Waiting[From].insert(std::make_pair(SrcReg, DestReg));
+ UsedByAnother.insert(SrcReg);
} else {
PHIUnion.insert(SrcReg);
UnionedBlocks.insert(SrcInfo.DefInst->getParent());
std::vector<std::pair<unsigned, unsigned> > localInterferences;
processPHIUnion(P, PHIUnion, DF, localInterferences);
- // FIXME: Check for local interferences
+ // Check for local interferences
+ for (std::vector<std::pair<unsigned, unsigned> >::iterator I =
+ localInterferences.begin(), E = localInterferences.end(); I != E; ++I) {
+ std::pair<unsigned, unsigned> p = *I;
+
+ LiveVariables::VarInfo& FirstInfo = LV.getVarInfo(p.first);
+ LiveVariables::VarInfo& SecondInfo = LV.getVarInfo(p.second);
+
+ MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
+
+ // Determine the block we need to scan and the relationship between
+ // the two registers
+ MachineBasicBlock* scan = 0;
+ unsigned mode = 0;
+ if (FirstInfo.DefInst->getParent() == SecondInfo.DefInst->getParent()) {
+ scan = FirstInfo.DefInst->getParent();
+ mode = 0; // Same block
+ } else if (MDT.dominates(FirstInfo.DefInst->getParent(),
+ SecondInfo.DefInst->getParent())) {
+ scan = SecondInfo.DefInst->getParent();
+ mode = 1; // First dominates second
+ } else {
+ scan = FirstInfo.DefInst->getParent();
+ mode = 2; // Second dominates first
+ }
+
+ // If there's an interference, we need to insert copies
+ if (interferes(FirstInfo, SecondInfo, scan, mode)) {
+ // Insert copies for First
+ for (int i = P->getNumOperands() - 1; i >= 2; i-=2) {
+ if (P->getOperand(i-1).getReg() == p.first) {
+ unsigned SrcReg = p.first;
+ MachineBasicBlock* From = P->getOperand(i).getMBB();
+
+ Waiting[From].insert(std::make_pair(SrcReg,
+ P->getOperand(0).getReg()));
+ UsedByAnother.insert(SrcReg);
+
+ PHIUnion.erase(SrcReg);
+ }
+ }
+ }
+ }
+
+ // FIXME: Cache renaming information
ProcessedNames.insert(PHIUnion.begin(), PHIUnion.end());
++P;
unsigned SrcReg = DFNode->getReg();
MachineBasicBlock* From = Inst->getOperand(i).getMBB();
- Waiting[From].push_back(std::make_pair(SrcReg, DestReg));
+ Waiting[From].insert(std::make_pair(SrcReg, DestReg));
+ UsedByAnother.insert(SrcReg);
+
PHIUnion.erase(SrcReg);
}
}
}
}
-/// breakCriticalEdges - Break critical edges coming into blocks with PHI
-/// nodes, preserving dominator and livevariable info.
-void StrongPHIElimination::breakCriticalEdges(MachineFunction &Fn) {
- typedef std::pair<MachineBasicBlock*, MachineBasicBlock*> MBB_pair;
+/// 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) {
+ 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;
+ }
+ }
- MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
LiveVariables& LV = getAnalysis<LiveVariables>();
- // Find critical edges
- std::vector<MBB_pair> criticals;
- for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
- if (!I->empty() &&
- I->begin()->getOpcode() == TargetInstrInfo::PHI &&
- I->pred_size() > 1)
- for (MachineBasicBlock::pred_iterator PI = I->pred_begin(),
- PE = I->pred_end(); PI != PE; ++PI)
- if ((*PI)->succ_size() > 1)
- criticals.push_back(std::make_pair(*PI, I));
-
- for (std::vector<MBB_pair>::iterator I = criticals.begin(),
- E = criticals.end(); I != E; ++I) {
- // Split the edge
- MachineBasicBlock* new_bb = SplitCriticalMachineEdge(I->first, I->second);
-
- // Update dominators
- MDT.splitBlock(I->first);
+ // 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);
+
+ if (isLiveOut(LV.getVarInfo(curr.second), MBB)) {
+ // Insert copy from curr.second to a temporary
+ // Push temporary on Stacks
+ // Insert temporary in pushed
+ }
+
+ // Insert copy from map[curr.first] to curr.second
+ 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;
+ }
+ }
- // Update livevariables
- for (unsigned var = 1024; var < Fn.getSSARegMap()->getLastVirtReg(); ++var)
- if (isLiveOut(LV.getVarInfo(var), I->first))
- LV.getVarInfo(var).AliveBlocks.set(new_bb->getNumber());
+ if (!copy_set.empty()) {
+ std::pair<unsigned, unsigned> curr = *copy_set.begin();
+ copy_set.erase(curr.first);
+
+ // Insert a copy from dest to a new temporary t at the end of b
+ // map[curr.second] = t;
+
+ worklist.insert(curr);
+ }
}
}
+/// InsertCopies - insert copies into MBB and all of its successors
+void StrongPHIElimination::InsertCopies(MachineBasicBlock* 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)
+ InsertCopies(*I);
+
+ // 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();
+}
+
bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
- breakCriticalEdges(Fn);
+ // Compute DFS numbers of each block
computeDFS(Fn);
+ // Determine which phi node operands need copies
for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
if (!I->empty() &&
I->begin()->getOpcode() == TargetInstrInfo::PHI)
processBlock(I);
+ // Insert copies
+ // FIXME: This process should probably preserve LiveVariables
+ InsertCopies(Fn.begin());
+
+ // FIXME: Perform renaming
+
return false;
}
projects / oota-llvm.git / blobdiff