Home | History | Annotate | Download | only in CodeGen 
      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/CodeGen/LiveInterval.h"
     41 #include "llvm/CodeGen/RegisterClassInfo.h"
     42 
     43 namespace llvm {
     44 
     45 template<typename T> class SmallVectorImpl;
     46 class TargetRegisterInfo;
     47 class VirtRegMap;
     48 class LiveIntervals;
     49 class LiveRegMatrix;
     50 class Spiller;
     51 
     52 /// RegAllocBase provides the register allocation driver and interface that can
     53 /// be extended to add interesting heuristics.
     54 ///
     55 /// Register allocators must override the selectOrSplit() method to implement
     56 /// live range splitting. They must also override enqueue/dequeue to provide an
     57 /// assignment order.
     58 class RegAllocBase {
     59   virtual void anchor();
     60 protected:
     61   const TargetRegisterInfo *TRI;
     62   MachineRegisterInfo *MRI;
     63   VirtRegMap *VRM;
     64   LiveIntervals *LIS;
     65   LiveRegMatrix *Matrix;
     66   RegisterClassInfo RegClassInfo;
     67 
     68   RegAllocBase()
     69     : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {}
     70 
     71   virtual ~RegAllocBase() {}
     72 
     73   // A RegAlloc pass should call this before allocatePhysRegs.
     74   void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat);
     75 
     76   // The top-level driver. The output is a VirtRegMap that us updated with
     77   // physical register assignments.
     78   void allocatePhysRegs();
     79 
     80   // Get a temporary reference to a Spiller instance.
     81   virtual Spiller &spiller() = 0;
     82 
     83   /// enqueue - Add VirtReg to the priority queue of unassigned registers.
     84   virtual void enqueue(LiveInterval *LI) = 0;
     85 
     86   /// dequeue - Return the next unassigned register, or NULL.
     87   virtual LiveInterval *dequeue() = 0;
     88 
     89   // A RegAlloc pass should override this to provide the allocation heuristics.
     90   // Each call must guarantee forward progess by returning an available PhysReg
     91   // or new set of split live virtual registers. It is up to the splitter to
     92   // converge quickly toward fully spilled live ranges.
     93   virtual unsigned selectOrSplit(LiveInterval &VirtReg,
     94                                  SmallVectorImpl<unsigned> &splitLVRs) = 0;
     95 
     96   // Use this group name for NamedRegionTimer.
     97   static const char TimerGroupName[];
     98 
     99   /// Method called when the allocator is about to remove a LiveInterval.
    100   virtual void aboutToRemoveInterval(LiveInterval &LI) {}
    101 
    102 public:
    103   /// VerifyEnabled - True when -verify-regalloc is given.
    104   static bool VerifyEnabled;
    105 
    106 private:
    107   void seedLiveRegs();
    108 };
    109 
    110 } // end namespace llvm
    111 
    112 #endif
    113