lib/CodeGen/StrongPHIElimination.cpp

   1 //===- StrongPhiElimination.cpp - Eliminate PHI nodes by inserting copies -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Owen Anderson and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass eliminates machine instruction PHI nodes by inserting copy
  11 // instructions, using an intelligent copy-folding technique based on
  12 // dominator information.  This is technique is derived from:
  13 //
  14 //    Budimlic, et al. Fast copy coalescing and live-range identification.
  15 //    In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
  16 //    Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
  17 //    PLDI '02. ACM, New York, NY, 25-32.
  18 //    DOI= http://doi.acm.org/10.1145/512529.512534
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #define DEBUG_TYPE "strongphielim"
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/CodeGen/LiveVariables.h"
  25 #include "llvm/CodeGen/MachineDominators.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstr.h"
  28 #include "llvm/Target/TargetInstrInfo.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/Support/Compiler.h"
  32 using namespace llvm;
  33
  34
  35 namespace {
  36   struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass {
  37     static char ID; // Pass identification, replacement for typeid
  38     StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
  39
  40     bool runOnMachineFunction(MachineFunction &Fn);
  41
  42     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  43       AU.addPreserved<LiveVariables>();
  44       AU.addPreservedID(PHIEliminationID);
  45       AU.addRequired<MachineDominatorTree>();
  46       AU.addRequired<LiveVariables>();
  47       AU.setPreservesAll();
  48       MachineFunctionPass::getAnalysisUsage(AU);
  49     }
  50
  51     virtual void releaseMemory() {
  52       preorder.clear();
  53       maxpreorder.clear();
  54
  55       waiting.clear();
  56     }
  57
  58   private:
  59     struct DomForestNode {
  60     private:
  61       std::vector<DomForestNode*> children;
  62       unsigned reg;
  63
  64       void addChild(DomForestNode* DFN) { children.push_back(DFN); }
  65
  66     public:
  67       typedef std::vector<DomForestNode*>::iterator iterator;
  68
  69       DomForestNode(unsigned r, DomForestNode* parent) : reg(r) {
  70         if (parent)
  71           parent->addChild(this);
  72       }
  73
  74       ~DomForestNode() {
  75         for (iterator I = begin(), E = end(); I != E; ++I)
  76           delete *I;
  77       }
  78
  79       inline unsigned getReg() { return reg; }
  80
  81       inline DomForestNode::iterator begin() { return children.begin(); }
  82       inline DomForestNode::iterator end() { return children.end(); }
  83     };
  84
  85     DenseMap<MachineBasicBlock*, unsigned> preorder;
  86     DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
  87
  88     DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > waiting;
  89
  90
  91     void computeDFS(MachineFunction& MF);
  92     void processPHI(MachineInstr* P);
  93
  94     std::vector<DomForestNode*> computeDomForest(std::set<unsigned>& instrs);
  95
  96   };
  97
  98   char StrongPHIElimination::ID = 0;
  99   RegisterPass<StrongPHIElimination> X("strong-phi-node-elimination",
 100                   "Eliminate PHI nodes for register allocation, intelligently");
 101 }
 102
 103 const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo();
 104
 105 /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
 106 /// of the given MachineFunction.  These numbers are then used in other parts
 107 /// of the PHI elimination process.
 108 void StrongPHIElimination::computeDFS(MachineFunction& MF) {
 109   SmallPtrSet<MachineDomTreeNode*, 8> frontier;
 110   SmallPtrSet<MachineDomTreeNode*, 8> visited;
 111
 112   unsigned time = 0;
 113
 114   MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
 115
 116   MachineDomTreeNode* node = DT.getRootNode();
 117
 118   std::vector<MachineDomTreeNode*> worklist;
 119   worklist.push_back(node);
 120
 121   while (!worklist.empty()) {
 122     MachineDomTreeNode* currNode = worklist.back();
 123
 124     if (!frontier.count(currNode)) {
 125       frontier.insert(currNode);
 126       ++time;
 127       preorder.insert(std::make_pair(currNode->getBlock(), time));
 128     }
 129
 130     bool inserted = false;
 131     for (MachineDomTreeNode::iterator I = node->begin(), E = node->end();
 132          I != E; ++I)
 133       if (!frontier.count(*I) && !visited.count(*I)) {
 134         worklist.push_back(*I);
 135         inserted = true;
 136         break;
 137       }
 138
 139     if (!inserted) {
 140       frontier.erase(currNode);
 141       visited.insert(currNode);
 142       maxpreorder.insert(std::make_pair(currNode->getBlock(), time));
 143
 144       worklist.pop_back();
 145     }
 146   }
 147 }
 148
 149 /// PreorderSorter - a helper class that is used to sort registers
 150 /// according to the preorder number of their defining blocks
 151 class PreorderSorter {
 152 private:
 153   DenseMap<MachineBasicBlock*, unsigned>& preorder;
 154   LiveVariables& LV;
 155
 156 public:
 157   PreorderSorter(DenseMap<MachineBasicBlock*, unsigned>& p,
 158                 LiveVariables& L) : preorder(p), LV(L) { }
 159
 160   bool operator()(unsigned A, unsigned B) {
 161     if (A == B)
 162       return false;
 163
 164     MachineBasicBlock* ABlock = LV.getVarInfo(A).DefInst->getParent();
 165     MachineBasicBlock* BBlock = LV.getVarInfo(A).DefInst->getParent();
 166
 167     if (preorder[ABlock] < preorder[BBlock])
 168       return true;
 169     else if (preorder[ABlock] > preorder[BBlock])
 170       return false;
 171
 172     assert(0 && "Error sorting by dominance!");
 173     return false;
 174   }
 175 };
 176
 177 /// computeDomForest - compute the subforest of the DomTree corresponding
 178 /// to the defining blocks of the registers in question
 179 std::vector<StrongPHIElimination::DomForestNode*>
 180 StrongPHIElimination::computeDomForest(std::set<unsigned>& regs) {
 181   LiveVariables& LV = getAnalysis<LiveVariables>();
 182
 183   DomForestNode* VirtualRoot = new DomForestNode(0, 0);
 184   maxpreorder.insert(std::make_pair((MachineBasicBlock*)0, ~0UL));
 185
 186   std::vector<unsigned> worklist;
 187   worklist.reserve(regs.size());
 188   for (std::set<unsigned>::iterator I = regs.begin(), E = regs.end();
 189        I != E; ++I)
 190     worklist.push_back(*I);
 191
 192   PreorderSorter PS(preorder, LV);
 193   std::sort(worklist.begin(), worklist.end(), PS);
 194
 195   DomForestNode* CurrentParent = VirtualRoot;
 196   std::vector<DomForestNode*> stack;
 197   stack.push_back(VirtualRoot);
 198
 199   for (std::vector<unsigned>::iterator I = worklist.begin(), E = worklist.end();
 200        I != E; ++I) {
 201     unsigned pre = preorder[LV.getVarInfo(*I).DefInst->getParent()];
 202     MachineBasicBlock* parentBlock =
 203       LV.getVarInfo(CurrentParent->getReg()).DefInst->getParent();
 204
 205     while (pre > maxpreorder[parentBlock]) {
 206       stack.pop_back();
 207       CurrentParent = stack.back();
 208
 209       parentBlock = LV.getVarInfo(CurrentParent->getReg()).DefInst->getParent();
 210     }
 211
 212     DomForestNode* child = new DomForestNode(*I, CurrentParent);
 213     stack.push_back(child);
 214     CurrentParent = child;
 215   }
 216
 217   std::vector<DomForestNode*> ret;
 218   ret.insert(ret.end(), VirtualRoot->begin(), VirtualRoot->end());
 219   return ret;
 220 }
 221
 222 /// processPHI - Eliminate the given PHI node
 223 void StrongPHIElimination::processPHI(MachineInstr* P) {
 224
 225 }
 226
 227 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
 228   computeDFS(Fn);
 229
 230   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
 231     for (MachineBasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;
 232          ++BI) {
 233       if (BI->getOpcode() == TargetInstrInfo::PHI)
 234         processPHI(BI);
 235       else
 236         break;
 237     }
 238   }
 239
 240   return false;
 241 }