Line data    Source code

       1             : //===- RegAllocBase.h - basic regalloc interface and driver -----*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the RegAllocBase class, which is the skeleton of a basic
      11             : // register allocation algorithm and interface for extending it. It provides the
      12             : // building blocks on which to construct other experimental allocators and test
      13             : // the validity of two principles:
      14             : //
      15             : // - If virtual and physical register liveness is modeled using intervals, then
      16             : // on-the-fly interference checking is cheap. Furthermore, interferences can be
      17             : // lazily cached and reused.
      18             : //
      19             : // - Register allocation complexity, and generated code performance is
      20             : // determined by the effectiveness of live range splitting rather than optimal
      21             : // coloring.
      22             : //
      23             : // Following the first principle, interfering checking revolves around the
      24             : // LiveIntervalUnion data structure.
      25             : //
      26             : // To fulfill the second principle, the basic allocator provides a driver for
      27             : // incremental splitting. It essentially punts on the problem of register
      28             : // coloring, instead driving the assignment of virtual to physical registers by
      29             : // the cost of splitting. The basic allocator allows for heuristic reassignment
      30             : // of registers, if a more sophisticated allocator chooses to do that.
      31             : //
      32             : // This framework provides a way to engineer the compile time vs. code
      33             : // quality trade-off without relying on a particular theoretical solver.
      34             : //
      35             : //===----------------------------------------------------------------------===//
      36             : 
      37             : #ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H
      38             : #define LLVM_LIB_CODEGEN_REGALLOCBASE_H
      39             : 
      40             : #include "llvm/ADT/SmallPtrSet.h"
      41             : #include "llvm/CodeGen/RegisterClassInfo.h"
      42             : 
      43             : namespace llvm {
      44             : 
      45             : class LiveInterval;
      46             : class LiveIntervals;
      47             : class LiveRegMatrix;
      48             : class MachineInstr;
      49             : class MachineRegisterInfo;
      50             : template<typename T> class SmallVectorImpl;
      51             : class Spiller;
      52             : class TargetRegisterInfo;
      53             : class VirtRegMap;
      54             : 
      55             : /// RegAllocBase provides the register allocation driver and interface that can
      56             : /// be extended to add interesting heuristics.
      57             : ///
      58             : /// Register allocators must override the selectOrSplit() method to implement
      59             : /// live range splitting. They must also override enqueue/dequeue to provide an
      60             : /// assignment order.
      61             : class RegAllocBase {
      62             :   virtual void anchor();
      63             : 
      64             : protected:
      65             :   const TargetRegisterInfo *TRI = nullptr;
      66             :   MachineRegisterInfo *MRI = nullptr;
      67             :   VirtRegMap *VRM = nullptr;
      68             :   LiveIntervals *LIS = nullptr;
      69             :   LiveRegMatrix *Matrix = nullptr;
      70             :   RegisterClassInfo RegClassInfo;
      71             : 
      72             :   /// Inst which is a def of an original reg and whose defs are already all
      73             :   /// dead after remat is saved in DeadRemats. The deletion of such inst is
      74             :   /// postponed till all the allocations are done, so its remat expr is
      75             :   /// always available for the remat of all the siblings of the original reg.
      76             :   SmallPtrSet<MachineInstr *, 32> DeadRemats;
      77             : 
      78       19686 :   RegAllocBase() = default;
      79       19572 :   virtual ~RegAllocBase() = default;
      80             : 
      81             :   // A RegAlloc pass should call this before allocatePhysRegs.
      82             :   void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat);
      83             : 
      84             :   // The top-level driver. The output is a VirtRegMap that us updated with
      85             :   // physical register assignments.
      86             :   void allocatePhysRegs();
      87             : 
      88             :   // Include spiller post optimization and removing dead defs left because of
      89             :   // rematerialization.
      90             :   virtual void postOptimization();
      91             : 
      92             :   // Get a temporary reference to a Spiller instance.
      93             :   virtual Spiller &spiller() = 0;
      94             : 
      95             :   /// enqueue - Add VirtReg to the priority queue of unassigned registers.
      96             :   virtual void enqueue(LiveInterval *LI) = 0;
      97             : 
      98             :   /// dequeue - Return the next unassigned register, or NULL.
      99             :   virtual LiveInterval *dequeue() = 0;
     100             : 
     101             :   // A RegAlloc pass should override this to provide the allocation heuristics.
     102             :   // Each call must guarantee forward progess by returning an available PhysReg
     103             :   // or new set of split live virtual registers. It is up to the splitter to
     104             :   // converge quickly toward fully spilled live ranges.
     105             :   virtual unsigned selectOrSplit(LiveInterval &VirtReg,
     106             :                                  SmallVectorImpl<unsigned> &splitLVRs) = 0;
     107             : 
     108             :   // Use this group name for NamedRegionTimer.
     109             :   static const char TimerGroupName[];
     110             :   static const char TimerGroupDescription[];
     111             : 
     112             :   /// Method called when the allocator is about to remove a LiveInterval.
     113           1 :   virtual void aboutToRemoveInterval(LiveInterval &LI) {}
     114             : 
     115             : public:
     116             :   /// VerifyEnabled - True when -verify-regalloc is given.
     117             :   static bool VerifyEnabled;
     118             : 
     119             : private:
     120             :   void seedLiveRegs();
     121             : };
     122             : 
     123             : } // end namespace llvm
     124             : 
     125             : #endif // LLVM_LIB_CODEGEN_REGALLOCBASE_H