path: root/utils/TableGen/CodeGenRegisters.h

//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines structures to encapsulate information gleaned from the
// target register and register class definitions.
//
//===----------------------------------------------------------------------===//

#ifndef CODEGEN_REGISTERS_H
#define CODEGEN_REGISTERS_H

#include "SetTheory.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/TableGen/Record.h"
#include <cstdlib>
#include <map>
#include <set>
#include <string>
#include <vector>

namespace llvm {
  class CodeGenRegBank;

  /// CodeGenSubRegIndex - Represents a sub-register index.
  class CodeGenSubRegIndex {
    Record *const TheDef;
    std::string Name;
    std::string Namespace;

  public:
    const unsigned EnumValue;
    unsigned LaneMask;

    CodeGenSubRegIndex(Record *R, unsigned Enum);
    CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum);

    const std::string &getName() const { return Name; }
    const std::string &getNamespace() const { return Namespace; }
    std::string getQualifiedName() const;

    // Order CodeGenSubRegIndex pointers by EnumValue.
    struct Less {
      bool operator()(const CodeGenSubRegIndex *A,
                      const CodeGenSubRegIndex *B) const {
        assert(A && B);
        return A->EnumValue < B->EnumValue;
      }
    };

    // Map of composite subreg indices.
    typedef std::map<CodeGenSubRegIndex*, CodeGenSubRegIndex*, Less> CompMap;

    // Returns the subreg index that results from composing this with Idx.
    // Returns NULL if this and Idx don't compose.
    CodeGenSubRegIndex *compose(CodeGenSubRegIndex *Idx) const {
      CompMap::const_iterator I = Composed.find(Idx);
      return I == Composed.end() ? 0 : I->second;
    }

    // Add a composite subreg index: this+A = B.
    // Return a conflicting composite, or NULL
    CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A,
                                     CodeGenSubRegIndex *B) {
      assert(A && B);
      std::pair<CompMap::iterator, bool> Ins =
        Composed.insert(std::make_pair(A, B));
      return (Ins.second || Ins.first->second == B) ? 0 : Ins.first->second;
    }

    // Update the composite maps of components specified in 'ComposedOf'.
    void updateComponents(CodeGenRegBank&);

    // Return the map of composites.
    const CompMap &getComposites() const { return Composed; }

    // Compute LaneMask from Composed. Return LaneMask.
    unsigned computeLaneMask();

  private:
    CompMap Composed;
  };

  /// CodeGenRegister - Represents a register definition.
  struct CodeGenRegister {
    Record *TheDef;
    unsigned EnumValue;
    unsigned CostPerUse;
    bool CoveredBySubRegs;

    // Map SubRegIndex -> Register.
    typedef std::map<CodeGenSubRegIndex*, CodeGenRegister*,
                     CodeGenSubRegIndex::Less> SubRegMap;

    CodeGenRegister(Record *R, unsigned Enum);

    const std::string &getName() const;

    // Extract more information from TheDef. This is used to build an object
    // graph after all CodeGenRegister objects have been created.
    void buildObjectGraph(CodeGenRegBank&);

    // Lazily compute a map of all sub-registers.
    // This includes unique entries for all sub-sub-registers.
    const SubRegMap &computeSubRegs(CodeGenRegBank&);

    // Compute extra sub-registers by combining the existing sub-registers.
    void computeSecondarySubRegs(CodeGenRegBank&);

    // Add this as a super-register to all sub-registers after the sub-register
    // graph has been built.
    void computeSuperRegs(CodeGenRegBank&);

    const SubRegMap &getSubRegs() const {
      assert(SubRegsComplete && "Must precompute sub-registers");
      return SubRegs;
    }

    // Add sub-registers to OSet following a pre-order defined by the .td file.
    void addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
                            CodeGenRegBank&) const;

    // Return the sub-register index naming Reg as a sub-register of this
    // register. Returns NULL if Reg is not a sub-register.
    CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const {
      return SubReg2Idx.lookup(Reg);
    }

    typedef std::vector<const CodeGenRegister*> SuperRegList;

    // Get the list of super-registers in topological order, small to large.
    // This is valid after computeSubRegs visits all registers during RegBank
    // construction.
    const SuperRegList &getSuperRegs() const {
      assert(SubRegsComplete && "Must precompute sub-registers");
      return SuperRegs;
    }

    // Get the list of ad hoc aliases. The graph is symmetric, so the list
    // contains all registers in 'Aliases', and all registers that mention this
    // register in 'Aliases'.
    ArrayRef<CodeGenRegister*> getExplicitAliases() const {
      return ExplicitAliases;
    }

    // Get the topological signature of this register. This is a small integer
    // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have
    // identical sub-register structure. That is, they support the same set of
    // sub-register indices mapping to the same kind of sub-registers
    // (TopoSig-wise).
    unsigned getTopoSig() const {
      assert(SuperRegsComplete && "TopoSigs haven't been computed yet.");
      return TopoSig;
    }

    // List of register units in ascending order.
    typedef SmallVector<unsigned, 16> RegUnitList;

    // How many entries in RegUnitList are native?
    unsigned NumNativeRegUnits;

    // Get the list of register units.
    // This is only valid after computeSubRegs() completes.
    const RegUnitList &getRegUnits() const { return RegUnits; }

    // Get the native register units. This is a prefix of getRegUnits().
    ArrayRef<unsigned> getNativeRegUnits() const {
      return makeArrayRef(RegUnits).slice(0, NumNativeRegUnits);
    }

    // Inherit register units from subregisters.
    // Return true if the RegUnits changed.
    bool inheritRegUnits(CodeGenRegBank &RegBank);

    // Adopt a register unit for pressure tracking.
    // A unit is adopted iff its unit number is >= NumNativeRegUnits.
    void adoptRegUnit(unsigned RUID) { RegUnits.push_back(RUID); }

    // Get the sum of this register's register unit weights.
    unsigned getWeight(const CodeGenRegBank &RegBank) const;

    // Order CodeGenRegister pointers by EnumValue.
    struct Less {
      bool operator()(const CodeGenRegister *A,
                      const CodeGenRegister *B) const {
        assert(A && B);
        return A->EnumValue < B->EnumValue;
      }
    };

    // Canonically ordered set.
    typedef std::set<const CodeGenRegister*, Less> Set;

    // Compute the set of registers overlapping this.
    void computeOverlaps(Set &Overlaps, const CodeGenRegBank&) const;

  private:
    bool SubRegsComplete;
    bool SuperRegsComplete;
    unsigned TopoSig;

    // The sub-registers explicit in the .td file form a tree.
    SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices;
    SmallVector<CodeGenRegister*, 8> ExplicitSubRegs;

    // Explicit ad hoc aliases, symmetrized to form an undirected graph.
    SmallVector<CodeGenRegister*, 8> ExplicitAliases;

    // Super-registers where this is the first explicit sub-register.
    SuperRegList LeadingSuperRegs;

    SubRegMap SubRegs;
    SuperRegList SuperRegs;
    DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx;
    RegUnitList RegUnits;
  };


  class CodeGenRegisterClass {
    CodeGenRegister::Set Members;
    // Allocation orders. Order[0] always contains all registers in Members.
    std::vector<SmallVector<Record*, 16> > Orders;
    // Bit mask of sub-classes including this, indexed by their EnumValue.
    BitVector SubClasses;