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 PHI instructions by aggressively coalescing the copies
// that would be inserted by a naive algorithm and only inserting the copies
// that are necessary. The coalescing technique initially assumes that all
// registers appearing in a PHI instruction do not interfere. It then eliminates
// proven interferences, using dominators to only perform a linear number of
// interference tests instead of the quadratic number of interference tests
// that this would naively require. This is a technique 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.
//
// The original implementation constructs a data structure they call a dominance
// forest for this purpose. The dominance forest was shown to be unnecessary,
// as it is possible to emulate the creation and traversal of a dominance forest
// by directly using the dominator tree, rather than actually constructing the
// dominance forest.  This technique is explained in:
//
//   Boissinot, et al. Revisiting Out-of-SSA Translation for Correctness, Code
//     Quality and Efficiency,
//   In Proceedings of the 7th annual IEEE/ACM International Symposium on Code
//   Generation and Optimization (Seattle, Washington, March 22 - 25, 2009).
//   CGO '09. IEEE, Washington, DC, 114-125.
//
// Careful implementation allows for all of the dominator forest interference
// checks to be performed at once in a single depth-first traversal of the
// dominator tree, which is what is implemented here.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "strongphielim"
#include "PHIEliminationUtils.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
using namespace llvm;

namespace {
  class StrongPHIElimination : public MachineFunctionPass {
  public:
    static char ID; // Pass identification, replacement for typeid
    StrongPHIElimination() : MachineFunctionPass(ID) {
      initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
    }

    virtual void getAnalysisUsage(AnalysisUsage&) const;
    bool runOnMachineFunction(MachineFunction&);

  private:
    /// This struct represents a single node in the union-find data structure
    /// representing the variable congruence classes. There is one difference
    /// from a normal union-find data structure. We steal two bits from the parent
    /// pointer . One of these bits is used to represent whether the register
    /// itself has been isolated, and the other is used to represent whether the
    /// PHI with that register as its destination has been isolated.
    ///
    /// Note that this leads to the strange situation where the leader of a
    /// congruence class may no longer logically be a member, due to being
    /// isolated.
    struct Node {
      enum Flags {
        kRegisterIsolatedFlag = 1,
        kPHIIsolatedFlag = 2
      };
      Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); }

      Node *getLeader();

      PointerIntPair<Node*, 2> parent;
      unsigned value;
      unsigned rank;
    };

    /// Add a register in a new congruence class containing only itself.
    void addReg(unsigned);

    /// Join the congruence classes of two registers. This function is biased
    /// towards the left argument, i.e. after
    ///
    /// addReg(r2);
    /// unionRegs(r1, r2);
    ///
    /// the leader of the unioned congruence class is the same as the leader of
    /// r1's congruence class prior to the union. This is actually relied upon
    /// in the copy insertion code.
    void unionRegs(unsigned, unsigned);

    /// Get the color of a register. The color is 0 if the register has been
    /// isolated.
    unsigned getRegColor(unsigned);

    // Isolate a register.
    void isolateReg(unsigned);

    /// Get the color of a PHI. The color of a PHI is 0 if the PHI has been
    /// isolated. Otherwise, it is the original color of its destination and
    /// all of its operands (before they were isolated, if they were).
    unsigned getPHIColor(MachineInstr*);

    /// Isolate a PHI.
    void isolatePHI(MachineInstr*);

    /// Traverses a basic block, splitting any interferences found between
    /// registers in the same congruence class. It takes two DenseMaps as
    /// arguments that it also updates: CurrentDominatingParent, which maps
    /// a color to the register in that congruence class whose definition was
    /// most recently seen, and ImmediateDominatingParent, which maps a register
    /// to the register in the same congruence class that most immediately
    /// dominates it.
    ///
    /// This function assumes that it is being called in a depth-first traversal
    /// of the dominator tree.
    void SplitInterferencesForBasicBlock(
      MachineBasicBlock&,
      DenseMap<unsigned, unsigned> &CurrentDominatingParent,
      DenseMap<unsigned, unsigned> &ImmediateDominatingParent);

    // Lowers a PHI instruction, inserting copies of the source and destination
    // registers as necessary.
    void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);

    // Merges the live interval of Reg into NewReg and renames Reg to NewReg
    // everywhere that Reg appears. Requires Reg and NewReg to have non-
    // overlapping lifetimes.
    void MergeLIsAndRename(unsigned Reg, unsigned NewReg);

    MachineRegisterInfo *MRI;
    const TargetInstrInfo *TII;
    MachineDominatorTree *DT;
    LiveIntervals *LI;

    BumpPtrAllocator Allocator;

    DenseMap<unsigned, Node*> RegNodeMap;

    // Maps a basic block to a list of its defs of registers that appear as PHI
    // sources.
    DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > PHISrcDefs;

    // Maps a color to a pair of a MachineInstr* and a virtual register, which
    // is the operand of that PHI corresponding to the current basic block.
    DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;

    // FIXME: Can these two data structures be combined? Would a std::multimap
    // be any better?

    // Stores pairs of predecessor basic blocks and the source registers of
    // inserted copy instructions.
    typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > SrcCopySet;
    SrcCopySet InsertedSrcCopySet;

    // Maps pairs of predecessor basic blocks and colors to their defining copy
    // instructions.
    typedef DenseMap<std::pair<MachineBasicBlock*, unsigned>, MachineInstr*>
      SrcCopyMap;
    SrcCopyMap InsertedSrcCopyMap;

    // Maps inserted destination copy registers to their defining copy
    // instructions.
    typedef DenseMap<unsigned, MachineInstr*> DestCopyMap;
    DestCopyMap InsertedDestCopies;
  };

  struct MIIndexCompare {
    MIIndexCompare(LiveIntervals *LiveIntervals) : LI(LiveIntervals) { }

    bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
      return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS);
    }

    LiveIntervals *LI;
  };
} // namespace

STATISTIC(NumPHIsLowered, "Number of PHIs lowered");
STATISTIC(NumDestCopiesInserted, "Number of destination copies inserted");
STATISTIC(NumSrcCopiesInserted, "Number of source copies inserted");

char StrongPHIElimination::ID = 0;
INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
  "Eliminate PHI nodes for register allocation, intelligently", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
  "Eliminate PHI nodes for register allocation, intelligently", false, false)

char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;

void StrongPHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesCFG();
  AU.addRequired<MachineDominatorTree>();
  AU.addRequired<SlotIndexes>();
  AU.addPreserved<SlotIndexes>();
  AU.addRequired<LiveIntervals>();
  AU.addPreserved<LiveIntervals>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

static MachineOperand *findLastUse(MachineBasicBlock *