path: root/lib/CodeGen/StrongPHIElimination.cpp

//===- StrongPhiElimination.cpp - Eliminate PHI nodes by inserting copies -===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass eliminates machine instruction PHI nodes by inserting copy
// instructions, using an intelligent copy-folding technique based on
// dominator information.  This is technique is derived from:
// 
//    Budimlic, et al. Fast copy coalescing and live-range identification.
//    In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
//    Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
//    PLDI '02. ACM, New York, NY, 25-32.
//    DOI= http://doi.acm.org/10.1145/512529.512534
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "strongphielim"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
using namespace llvm;

namespace {
  struct StrongPHIElimination : public MachineFunctionPass {
    static char ID; // Pass identification, replacement for typeid
    StrongPHIElimination() : MachineFunctionPass(&ID) {}

    // Waiting stores, for each MBB, the set of copies that need to
    // be inserted into that MBB
    DenseMap<MachineBasicBlock*,
             std::multimap<unsigned, unsigned> > Waiting;
    
    // Stacks holds the renaming stack for each register
    std::map<unsigned, std::vector<unsigned> > Stacks;
    
    // Registers in UsedByAnother are PHI nodes that are themselves
    // used as operands to another PHI node
    std::set<unsigned> UsedByAnother;
    
    // RenameSets are the is a map from a PHI-defined register
    // to the input registers to be coalesced along with the 
    // predecessor block for those input registers.
    std::map<unsigned, std::map<unsigned, MachineBasicBlock*> > RenameSets;
    
    // PhiValueNumber holds the ID numbers of the VNs for each phi that we're
    // eliminating, indexed by the register defined by that phi.
    std::map<unsigned, unsigned> PhiValueNumber;

    // Store the DFS-in number of each block
    DenseMap<MachineBasicBlock*, unsigned> preorder;
    
    // Store the DFS-out number of each block
    DenseMap<MachineBasicBlock*, unsigned> maxpreorder;

    bool runOnMachineFunction(MachineFunction &Fn);
    
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      AU.addRequired<MachineDominatorTree>();
      AU.addRequired<SlotIndexes>();
      AU.addPreserved<SlotIndexes>();
      AU.addRequired<LiveIntervals>();
      
      // TODO: Actually make this true.
      AU.addPreserved<LiveIntervals>();
      AU.addPreserved<RegisterCoalescer>();
      MachineFunctionPass::getAnalysisUsage(AU);
    }
    
    virtual void releaseMemory() {
      preorder.clear();
      maxpreorder.clear();
      
      Waiting.clear();
      Stacks.clear();
      UsedByAnother.clear();
      RenameSets.clear();
    }

  private:
    
    /// DomForestNode - Represents a node in the "dominator forest".  This is
    /// a forest in which the nodes represent registers and the edges
    /// represent a dominance relation in the block defining those registers.
    struct DomForestNode {
    private:
      // Store references to our children
      std::vector<DomForestNode*> children;
      // The register we represent
      unsigned reg;
      
      // Add another node as our child
      void addChild(DomForestNode* DFN) { children.push_back(DFN); }
      
    public:
      typedef std::vector<DomForestNode*>::iterator iterator;
      
      // Create a DomForestNode by providing the register it represents, and
      // the node to be its parent.  The virtual root node has register 0
      // and a null parent.
      DomForestNode(unsigned r, DomForestNode* parent) : reg(r) {
        if (parent)
          parent->addChild(this);
      }
      
      ~DomForestNode() {
        for (iterator I = begin(), E = end(); I != E; ++I)
          delete *I;
      }
      
      /// getReg - Return the regiser that this node represents
      inline unsigned getReg() { return reg; }
      
      // Provide iterator access to our children
      inline DomForestNode::iterator begin() { return children.begin(); }
      inline DomForestNode::iterator end() { return children.end(); }
    };
    
    void computeDFS(MachineFunction& MF);
    void processBlock(MachineBasicBlock* MBB);
    
    std