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/BreakCriticalMachineEdge.h"
  25 #include "llvm/CodeGen/LiveVariables.h"
  26 #include "llvm/CodeGen/MachineDominators.h"
  27 #include "llvm/CodeGen/MachineFunctionPass.h"
  28 #include "llvm/CodeGen/MachineInstr.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/Support/Compiler.h"
  33 using namespace llvm;
  34
  35
  36 namespace {
  37   struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass {
  38     static char ID; // Pass identification, replacement for typeid
  39     StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
  40
  41     bool runOnMachineFunction(MachineFunction &Fn);
  42
  43     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  44       AU.addPreserved<LiveVariables>();
  45       AU.addPreservedID(PHIEliminationID);
  46       AU.addRequired<MachineDominatorTree>();
  47       AU.addRequired<LiveVariables>();
  48       AU.setPreservesAll();
  49       MachineFunctionPass::getAnalysisUsage(AU);
  50     }
  51
  52     virtual void releaseMemory() {
  53       preorder.clear();
  54       maxpreorder.clear();
  55
  56       waiting.clear();
  57     }
  58
  59   private:
  60     struct DomForestNode {
  61     private:
  62       std::vector<DomForestNode*> children;
  63       unsigned reg;
  64
  65       void addChild(DomForestNode* DFN) { children.push_back(DFN); }
  66
  67     public:
  68       typedef std::vector<DomForestNode*>::iterator iterator;
  69
  70       DomForestNode(unsigned r, DomForestNode* parent) : reg(r) {
  71         if (parent)
  72           parent->addChild(this);
  73       }
  74
  75       ~DomForestNode() {
  76         for (iterator I = begin(), E = end(); I != E; ++I)
  77           delete *I;
  78       }
  79
  80       inline unsigned getReg() { return reg; }
  81
  82       inline DomForestNode::iterator begin() { return children.begin(); }
  83       inline DomForestNode::iterator end() { return children.end(); }
  84     };
  85
  86     DenseMap<MachineBasicBlock*, unsigned> preorder;
  87     DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
  88
  89     DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > waiting;
  90
  91
  92     void computeDFS(MachineFunction& MF);
  93     void processBlock(MachineBasicBlock* MBB);
  94
  95     std::vector<DomForestNode*> computeDomForest(std::set<unsigned>& instrs);
  96
  97   };
  98
  99   char StrongPHIElimination::ID = 0;
 100   RegisterPass<StrongPHIElimination> X("strong-phi-node-elimination",
 101                   "Eliminate PHI nodes for register allocation, intelligently");
 102 }
 103
 104 const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo();
 105
 106 /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
 107 /// of the given MachineFunction.  These numbers are then used in other parts
 108 /// of the PHI elimination process.
 109 void StrongPHIElimination::computeDFS(MachineFunction& MF) {
 110   SmallPtrSet<MachineDomTreeNode*, 8> frontier;
 111   SmallPtrSet<MachineDomTreeNode*, 8> visited;
 112
 113   unsigned time = 0;
 114
 115   MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
 116
 117   MachineDomTreeNode* node = DT.getRootNode();
 118
 119   std::vector<MachineDomTreeNode*> worklist;
 120   worklist.push_back(node);
 121
 122   while (!worklist.empty()) {
 123     MachineDomTreeNode* currNode = worklist.back();
 124
 125     if (!frontier.count(currNode)) {
 126       frontier.insert(currNode);
 127       ++time;
 128       preorder.insert(std::make_pair(currNode->getBlock(), time));
 129     }
 130
 131     bool inserted = false;
 132     for (MachineDomTreeNode::iterator I = node->begin(), E = node->end();
 133          I != E; ++I)
 134       if (!frontier.count(*I) && !visited.count(*I)) {
 135         worklist.push_back(*I);
 136         inserted = true;
 137         break;
 138       }
 139
 140     if (!inserted) {
 141       frontier.erase(currNode);
 142       visited.insert(currNode);
 143       maxpreorder.insert(std::make_pair(currNode->getBlock(), time));
 144
 145       worklist.pop_back();
 146     }
 147   }
 148 }
 149
 150 /// PreorderSorter - a helper class that is used to sort registers
 151 /// according to the preorder number of their defining blocks
 152 class PreorderSorter {
 153 private:
 154   DenseMap<MachineBasicBlock*, unsigned>& preorder;
 155   LiveVariables& LV;
 156
 157 public:
 158   PreorderSorter(DenseMap<MachineBasicBlock*, unsigned>& p,
 159                 LiveVariables& L) : preorder(p), LV(L) { }
 160
 161   bool operator()(unsigned A, unsigned B) {
 162     if (A == B)
 163       return false;
 164
 165     MachineBasicBlock* ABlock = LV.getVarInfo(A).DefInst->getParent();
 166     MachineBasicBlock* BBlock = LV.getVarInfo(A).DefInst->getParent();
 167
 168     if (preorder[ABlock] < preorder[BBlock])
 169       return true;
 170     else if (preorder[ABlock] > preorder[BBlock])
 171       return false;
 172
 173     assert(0 && "Error sorting by dominance!");
 174     return false;
 175   }
 176 };
 177
 178 /// computeDomForest - compute the subforest of the DomTree corresponding
 179 /// to the defining blocks of the registers in question
 180 std::vector<StrongPHIElimination::DomForestNode*>
 181 StrongPHIElimination::computeDomForest(std::set<unsigned>& regs) {
 182   LiveVariables& LV = getAnalysis<LiveVariables>();
 183
 184   DomForestNode* VirtualRoot = new DomForestNode(0, 0);
 185   maxpreorder.insert(std::make_pair((MachineBasicBlock*)0, ~0UL));
 186
 187   std::vector<unsigned> worklist;
 188   worklist.reserve(regs.size());
 189   for (std::set<unsigned>::iterator I = regs.begin(), E = regs.end();
 190        I != E; ++I)
 191     worklist.push_back(*I);
 192
 193   PreorderSorter PS(preorder, LV);
 194   std::sort(worklist.begin(), worklist.end(), PS);
 195
 196   DomForestNode* CurrentParent = VirtualRoot;
 197   std::vector<DomForestNode*> stack;
 198   stack.push_back(VirtualRoot);
 199
 200   for (std::vector<unsigned>::iterator I = worklist.begin(), E = worklist.end();
 201        I != E; ++I) {
 202     unsigned pre = preorder[LV.getVarInfo(*I).DefInst->getParent()];
 203     MachineBasicBlock* parentBlock =
 204       LV.getVarInfo(CurrentParent->getReg()).DefInst->getParent();
 205
 206     while (pre > maxpreorder[parentBlock]) {
 207       stack.pop_back();
 208       CurrentParent = stack.back();
 209
 210       parentBlock = LV.getVarInfo(CurrentParent->getReg()).DefInst->getParent();
 211     }
 212
 213     DomForestNode* child = new DomForestNode(*I, CurrentParent);
 214     stack.push_back(child);
 215     CurrentParent = child;
 216   }
 217
 218   std::vector<DomForestNode*> ret;
 219   ret.insert(ret.end(), VirtualRoot->begin(), VirtualRoot->end());
 220   return ret;
 221 }
 222
 223 /// isLiveIn - helper method that determines, from a VarInfo, if a register
 224 /// is live into a block
 225 bool isLiveIn(LiveVariables::VarInfo& V, MachineBasicBlock* MBB) {
 226   if (V.AliveBlocks.test(MBB->getNumber()))
 227     return true;
 228
 229   if (V.DefInst->getParent() != MBB &&
 230       V.UsedBlocks.test(MBB->getNumber()))
 231     return true;
 232
 233   return false;
 234 }
 235
 236 /// isLiveOut - help method that determines, from a VarInfo, if a register is
 237 /// live out of a block.
 238 bool isLiveOut(LiveVariables::VarInfo& V, MachineBasicBlock* MBB) {
 239   if (MBB == V.DefInst->getParent() ||
 240       V.UsedBlocks.test(MBB->getNumber())) {
 241     for (std::vector<MachineInstr*>::iterator I = V.Kills.begin(),
 242          E = V.Kills.end(); I != E; ++I)
 243       if ((*I)->getParent() == MBB)
 244         return false;
 245
 246     return true;
 247   }
 248
 249   return false;
 250 }
 251
 252 /// processBlock - Eliminate PHIs in the given block
 253 void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
 254   LiveVariables& LV = getAnalysis<LiveVariables>();
 255
 256   // Holds names that have been added to a set in any PHI within this block
 257   // before the current one.
 258   std::set<unsigned> ProcessedNames;
 259
 260   MachineBasicBlock::iterator P = MBB->begin();
 261   while (P->getOpcode() == TargetInstrInfo::PHI) {
 262     LiveVariables::VarInfo& PHIInfo = LV.getVarInfo(P->getOperand(0).getReg());
 263
 264     // Hold the names that are currently in the candidate set.
 265     std::set<unsigned> PHIUnion;
 266     std::set<MachineBasicBlock*> UnionedBlocks;
 267
 268     for (int i = P->getNumOperands() - 1; i >= 2; i-=2) {
 269       unsigned SrcReg = P->getOperand(i-1).getReg();
 270       LiveVariables::VarInfo& SrcInfo = LV.getVarInfo(SrcReg);
 271
 272       if (isLiveIn(SrcInfo, P->getParent())) {
 273         // add a copy from a_i to p in Waiting[From[a_i]]
 274       } else if (isLiveOut(PHIInfo, SrcInfo.DefInst->getParent())) {
 275         // add a copy to Waiting[From[a_i]]
 276       } else if (PHIInfo.DefInst->getOpcode() == TargetInstrInfo::PHI &&
 277                  isLiveIn(PHIInfo, SrcInfo.DefInst->getParent())) {
 278         // add a copy to Waiting[From[a_i]]
 279       } else if (ProcessedNames.count(SrcReg)) {
 280         // add a copy to Waiting[From[a_i]]
 281       } else if (UnionedBlocks.count(SrcInfo.DefInst->getParent())) {
 282         // add a copy to Waiting[From[a_i]]
 283       } else {
 284         PHIUnion.insert(SrcReg);
 285         UnionedBlocks.insert(SrcInfo.DefInst->getParent());
 286
 287         // DO STUFF HERE
 288
 289       }
 290
 291       ProcessedNames.insert(PHIUnion.begin(), PHIUnion.end());
 292     }
 293
 294     ++P;
 295   }
 296 }
 297
 298 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
 299   computeDFS(Fn);
 300
 301   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 302     if (!I->empty() &&
 303         I->begin()->getOpcode() == TargetInstrInfo::PHI)
 304       processBlock(I);
 305
 306   return false;
 307 }