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       computeDFS(Fn);
  42
  43
  44       return false;
  45     }
  46
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       AU.addPreserved<LiveVariables>();
  49       AU.addPreservedID(PHIEliminationID);
  50       AU.addRequired<MachineDominatorTree>();
  51       MachineFunctionPass::getAnalysisUsage(AU);
  52     }
  53
  54     virtual void releaseMemory() {
  55       preorder.clear();
  56       maxpreorder.clear();
  57     }
  58
  59   private:
  60     struct DomForestNode {
  61     private:
  62       std::vector<DomForestNode*> children;
  63       MachineInstr* instr;
  64
  65       void addChild(DomForestNode* DFN) { children.push_back(DFN); }
  66
  67     public:
  68       typedef std::vector<DomForestNode*>::iterator iterator;
  69
  70       DomForestNode(MachineInstr* MI, DomForestNode* parent) : instr(MI) {
  71         if (parent)
  72           parent->addChild(this);
  73       }
  74
  75       MachineInstr* getInstr() { return instr; }
  76
  77       DomForestNode::iterator begin() { return children.begin(); }
  78       DomForestNode::iterator end() { return children.end(); }
  79     };
  80
  81     DenseMap<MachineBasicBlock*, unsigned> preorder;
  82     DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
  83
  84     void computeDFS(MachineFunction& MF);
  85
  86     std::vector<DomForestNode*>
  87       computeDomForest(SmallPtrSet<MachineInstr*, 8>& instrs);
  88
  89   };
  90
  91   char StrongPHIElimination::ID = 0;
  92   RegisterPass<StrongPHIElimination> X("strong-phi-node-elimination",
  93                   "Eliminate PHI nodes for register allocation, intelligently");
  94 }
  95
  96 const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo();
  97
  98 /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
  99 /// of the given MachineFunction.  These numbers are then used in other parts
 100 /// of the PHI elimination process.
 101 void StrongPHIElimination::computeDFS(MachineFunction& MF) {
 102   SmallPtrSet<MachineDomTreeNode*, 8> frontier;
 103   SmallPtrSet<MachineDomTreeNode*, 8> visited;
 104
 105   unsigned time = 0;
 106
 107   MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
 108
 109   MachineDomTreeNode* node = DT.getRootNode();
 110
 111   std::vector<MachineDomTreeNode*> worklist;
 112   worklist.push_back(node);
 113
 114   while (!worklist.empty()) {
 115     MachineDomTreeNode* currNode = worklist.back();
 116
 117     if (!frontier.count(currNode)) {
 118       frontier.insert(currNode);
 119       ++time;
 120       preorder.insert(std::make_pair(currNode->getBlock(), time));
 121     }
 122
 123     bool inserted = false;
 124     for (MachineDomTreeNode::iterator I = node->begin(), E = node->end();
 125          I != E; ++I)
 126       if (!frontier.count(*I) && !visited.count(*I)) {
 127         worklist.push_back(*I);
 128         inserted = true;
 129         break;
 130       }
 131
 132     if (!inserted) {
 133       frontier.erase(currNode);
 134       visited.insert(currNode);
 135       maxpreorder.insert(std::make_pair(currNode->getBlock(), time));
 136
 137       worklist.pop_back();
 138     }
 139   }
 140 }
 141
 142 class PreorderSorter {
 143 private:
 144   DenseMap<MachineBasicBlock*, unsigned>& preorder;
 145
 146 public:
 147   PreorderSorter(DenseMap<MachineBasicBlock*, unsigned>& p) : preorder(p) { }
 148
 149   bool operator()(MachineInstr* A, MachineInstr* B) {
 150     if (A == B)
 151       return false;
 152
 153     if (preorder[A->getParent()] < preorder[B->getParent()])
 154       return true;
 155     else if (preorder[A->getParent()] > preorder[B->getParent()])
 156       return false;
 157
 158     if (A->getOpcode() == TargetInstrInfo::PHI &&
 159         B->getOpcode() == TargetInstrInfo::PHI)
 160       return A < B;
 161
 162     MachineInstr* begin = A->getParent()->begin();
 163     return std::distance(begin, A) < std::distance(begin, B);
 164   }
 165 };
 166
 167 std::vector<StrongPHIElimination::DomForestNode*>
 168 StrongPHIElimination::computeDomForest(SmallPtrSet<MachineInstr*, 8>& instrs) {
 169   DomForestNode* VirtualRoot = new DomForestNode(0, 0);
 170   maxpreorder.insert(std::make_pair((MachineBasicBlock*)0, ~0UL));
 171
 172   std::vector<MachineInstr*> worklist;
 173   worklist.reserve(instrs.size());
 174   for (SmallPtrSet<MachineInstr*, 8>::iterator I = instrs.begin(),
 175        E = instrs.end(); I != E; ++I)
 176     worklist.push_back(*I);
 177   PreorderSorter PS(preorder);
 178   std::sort(worklist.begin(), worklist.end(), PS);
 179
 180   DomForestNode* CurrentParent = VirtualRoot;
 181   std::vector<DomForestNode*> stack;
 182   stack.push_back(VirtualRoot);
 183
 184   for (std::vector<MachineInstr*>::iterator I = worklist.begin(),
 185        E = worklist.end(); I != E; ++I) {
 186     while (preorder[(*I)->getParent()] >
 187            maxpreorder[CurrentParent->getInstr()->getParent()]) {
 188       stack.pop_back();
 189       CurrentParent = stack.back();
 190     }
 191
 192     DomForestNode* child = new DomForestNode(*I, CurrentParent);
 193     stack.push_back(child);
 194     CurrentParent = child;
 195   }
 196
 197   std::vector<DomForestNode*> ret;
 198   ret.insert(ret.end(), VirtualRoot->begin(), VirtualRoot->end());
 199   return ret;
 200 }