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/MachineDominators.h"
  25 #include "llvm/CodeGen/MachineFunctionPass.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/Support/Compiler.h"
  31 using namespace llvm;
  32
  33
  34 namespace {
  35   struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass {
  36     static char ID; // Pass identification, replacement for typeid
  37     StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
  38
  39     bool runOnMachineFunction(MachineFunction &Fn) {
  40       computeDFS(Fn);
  41
  42
  43       return false;
  44     }
  45
  46     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  47       AU.addRequired<MachineDominatorTree>();
  48       MachineFunctionPass::getAnalysisUsage(AU);
  49     }
  50
  51     virtual void releaseMemory() {
  52       preorder.clear();
  53       maxpreorder.clear();
  54     }
  55
  56   private:
  57     DenseMap<MachineBasicBlock*, unsigned> preorder;
  58     DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
  59
  60     void computeDFS(MachineFunction& MF);
  61   };
  62
  63   char StrongPHIElimination::ID = 0;
  64   RegisterPass<StrongPHIElimination> X("strong-phi-node-elimination",
  65                   "Eliminate PHI nodes for register allocation, intelligently");
  66 }
  67
  68 const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo();
  69
  70 /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
  71 /// of the given MachineFunction.  These numbers are then used in other parts
  72 /// of the PHI elimination process.
  73 void StrongPHIElimination::computeDFS(MachineFunction& MF) {
  74   SmallPtrSet<MachineDomTreeNode*, 8> frontier;
  75   SmallPtrSet<MachineDomTreeNode*, 8> visited;
  76
  77   unsigned time = 0;
  78
  79   MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
  80
  81   MachineDomTreeNode* node = DT.getRootNode();
  82
  83   std::vector<MachineDomTreeNode*> worklist;
  84   worklist.push_back(node);
  85
  86   while (!worklist.empty()) {
  87     MachineDomTreeNode* currNode = worklist.back();
  88
  89     if (!frontier.count(currNode)) {
  90       frontier.insert(currNode);
  91       ++time;
  92       preorder.insert(std::make_pair(currNode->getBlock(), time));
  93     }
  94
  95     bool inserted = false;
  96     for (MachineDomTreeNode::iterator I = node->begin(), E = node->end();
  97          I != E; ++I)
  98       if (!frontier.count(*I) && !visited.count(*I)) {
  99         worklist.push_back(*I);
 100         inserted = true;
 101         break;
 102       }
 103
 104     if (!inserted) {
 105       frontier.erase(currNode);
 106       visited.insert(currNode);
 107       maxpreorder.insert(std::make_pair(currNode->getBlock(), time));
 108
 109       worklist.pop_back();
 110     }
 111   }
 112 }